1.E: Підрахунок (вправи)

Template:MathJaxLevin

1.1: Адитивні та мультиплікативні принципи

1

Ваш гардероб складається з 5 сорочок, 3 пар штанів і 17 краваток-метеликів. Скільки різних нарядів ви можете зробити?

Відповідь

Є 255 нарядів. Використовуйте мультиплікативний принцип.

2

Для співбесіди в коледжі ви повинні носити краватку. Ви володієте 3 звичайними (нудними) краватками та 5 (крутими) краватками-метеликами.

1. Скільки варіантів у вас є для одягу на шиї?
2. Ви розумієте, що інтерв'ю для клоунського коледжу, так що ви, ймовірно, повинні носити як звичайний краватку і краватку метелика. Скільки варіантів у вас зараз?
3. Для решти вашого вбрання у вас є 5 сорочок, 4 спідниці, 3 штани та 7 суконь. Ви хочете вибрати або сорочку, щоб носити зі спідницею або штанами, або просто плаття. Скільки нарядів ви повинні вибрати з?

Відповідь

1. 8 краватки. Скористайтеся принципом добавки.
2. 15 краватки. Використовуйте мультиплікативний принцип
3. \(5 \cdot (4+3) + 7 = 42\)наряди.

3

Ваша колекція Blu-ray складається з 9 комедій та 7 фільмів жахів. Наведемо приклад питання, на який відповідь:

1. 16.
2. 63.

Відповідь

1. Наприклад, 16 - це кількість варіантів, які ви маєте, якщо ви хочете переглянути один фільм, або комедію, або фільм жахів.
2. Наприклад, 63 - це кількість варіантів, які ви маєте, якщо ви будете дивитися два фільми, спочатку комедію, а потім жах.

4

Зазвичай ми пишемо числа в десятковій формі (або базу 10), тобто числа складаються з використанням 10 різних «цифр»\(\{0,1,\ldots, 9\}\text{.}\) Іноді, хоча корисно писати числа шістнадцяткові або базові 16. Тепер існує 16 різних цифр, які можуть бути використані для формування чисел:\(\{0, 1, \ldots, 9, \mathrm{A, B, C, D, E, F}\}\text{.}\) Так, наприклад, 3-значне шістнадцяткове число може бути 2B8.

1. Скільки двозначних шістнадцяткових знаків, в яких перша цифра - E або F? Поясніть свою відповідь з точки зору адитивного принципу (використовуючи або події, або множини).
2. Поясніть, чому ваша відповідь на попередню частину правильна з точки зору мультиплікативного принципу (використовуючи або події, або множини). Чому і адитивний, і мультиплікативний принципи дають вам однакову відповідь?
3. Скільки тризначних шістнадцяткових знаків починаються з літери (A-F) і закінчуються цифрою (0-9)? Поясніть.
4. Скільки тризначних шістнадцяткових знаків починаються з літери (A-F) або закінчуються числівником (0-9) (або обидва)? Поясніть.

5

Припустимо, у вас є\(A\) набори і\(B\) з\(\card{A} = 10\) і\(\card{B} = 15\text{.}\)

1. Яке максимально можливе значення для\(\card{A \cap B}\text{?}\)
2. Яке найменше можливе значення\(\card{A \cap B}\text{?}\)
3. Які можливі значення для\(\card{A \cup B}\text{?}\)

Відповідь

1. Щоб максимізувати кількість спільних елементів між\(A\) і\(B\text{,}\) зробити\(A \subset B\text{.}\) Це дало б\(\card{A \cap B} = 10\text{.}\)
2. \(A\)і\(B\) може не мати спільних елементів, даючи\(\card{A\cap B} = 0\text{.}\)
3. \(15 \le \card{A \cup B} \le 25\text{.}\)Насправді, коли\(\card{A \cap B} = 0\) тоді\(\card{A \cup B} = 25\) і коли\(\card{A \cap B} = 10\) тоді\(\card{A \cup B} = 15\text{.}\)

6

Якщо\(\card{A} = 8\) і\(\card{B} = 5\text{,}\) що\(\card{A \cup B} + \card{A \cap B}\text{?}\)

Відповідь

\(\card{A \cup B} + \card{A \cap B} = 13\text{.}\)Використовуйте PIE: ми знаємо\(\card{A \cup B} = 8 + 5 - \card{A \cap B}\text{.}\)

7

Групу студентів коледжу запитали про їхні звички перегляду телевізора. З опитаних 28 студентів дивляться «Ходячі мерці», 19 дивляться «Чорний список» та 24 дивляться «Гру престолів». Крім того, 16 дивіться «Ходячі мерці» та «Чорний список», 14 дивіться «Ходячі мерці» та «Гра престолів» та «Чорний список» та «Гра престолів». Є 8 студентів, які дивляться всі три шоу. Скільки опитаних студентів дивилися хоча б одне з шоу?

Відповідь

39 студентів. Використовуйте PIE або діаграму Венна.

8

В недавньому опитуванні 30 студентів повідомили, чи сподобалося їм картопляне пюре, смажене по-французьки або двічі запечене. 15 любили їх пюре, 20 любили картоплю фрі, а 9 любили двічі запечену картоплю. Крім того, 12 студентів любили як пюре, так і смажену картоплю, 5 любили картоплю фрі і двічі запечена картопля, 6 любили пюре і запечена, а 3 сподобалися всі три стилі. Скільки студентів ненавидять картоплю? Поясніть, чому ваша відповідь правильна.

9

За скільки\(n \in \{1,2, \ldots, 500\}\)\(n\) кратна одному або більше 5, 6 або 7?

Підказка:

Щоб дізнатися, скільки чисел ділимо на 6 і 7, наприклад, візьмемо\(500/42\) і округляємо вниз.

10

Нехай\(A\text{,}\)\(B\text{,}\) і\(C\) будуть набори.

1. Знайти\(\card{(A \cup C)\setminus B}\) надані\(\card{A} = 50\text{,}\)\(\card{B} = 45\text{,}\)\(\card{C} = 40\text{,}\)\(\card{A\cap B} = 20\text{,}\)\(\card{A \cap C} = 15\text{,}\)\(\card{B \cap C} = 23\text{,}\) та\(\card{A \cap B \cap C} = 12\text{.}\)
2. Опишіть набір з точки зору\(A\text{,}\)\(B\text{,}\) і\(C\) з кардинальністю 26.

11

Розглянемо всі 5 літерних «слів», зроблених з букв\(a\) через\(h\text{.}\) (Нагадаємо, слова - це просто рядки букв, не обов'язково фактичні англійські слова.)

1. Скільки всього цих слів?
2. Скільки з цих слів не містять повторюваних букв?
3. Скільки з цих слів починаються з підслова «аха»?
4. Скільки з цих слів або починаються на «ага», або закінчуються на «бах» або обидва?
5. Скільки слів, що не містять повторів, також не містять підслова «погано»?

Відповідь

1. \(8^5 = 32768\)слова, так як ви вибираєте з 8 букв 5 разів.
2. \(8\cdot 7\cdot 6\cdot 5\cdot 4 = 6720\)слова. Після вибору літери у вас буде менше літер, щоб вибрати для наступного.
3. \(8 \cdot 8 =64\)слова: потрібно виділити 4-ю і 5-ю літери.
4. \(64 + 64 - 0 = 128\)слова. Є 64 слова, які починаються з «ага» і ще 64 слова, що закінчуються на «бах». Можливо, ми перерахували слова, які обидва починаються на «ага» і закінчуються на «бах», але оскільки слова довжиною всього 5 букв, таких слів немає.
5. \((8\cdot 7\cdot 6\cdot 5\cdot 4) - 3\cdot (5\cdot 4) = 6660\)слова. Всі слова мінус погані. Слово табу може бути в будь-якій з трьох позицій (починаючи з літери 1, 2 або 3), і для кожної позиції ми повинні вибрати дві інші літери (з решти 5 букв).

12

За скільки тризначних чисел (від 100 до 999) дорівнює сумі цифр парних? (Наприклад,\(343\) має парну суму цифр:\(3+4+3 = 10\) яка парна.) Знайдіть відповідь і поясніть, чому це правильно принаймні двома різними способами.

13

Число 735000 факторів\(2^3 \cdot 3 \cdot 5^4 \cdot 7^2\text{.}\) як Скільки дільників він має? Поясніть свою відповідь, використовуючи мультиплікативний принцип.

1.2: Біноміальні коефіцієнти

1

Нехай\(S = \{1, 2, 3, 4, 5, 6\}\)

1. Скільки підмножин є загальним?
2. Скільки підмножин мають\(\{2,3,5\}\) як підмножину?
3. Скільки підмножин містять хоча б одне непарне число?
4. Скільки підмножин містять рівно одне парне число?

Відповідь

1. \(2^6 = 64\)підмножини. Нам потрібно вибрати так/ні для кожного з шести елементів.
2. \(2^3 = 8\)підмножини. Нам потрібно вибрати так/ні для кожного з решти трьох елементів.
3. \(2^6 - 2^3 = 56\)підмножини. Є 8 підмножин, які не містять непарних чисел (виберіть так/ні для кожного парного числа).
4. \(3\cdot 2^3 = 24\)підмножини. Спочатку виберіть парне число. Потім скажіть «так» чи «ні» кожному з непарних чисел.

2

Нехай\(S = \{1, 2, 3, 4, 5, 6\}\)

1. Скільки існує підмножин кардинальності 4?
2. Скільки підмножин кардинальності 4 мають\(\{2,3,5\}\) як підмножини?
3. Скільки підмножин кардинальності 4 містять хоча б одне непарне число?
4. Скільки підмножин кардинальності 4 містять рівно одне парне число?

Відповідь

1. \({6\choose 4} = 15\)підмножини.
2. \({3 \choose 1} = 3\)підмножини. Нам потрібно вибрати 1 з 3 інших елементів, які будуть в підмножині.
3. \({6 \choose 4} = 15\)підмножини. Всі підмножини кардинальності 4 повинні містити хоча б одне непарне число.
4. \({3 \choose 1} = 3\)підмножини. Виберіть 1 з 3 парних чисел. Решта три непарних числа\(S\) повинні бути всі в наборі.

3

Нехай\(A = \{1,2,3,\ldots,9\}\text{.}\)

1. Скільки підмножин\(A\) існує? Тобто знайдіть\(|\pow(A)|\text{.}\) Поясніть.
2. Скільки підмножин\(A\) містять рівно 5 елементів? Поясніть.
3. Скільки підмножин\(A\) містять лише парні числа? Поясніть.
4. Скільки підмножин\(A\) містять парну кількість елементів? Поясніть.

4

Скільки\(9\) -bit рядків (тобто бітових рядків довжиною 9) є які:

1. Почніть з підрядка 101? Поясніть.
2. Мають вагу 5 (тобто містять рівно п'ять 1) і почати з підрядка 101? Поясніть.
3. Або почати з\(101\) або закінчити з\(11\) (або обидва)? Поясніть.
4. Маєте вагу 5 і або починаєте з 101 або закінчуєте з 11 (або обидва)? Поясніть.

5

Ви розбиваєте свій скарбничний банк, щоб виявити багато копійок і нікелів. Ви починаєте влаштовувати їх в рядах по 6 монет.

1. Ви опиняєтеся, роблячи рядки, що містять рівну кількість копійок і нікелів. Для забави ви вирішите викладати всілякі такі ряди. Скільки монет вам знадобиться?
2. Скільки монет вам потрібно, щоб зробити всі можливі ряди з 6 монет (не обов'язково з рівною кількістю копійок і нікелів)?

Відповідь

1. Ми можемо думати про кожен рядок як 6-бітний рядок вагою 3 (оскільки з 6 монет, ми вимагаємо 3, щоб бути копійки). Таким чином, можливі\({6 \choose 3} = 20\) ряди. Кожен ряд вимагає 6 монет, тому, якщо ми хочемо зробити всі ряди одночасно, нам знадобиться 120 монет (60 з кожного).
2. Тепер можливі\(2^6 = 64\) рядки, що також є,\({6 \choose 0} + {6\choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}\text{,}\) якщо ви розбиваєте їх на рядки, що містять 0, 1, 2 і т.д. копійки. Таким чином нам знадобляться\(6 \cdot 64 = 384\) монети (по 192 з кожної).

6

Скільки 10-бітних рядків містять 6 або більше одиниць?

Відповідь

\({10 \choose 6} + {10\choose 7} + {10\choose 8} + {10 \choose 9} + {10\choose 10} = 386\)струни. Підрахуйте кількість рядків з кожним допустимим числом 1 окремо, потім складіть їх.

7

Скільки підмножин\(\{0,1,\ldots, 9\}\) мають кардинальність 6 або більше?

Підказка:

Розбийте питання на п'ять випадків.

8

Що таке коефіцієнт\(x^{12}\) в\((x+2)^{15}\text{?}\)

Відповідь

Щоб отримати,\(x^{12}\text{,}\) ми повинні вибрати 12 з 15 факторів, щоб сприяти\(x\text{,}\) залишенню інших 3, щоб внести 2. Існують\({15 \choose 12}\) способи вибору цих 12 факторів. Отже, термін, що містить\(x^{12}\) буде\({15 \choose 12}x^{12}2^{3}\text{.}\) Іншими словами,\(x^{12}\) коефіцієнт\({15\choose 12}2^3 = 3640\text{.}\)

9

Який коефіцієнт\(x^9\) в розширенні\((x+1)^{14} + x^3(x+2)^{15}\text{?}\)

10

Скільки найкоротших ґратчастих шляхів починаються з (3,3) і

1. кінець на (10,10)?
2. закінчити на (10,10) і пройти через (5,7)?
3. закінчуватися на (10,10) і уникати (5,7)?

Відповідь

1. \({14 \choose 7} = 3432\)доріжки. Всі шляхи мають довжину 14 (7 кроків вгору і 7 кроків праворуч), ми просто вибираємо, які 7 з цих 14 повинні бути вгору.
2. \({6 \choose 2}{8\choose 5} = 840\)доріжки. Спочатку подорожуйте до (5,7), а потім продовжуйте до (10,10).
3. \({14 \choose 7} - {6\choose 2}{8 \choose 5}\)доріжки. Видаліть всі шляхи, які ви знайшли в частині (b).

11

Gridtown США, крім того, що мають відмінні пончики, відомий своєю точно викладеною сіткою вулиць і проспектів. Вулиці проходять схід-захід, а проспекти північ-південь, на всю ділянку міста, ніколи не вигинаючись і ніколи не перериваються парками чи школами тощо.

Припустимо, ви живете на розі 1-го і 1-го і працюєте на розі 12-го і 12-го. Таким чином, ви повинні подорожувати 22 блоки, щоб дістатися до роботи якомога швидше.

1. Скільки різних маршрутів ви можете взяти на роботу, якщо ви хочете дістатися туди якомога швидше?
2. Тепер припустимо, ви хочете зупинитися і отримати пончик по дорозі на роботу, з улюбленого магазину пончиків на розі 8-го і 10-го пр. Скільки маршрутів працювати, через магазин пончиків, ви можете взяти (знову ж таки, забезпечивши найкоротший маршрут)?
3. Катастрофа вражає Gridtown: є вибоїна на 4-й авеню між 5-ю та 6-ю вулицями. Скільки маршрутів для роботи ви можете зробити, уникаючи цього непривабливого (і небезпечного) ділянки дороги?
4. Скільки маршрутів є як уникаючи вибоїни, так і відвідування магазину пончиків?

12

Припустимо, ви замовляєте велику піцу від D.P. тісто. Ви хочете 3 різні начинки, вибрані зі списку з 11 вегетаріанських начинок.

1. Скільки варіантів у вас є для піци?
2. Скільки варіантів у вас є для піци, якщо ви відмовляєтеся мати ананас як одну з ваших начинок?
3. Скільки варіантів у вас є для піци, якщо ви наполягаєте на тому, щоб ананас був однією з ваших начинок?
4. Як три вищезазначені питання пов'язані один з одним?

13

Поясніть, чому\(x^5y^3\) коефіцієнт такий же, як коефіцієнт\(x^3y^5\) в розширенні\((x+y)^8\text{?}\)

1.3: Комбінації та перестановки

1

Піцерія пропонує 10 начинок.

1. Скільки піц з 3-топінгом вони могли б покласти у своє меню? Припустімо, що подвійні начинки не допускаються.
2. Скільки загальної піци можливо, з дозволеними від нуля до десяти начинок (але не подвійних начинок)?
3. Піцерія перерахує 10 начинок у двох стовпцях однакового розміру у своєму меню. Скільки способів вони можуть розташувати начинки в лівій колонці?

Відповідь

1. \({10 \choose 3} = 120\)піци. Ми повинні вибрати (в особливому порядку) 3 з 10 начинки.
2. \(2^{10} = 1024\)піци. Скажіть «так» чи «ні» кожному топінгу.
3. \(P(10,5) = 30240\)способи. Призначте кожному з 5 місць в лівій колонці унікальну начинку піци.

2

Кодовий замок складається з циферблата з 40 номерами на ньому. Щоб відкрити замок, ви повертаєте циферблат вправо, поки не дійдете до першого номера, потім вліво, поки не потрапите на другий номер, потім вправо знову на третій номер. Цифри повинні бути різними. Скільки різних комбінацій можливо?

Відповідь

Незважаючи на свою назву, ми не шукаємо тут комбінацію. Має значення порядок, в якому з'являються три числа. Існують\(P(40,3) = 40\cdot 39 \cdot 38\) різні можливості для «комбінації». Це припускає, що ви не можете повторити жодне з чисел (якщо б ви могли, відповідь була б\(40^3\)).

3

Використовуючи цифри від 2 до 8, знайдіть кількість різних 5-значних чисел таких, що:

1. Цифри можна використовувати більше одного разу.
2. Цифри не можуть повторюватися, але можуть прийти в будь-якому порядку.
3. Цифри не можуть повторюватися і повинні бути записані у зростаючому порядку.
4. Який з перерахованих вище питань підрахунку є комбінацією, а який - перестановкою? Поясніть, чому це має сенс.

4

Скільки трикутників з вершинами з точок, показаних нижче? Зауважте, ми не допускаємо вироджених трикутників - тих, у яких всі три вершини на одній лінії, але ми допускаємо неправильні трикутники. Поясніть, чому ваша відповідь правильна.

Підказка:

Вам потрібно рівно дві точки на\(y\) осі\(x\) - або -, але не перерахуйте правильні трикутники.

5

Скільки чотирикутників ви можете намалювати, використовуючи точки нижче як вершини (кути)?

Відповідь

\({7\choose 2}{7\choose 2} = 441\)чотирикутники. Ми повинні вибрати дві з семи точок з верхнього ряду і дві з семи точок на нижньому ряду. Однак не має значення, який з двох (у кожному рядку) ми вибираємо першим, оскільки після того, як ці чотири точки вибрані, вони визначають рівно один чотирикутник.

6

Скільки чотирикутників можливих в попередній задачі:

1. Квадрати?
2. Прямокутники?
3. Паралелограми?
4. Трапеції? ² Тут, як і в численні, трапеція визначається як чотирикутник з хоча б однією парою паралельних сторін. Зокрема, паралелограми - це трапеції.
5. Трапеції, які не є паралелограмами?

Відповідь

1. 5 квадратів. Потрібно пропустити рівно одну крапку зверху і знизу, щоб довжини сторін були рівними. Після того, як ви виберете крапку на вершині, інші три точки визначаються.
2. \({7 \choose 2}\)прямокутники. Після того, як ви виберете дві точки вгорі, визначаються дві нижні.
3. Це складно, оскільки вам потрібно турбуватися про вичерпання місця. Один із способів підрахунку: розбивати на футляри по розташуванню лівого верхнього кута. У вас\({7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\) вийдуть паралелограми.
4. Всі вони
5. \({7\choose 2}{7\choose 2} - \left[ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right]\text{.}\)Всі вони, крім паралелограмів.

7

Анаграма слова - це всього лише перестановка його букв. Скільки існує різних анаграм «незахищених авторським правом»? (Це трапляється найдовшим загальним англійським словом без повторюваних букв.)

8

Скільки анаграм слова «оцінює», які починаються з літери «а»?

Відповідь

Після першої літери (а) ми повинні переставити залишилися 7 букв. Є тільки дві літери (s і e), так що це дійсно просто біт-рядок питання (думаю про s як 1 і е як 0). При цьому з'являються\({7 \choose 2} = 21\) анаграми, що починаються з «а».

9

Скільки існує анаграм «анаграми»?

10

На діловому відступі, ваша компанія з 20 бізнесменів і бізнес-леді йти в гольф.

1. Потрібно розділити на четвірки (групи по 4 людини): першу четвірку, другу четвірку і так далі. Скільки способів ви можете це зробити?
2. Після всієї вашої важкої роботи ви розумієте, що насправді ви хочете, щоб кожна четвірка включала одного з п'яти членів Правління. Скільки способів ви можете це зробити?

Відповідь

1. \({20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\)способи. Виберіть 4 з 20 осіб, які будуть в першій четвірці, потім 4 з решти 16 для другої четвірки і так далі (використовуйте мультиплікативний принцип для об'єднання).
2. \(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\)способи. Спочатку визначити час трійника 5 членів ради, потім виберіть 3 з 15 не членів правління для гольфу з першим членом правління, потім 3 з решти 12 для гольфу з другим, і так далі.

11

Скільки різних розсадження можливі для короля Артура і його 9 лицарів навколо їх круглого столу?

Відповідь

\(9!\)(За столом сидять 10 чоловік, але не важливо, де сидить король Артур, тільки хто сидить зліва від нього, два місця зліва від нього і так далі).

12

Розглянемо\(A\) набори і\(B\) з\(|A| = 10\) і\(|B| = 17\text{.}\)

1. Скільки функцій\(f: A \to B\) існує?
2. Скільки функцій\(f: A \to B\) є ін'єкційними?

Відповідь

1. \(17^{10}\)функції. Існує 17 варіантів для зображення кожного елемента в домені.
2. \(P(17, 10)\)ін'єкційні функції. Є 17 варіантів для зображення першого елемента домену, потім лише 16 варіантів для другого і так далі.

13

Розглянемо функції\(f: \{1,2,3,4\} \to \{1,2,3,4,5,6\}\text{.}\)

1. Скільки функцій є всього?
2. Скільки функцій є ін'єкційними?
3. На скільки збільшуються ін'єкційні функції? Збільшення означає, що якщо\(a \lt b\) потім\(f(a) \lt f(b)\text{,}\) або іншими словами, виходи стають більшими, оскільки входи стають більшими.

14

Ми бачили, що формула для\(P(n,k)\) це\(\dfrac{n!}{(n-k)!}\text{.}\) Ваше завдання тут полягає в тому, щоб пояснити, чому це правильна формула.

1. Припустимо, у вас є 12 фішок, кожна різного кольору. Скільки різних стеків з 5 фішок ви можете зробити? Поясніть свою відповідь і чому вона така ж, як використання формули для\(P(12,5)\text{.}\)
2. Використовуючи сценарій 12 фішок знову, що\(12!\) рахується? Що\(7!\) розраховує? Поясніть.
3. Поясніть, чому має сенс ділити\(12!\) на\(7!\) при обчисленні\(P(12,5)\) (в плані чіпів).
4. Чи працює ваше пояснення для чисел, відмінних від 12 і 5? Поясніть формулу\(P(n,k) = \frac{n!}{(n-k)!}\) за допомогою змінних\(n\) і\(k\text{.}\)

1.4: Комбінаторні докази

1

Доведіть особу\({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) за допомогою питання про підмножини.

Відповідь

Доказ

Питання: Скільки підмножин розміру\(k\) є в множині\(\{1,2,\ldots, n\}\text{?}\)

Відповідь 1: Ви повинні вибрати\(k\) з\(n\) елементів, які потрібно покласти в набір, що можна зробити\({n \choose k}\) способами.

Відповідь 2: Спочатку підрахуйте кількість підмножин\(k\) -елементів,\(\{1,2,\ldots, n\}\) які містять число\(n\text{.}\) Ми повинні вибрати\(k-1\)\(n-1\) інший елемент для включення в цей набір. При цьому є\({n-1\choose k-1}\) такі підмножини. Ми ще не порахували всі\(k\) -element підмножини\(\{1,2,\ldots, n\}\) хоча. Насправді ми пропустили саме ті підмножини, які НЕ містять\(n\text{.}\) Щоб сформувати одну з цих підмножин, нам потрібно вибрати\(k\) інші\(n-1\) елементи, тому це можна зробити\({n-1 \choose k}\) способами. Таким чином, відповідь на питання\({n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

Оскільки дві відповіді є обома відповідями на одне і те ж питання, вони рівні, встановлюючи ідентичність\({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

\(\square\)

2

Дайте комбінаторне підтвердження особи\(2+2+2 = 3\cdot 2\text{.}\)

Відповідь

Доказ

Питання: Скільки дволітерних слів починаються з a, b або c і закінчуються на y або z?

Відповідь 1: Є два слова, які починаються з a, два, які починаються з b, два, які починаються з c, загалом\(2+2+2\text{.}\)

Відповідь 2: Є три варіанти для першої літери та два варіанти для другої літери, загалом\(3 \cdot 2\text{.}\)

Оскільки дві відповіді є обома відповідями на одне і те ж питання, вони рівні. Таким чином\(2 + 2 + 2 = 3\cdot 2\text{.}\)

\(\square\)

3

Дайте комбінаторний доказ особистості\(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\)

Відповідь

Доказ

Питання: Скільки підмножин\(A = {1,2,3, \ldots, n+1}\) містять рівно два елементи?

Відповідь 1: Ми повинні вибрати 2 елементи з\(n+1\) вибору, тому є\({n+1 \choose 2}\) підмножини.

Відповідь 2: Ми розбиваємо це питання на випадки, виходячи з того, що більший з двох елементів у підмножині. Більший елемент не може бути 1, оскільки нам потрібен принаймні один елемент менше, ніж він.

Більший елемент - 2: є 1 вибір для меншого елемента.

Більший елемент - 3: є 2 варіанти для меншого елемента.

Більший елемент - 4: є 3 варіанти для меншого елемента.

І так далі. Коли більший елемент\(n+1\text{,}\) є\(n\) вибір для меншого елемента. Оскільки кожні два підмножини елементів повинні бути точно в одному з цих випадків, загальна кількість двох підмножин елементів дорівнює\(1 + 2 + 3 + \cdots + n\text{.}\)

Відповідь 1 і відповідь 2 - це правильні відповіді на одне і те ж питання, тому вони повинні бути рівними. Тому

\ begin {рівняння*} 1 + 2 + 3 +\ cdots + n = {n+1\ вибрати 2}\ end {рівняння*}

\(\square\)

4

Жінка виходить заміж. Вона має 15 кращих друзів, але може вибрати лише 6 з них, щоб бути її подружками нареченої, одна з яких повинна бути її фрейліна. Скільки способів вона може це зробити?

1. Що робити, якщо вона спочатку вибере 6 подружок нареченої, а потім вибере одну з них, щоб стати фрейліною?
2. Що робити, якщо вона спочатку вибере свою фрейліну, а потім 5 інших подружок нареченої?
3. Поясніть, чому\(6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\)

Відповідь

1. У неї є\({15 \choose 6}\) способи вибрати 6 подружок нареченої, а потім для кожного способу, має 6 варіантів для фрейліни. Таким чином, у неї є\({15 \choose 6}6\) вибір.
2. У неї є 15 варіантів того, хто буде її фрейліною. Потім їй потрібно вибрати 5 з решти 14 друзів, щоб бути подружками нареченої, що вона може зробити\({14 \choose 5}\) різними способами. Таким чином, у неї є\(15 {14 \choose 5}\) вибір.
3. Ми відповіли на питання (скільки весільних вечірок може вибрати наречена) двома способами. Перший спосіб дає ліву сторону ідентичності, а другий спосіб дає праву частину ідентичності. Тому особистість тримається.

5

Дайте комбінаторне підтвердження особи\({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\)

Відповідь

Доказ

Питання: У вас є великий контейнер, наповнений кульками для пінг-понгу, всі з різною кількістю на них. Ви повинні вибрати\(k\) з кульок, поклавши два з них в банку, а інші в коробку. Скільки способів ви можете це зробити?

Відповідь 1: Спочатку виберіть 2\(n\) кульки, які потрібно покласти в банку. Потім виберіть\(k-2\) з решти\(n-2\) кульок покласти в коробку. Перше завдання можна виконати\({n \choose 2}\) по-різному, друге -\({n-2 \choose k-2}\) способами. Таким чином, існують\({n \choose 2}{n-2 \choose k-2}\) способи вибору кульок.

Відповідь 2: Спочатку виберіть\(k\) кульки\(n\) з контейнера. Потім виберіть 2\(k\) кульки, які ви вибрали, щоб покласти в банку, помістивши решту\(k-2\) в коробку. Перше завдання можна виконати\({n \choose k}\) способами, друге -\({k \choose 2}\) способами. Таким чином, існують\({n \choose k}{k \choose 2}\) способи вибору кульок.

Оскільки обидві відповіді вважають одне і те ж, вони повинні бути рівними і ідентичність встановлена.

\(\square\)

6

Розглянемо бітові рядки в\(\B^6_2\) (бітові рядки довжиною 6 і вагою 2).

1. Скільки з цих бітових рядків починаються з 1?
2. Скільки з цих бітових рядків починаються з 01?
3. Скільки з цих бітових рядків починаються з 001?
4. Чи є ще якісь рядки, які ми ще не рахували? Які з них, і скільки їх?
5. Скільки бітових рядків всього в\(\B^6_2\text{?}\)
6. Яку біноміальну ідентичність ви щойно дали комбінаторний доказ?

Відповідь

1. Після 1 нам потрібно знайти 5-бітну рядок з однією 1. Для цього є\({5 \choose 1}\) способи.
2. \({4 \choose 1}\)струни (нам потрібно забрати 1 з решти 4 слотів, щоб бути другий 1).
3. \({3 \choose 1}\)струни.
4. Так. Нам все ще потрібні рядки, що починаються\({2 \choose 1}\) з 0001 (є такі) і рядки, починаючи з 00001 (є тільки\({1 \choose 1} = 1\) з них).
5. \({6 \choose 2}\)струни
6. Приклад теореми про хокейну ключку:\ begin {рівняння*} {1\ вибрати 1} + {2\ вибрати 1} + {3\ choose 1} + {4\ choose 1} + {5\ choose 1} = {6\ choose 2}\ end {рівняння*}

7

Давайте порахуємо потрійні рядки цифр, тобто рядки, в яких кожна цифра може бути 0, 1 або 2.

1. Скільки рядків з трійчастими цифрами містять саме\(n\) цифри?
2. Скільки рядків трійчастих\(n\) цифр містять точно цифри і\(n\) 2.
3. Скільки рядків з трійчастими\(n\) цифрами містять точно цифри і\(n-1\) 2. (Підказка: куди можна поставити не 2 цифру, а потім що це може бути?)
4. Скільки рядків трійчастих\(n\) цифр містять точно цифри і\(n-2\) 2. (Підказка: див. попередню підказку)
5. Скільки рядків трійчастих\(n\) цифр містять точно цифри і\(n-k\) 2.
6. Скільки рядків з трійчастими\(n\) цифрами містять точно цифри і не 2. (Підказка: що це за рядок?)
7. Використовуйте наведені вище частини, щоб дати комбінаторне підтвердження ідентичності\ begin {рівняння*} {n\ choose 0} + 2 {n\ choose 1} + 2^2 {n\ choose 2} + 2^3 {n\ choose 3} +\ cdots + 2^n {n\ choose n} = 3^n.\ end {рівняння*}

Відповідь

1. \(3^n\)рядків, так як є 3 варіанти для кожної з\(n\) цифр.
2. \(1\)string, так як всі цифри повинні бути 2. Однак, ми могли б написати це як\({n \choose 0}\) рядки.
3. Є\({n \choose 1}\) місця, щоб поставити не2 цифру. Ця цифра може бути як 0, так і 1, тому є\(2{n \choose 1}\) такі рядки.
4. Ми повинні вибрати два слоти, щоб заповнити нулями або 1, є\({n \choose 2}\) способи зробити це. Після вибору слотів у нас є два варіанти для першого слота (0 або 1) та два варіанти для другого слота (0 або 1). Так що є в цілому\(2^2{n \choose 2}\) таких рядків.
5. Є\({n \choose k}\) способи вибрати, які слоти не мають 2, тоді ці слоти можуть бути заповнені\(2^k\) способами (0 або 1 для кожного слота). Так і є\(2^k{n \choose k}\) такі струни.
6. Ці рядки містять лише 0 та 1, тому вони є бітовими рядками. Є\(2^n\) бітові рядки. Але дотримуючись шаблону вище, ми могли б написати це як\(2^n {n \choose n}\) рядки.
7. Відповідаємо на питання про те, скільки довжини\(n\) трійчастих розрядних рядків існує двома способами. По-перше, кожна цифра може бути одним з трьох варіантів, так що загальна кількість рядків є\(3^n\text{.}\) З іншого боку, ми могли б розбити питання на випадки, скільки з цифр 2, Якщо вони всі 2, то є\({n \choose 0}\) рядки. Якщо все, крім одного, є 2, то є\(2{n \choose 1}\) рядки. Якщо всі цифри, крім 2, є 2, то є\(2^2{n \choose 2}\) рядки. Ми вибираємо 2 з\(n\) цифр, щоб бути не-2, а потім є 2 варіанти для кожної з цих цифр. І так далі для кожного можливого числа 2 в рядку. Тому\({n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \)

8

Скільки існує способів переставити букви в слові «переставляти»? Відповісти на це питання щонайменше двома різними способами встановлення біноміальної ідентичності.

Відповідь

Слово містить 9 букв: 3 «r» s, 2 «a» s і 2 «e» s разом з «n» і «g». Ми могли б спочатку вибрати позиції для «r» s\({9 \choose 3}\) способами, потім «a» s\({6 \choose 2}\) способами, «e» s\({4 \choose 2}\) способами, а потім вибрати одне з решти двох місць, щоб поставити «n» (розміщення «g» в останньому місці). Це дає відповідь

\ begin {рівняння*} {9\ вибрати 3} {6\ вибрати 2} {4\ вибрати 2} {2\ choose 1} {1\ choose 1}. \ end {рівняння*}

Крім того, ми могли б вибрати позиції букв у протилежному порядку, що дало б відповідь

\ begin {рівняння*} {9\ вибрати 1} {8\ вибрати 1} {7\ вибрати 2} {5\ вибрати 2} {3\ вибрати 3}. \ end {рівняння*}

(де 3 «r» s йдуть в інших 3 місцях). Ці два вирази рівні:

9

Дайте комбінаторний доказ особистості\(P(n,k) = {n \choose k}k!\)

Відповідь

Доказ

Питання: Скільки слів\(k\) -letter ви можете зробити, використовуючи\(n\) різні літери, не повторюючи жодної літери?

Відповідь 1: Є\(n\) варіанти для першої літери,\(n-1\) варіанти для другої літери,\(n-2\) варіанти для третьої літери тощо, поки не будуть\(n - (k-1)\) варіанти для\(k\) ї літери (оскільки\(k-1\) літери вже були призначені в цей момент). Добуток цих чисел може бути записаний\(\frac{n!}{(n-k)!}\) який є\(P(n,k)\text{.}\) Тому є\(P(n,k)\) слова.

Відповідь 2: Спочатку виберіть\(k\) літери, які будуть в слові з\(n\) вибору. Це можна зробити\({n \choose k}\) способами. Тепер розташуйте ці літери в слово. Є\(k\) вибір для першої літери,\(k-1\) вибір для другої і так далі, для загальної кількості\(k!\) композицій\(k\) листів. Таким чином, загальна кількість слів\({n \choose k}k!\text{.}\)

Оскільки дві відповіді є правильними відповідями на одне і те ж питання, ми встановили, що\(P(n,k) = {n \choose k}k!\text{.}\)

\(\square\)

10

Встановіть ідентифікацію нижче за допомогою комбінаторного доказу.

\ begin {рівняння*} {2\ вибрати 2} {n\ вибрати 2} + {3\ вибрати 2} {n-1\ вибрати 2} + {4\ вибрати 2} {n-2\ вибрати 2} +\ cdots + {n\ вибрати 2} {2\ вибрати 2} = {n+3\ вибрати 5}. \ end {рівняння*}

Відповідь

Доказ

Питання: Скільки 5-елементних підмножин у множині\(\{1,2,\ldots, n+3\}\text{.}\)

Відповідь 1: Ми вибираємо 5 з\(n+3\) елементів, тому\({n+3 \choose 5}\) підмножини.

Відповідь 2: Розбийте це на випадки, якими є «середній» (третій найменший) елемент підмножини елементів 5. Найменшим це може бути 3. У цьому випадку у нас є\({2 \choose 2}\) вибір для чисел під ним, і\({n \choose 2}\) вибір для чисел над ним. Крім того, середнє число може бути 4. У цьому випадку є\({3 \choose 2}\) вибір для двох нижніх чисел і\({n-1 \choose 2}\) вибір для двох верхніх чисел. Якщо середнє число дорівнює 5, то є\({4 \choose 2}\) вибір для двох нижніх чисел і\({n-2 \choose 2}\) вибір для двох верхніх чисел. І так далі, аж до найбільшого середнього числа може бути, який є\(n+1\text{.}\) У цьому випадку є\({n \choose 2}\) вибір для двох нижніх чисел і\({2 \choose 2}\) вибір для верхнього числа. Таким чином, кількість підмножин елементів 5 дорівнює

\ begin {рівняння*} {2\ вибрати 2} {n\ вибрати 2} + {3\ вибрати 2} {n-1\ вибрати 2} + {4\ вибрати 2} {n-2\ вибрати 2} +\ cdots + {n\ choose 2} {2\ choose 2}. \ end {рівняння*}

Оскільки дві відповіді правильно відповідають на одне і те ж питання, ми маємо\ begin {рівняння*} {2\ вибрати 2} {n\ choose 2} + {3\ choose 2} {n-1\ choose 2} {n-2\ choose 2} +\ cdots + {n\ choose 2} {2\ choose 2} = {n+3\ choose 5}. \ end {рівняння*}

1.5: Зірки та бари

1

Мультимножина - це колекція об'єктів, подібно до множини, але може містити об'єкт більше одного разу (порядок елементів все ще не має значення). Наприклад,\(\{1,1, 2, 5, 5, 7\}\) це мультімножина розміром 6.

1. Скільки наборів розміру 5 можна зробити за допомогою 10 числових цифр від 0 до 9?
2. Скільки мульти наборів розміром 5 можна зробити за допомогою 10 цифрових цифр від 0 до 9?

Відповідь

1. \({10\choose 5}\)набори. Ми повинні вибрати 5 з 10 цифр, щоб покласти в набір.
2. Використовуйте зірки та смуги: кожна зірка представляє один з 5 елементів набору, кожен бар являє собою перемикання між цифрами. Отже, є 5 зірок і 9 барів, що дають нам\({14 \choose 9}\) набори.

2

Кожна з наведених нижче задач підрахунку може бути вирішена за допомогою зірок і стовпчиків. Для кожного скажіть, який результат діаграми

\ begin {рівняння*} ***||||**|\ end {рівняння*}

являє собою, якщо є правильне число зірок і смуг для задачі. В іншому випадку скажіть, чому діаграма не представляє ніякого результату, і як виглядала б правильна діаграма.

1. Скільки способів вибрати жменю 6 желе з банки, яка містить 5 різних смаків?
2. Скільки способів можна розподілити 5 однакових льодяників 6 дітям?
3. Скільки слів з 6 букв ви можете зробити, використовуючи 5 голосних?
4. Скільки існує розв'язків рівняння\(x_1 + x_2 + x_3 + x_4 = 6\text{.}\)

Відповідь

1. Ви берете 3 полуниці, 1 лайм, 0 солодки, 2 чорниці і 0 жувальної гумки.
2. Це назад. Ми не хочемо, щоб зірки представляли дітей, тому що діти не ідентичні, але зірки є. Замість цього ми повинні використовувати 5 зірок (для льодяників) і використовувати 5 барів для перемикання між 6 дітьми. Наприклад,\ begin {equation*} **||***|||\ end {equation*} буде відображати результат, коли перший малюк отримує 2 льодяники, третій - 3, а решта дітей не отримує жодного.
3. Це слово AAAEOO.
4. Це не є рішенням. Кожна зірка повинна представляти одну з 6 одиниць, які складаються до 6, а смуги повинні перемикатися між різними змінними. У нас занадто багато барів. Прикладом правильної діаграми може бути\ begin {рівняння*} *|**||***,\ end {рівняння*}, що представляє це\(x_1 = 1\text{,}\)\(x_2 = 2\text{,}\)\(x_3 = 0\text{,}\) і\(x_4 = 3\text{.}\)

3

Після заняття в тренажерному залі вам поставлено завдання покласти 14 однакових dodgeballs геть в 5 засіки.

1. Скільки способів можна це зробити, якщо немає обмежень?
2. Скільки способів ви можете це зробити, якщо кожен контейнер повинен містити хоча б один dodgeball?

Відповідь

1. \({18 \choose 4}\)способи. Кожен результат може бути представлений послідовністю з 14 зірок і 4 стовпчиків.
2. \({13 \choose 4}\)способи. Спочатку покладіть по одній кульці в кожне відро. Це залишає 9 зірок і 4 бари.

4

Скільки цілочисельних розв'язків рівняння,\(x + y + z = 8\) для якого

1. \(x\text{,}\)\(y\text{,}\)і\(z\) чи все позитивно?
2. \(x\text{,}\)\(y\text{,}\)і\(z\) всі ненегативні?
3. \(x\text{,}\)\(y\text{,}\)і\(z\) все більше, ніж\(-3\text{.}\)

Відповідь

1. \({7 \choose 2}\)рішення. Після того, як кожна змінна отримує 1 зірку безкоштовно, нам залишається 5 зірок і 2 бари.
2. \({10 \choose 2}\)рішення. У нас є 8 зірок і 2 бари.
3. \({19 \choose 2}\)рішення. Ця задача еквівалентна знаходженню кількості рішень\(x' + y' + z' = 17\) де\(x'\text{,}\)\(y'\) і\(z'\) є ненегативними. (Насправді, ми дійсно просто робимо заміну. Нехай\(x = x'- 3\text{,}\)\(y = y' - 3\) і\(z = z' - 3\)).

5

Використовуючи цифри від 2 до 8, знайдіть кількість різних 5-значних чисел таких, що:

1. Цифри не можуть повторюватися і повинні бути записані у зростаючому порядку. Наприклад, 23678 - це нормально, а 32678 - ні.
2. Цифри можуть повторюватися і повинні бути записані в неспадаючому порядку. Наприклад, 24448 - це нормально, а 24484 - ні.

Відповідь

1. Є\({7 \choose 5}\) цифри. Ми просто вибираємо п'ять із семи цифр і одного разу вибрали їх у зростаючому порядку.
2. Для цього потрібні зірки і бари. Використовуйте зірку, щоб представити кожну з 5 цифр у номері, і використовуйте їх положення щодо смуг, щоб сказати, що числівник заповнює це місце. Таким чином, у нас буде 5 зірок і 6 барів, що дають\({11 \choose 6}\) цифри.

6

Граючи в Yahtzee, ви кидаєте п'ять звичайних 6-сторонніх кубиків. Скільки різних результатів можливі з одного рулону? Порядок кубиків значення не має.

7

Ваш друг каже вам, що у неї в руці 7 монет (всього копійки, нікелі, копійки і чверті). Якщо ви вгадаєте, скільки у неї кожного виду монет, вона віддасть їх вам. Якщо ви гадаєте випадковим чином, яка ймовірність того, що ви будете праві?

8

Скільки цілочисельних розв'язків\(x_1 + x_2 + x_3 + x_4 = 25\), для яких\(x_1 \ge 1\text{,}\)\(x_2 \ge 2\text{,}\)\(x_3 \ge 3\) і\(x_4 \ge 4\text{?}\)

9

Вирішіть три проблеми підрахунку нижче. Потім скажіть, чому має сенс, що всі вони мають однакову відповідь. Тобто сказати, як ви можете інтерпретувати їх як один одного.

1. Скільки способів розповсюдити 8 печива 3 дітям?
2. Скільки розв'язків у невід'ємних цілих числах є\(x+y+z = 8\text{?}\)
3. Скільки різних упаковок з 8 олівців ви можете зробити, використовуючи олівці, які бувають червоного, синього та жовтого кольорів?

10

Розглянемо функції\(f:\{1,2,3,4,5\} \to \{0,1,2,\ldots,9\}\text{.}\)

1. Скільки з цих функцій строго збільшується? Поясніть. (Функція суворо збільшується за умови, якщо\(a \lt b\text{,}\) тоді\(f(a) \lt f(b)\text{.}\))
2. Скільки функцій є незменшеними? Поясніть. (Функція не зменшується, якщо\(a \lt b\text{,}\) тоді\(f(a) \le f(b)\text{.}\))

11

Conic, ваш улюблений математичний тематичний фаст-фуд Drive-in пропонує 20 смаків, які можна додати до вашої газованої води. У вас достатньо грошей, щоб купити велику газовану воду з 4 доданими ароматизаторами. Скільки різних содових відварів можна замовити, якщо:

1. Ви відмовляєтеся від використання будь-якого з ароматів не один раз?
2. Ви відмовляєтеся від повторів, але дбаєте про порядок додавання ароматизаторів?
3. Ви дозволяєте собі кілька знімків одного і того ж аромату?
4. Ви дозволяєте собі кілька знімків, і дбаєте про порядок додавання ароматів?

Відповідь

1. \({20 \choose 4}\)газовані напої (порядок не має значення і повторення не допускаються).
2. \(P(20, 4) = 20\cdot 19\cdot 18 \cdot 17\)газовані напої (порядок питання і повторення не допускаються).
3. \({23 \choose 19}\)газовані напої (порядок не має значення і допускаються повторення; 4 зірки і 19 барів).
4. \(20^4\)газовані напої (допускаються питання порядку та повторення; 20 варіантів 4 рази).

1.6: Розширений підрахунок за допомогою PIE

1

Меню долара у вашому улюбленому ресторані швидкого харчування без оподаткування налічує 7 пунктів. У вас є 10 доларів, щоб витратити. Скільки різних страв можна купити, якщо витратити всі свої гроші і:

1. Придбайте хоча б по одному предмету.
2. Можливо, пропустіть деякі пункти.
3. Не отримуйте більше 2 будь-якого конкретного елемента.

Відповідь

\(9 \choose 6\)харчування.

Відповідь б

\(16 \choose 6\)харчування.

Відповідь c

\({16 \choose 6} - \left[{7 \choose 1}{13 \choose 6} - {7 \choose 2}{10 \choose 6} + {7 \choose 3}{7 \choose 6}\right]\)мене також. Використовуйте PIE, щоб відняти всі страви, в яких ви отримуєте 3 або більше певного елемента.

2

Після пізньої ночі вивчення математики, ви і ваші друзі вирішили піти до вашого улюбленого мексиканського ресторану швидкого харчування без податків, Burrito Chime. Ви вирішили замовити off з доларового меню, в якому є 7 пунктів. Ваша група має 16 доларів, щоб витратити (і витратить все це).

1. Скільки різних замовлень можливо? Поясніть. (Порядок, в якому розміщено замовлення, не має значення - тільки який і скільки кожного товару, який замовляється.)
2. Скільки різних замовлень можливо, якщо ви хочете отримати хоча б один з кожного товару? Поясніть.
3. Скільки різних замовлень можливо, якщо ви не отримуєте більше 4 будь-якого елемента? Поясніть.

3

Після іншого класу тренажерний зал вам доручено покласти 14 однакових dodgeballs геть в 5 засіки. Цього разу жоден смітник не може вмістити більше 6 кульок. Скільки способів можна прибирати?

Рішення

\({18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}\)Відніміть всі дистрибутиви, для яких в одному або декількох бункерах міститься 7 і більше кульок.

4

Розглянемо рівняння\(x_1 + x_2 + x_3 + x_4 = 15\text{.}\) Скільки рішень існує з\(2 \le x_i \le 5\) для всіх\(i \in \{1,2,3,4\}\text{?}\)

Рішення

Найпростіший спосіб вирішити це полягає в тому, щоб замість цього підрахувати розв'язки\(y_1 + y_2 + y_3 + y_4 = 7\) з\(0 \le y_i \le 3\text{.}\) За допомогою\(x_i = y_i+2\text{,}\) кожного рішення цього нового рівняння відповідає рівно одному розв'язку вихідного рівняння.

Тепер всі способи розподілу одиниць 7 на чотири\(y_i\) змінні можна знайти за допомогою зірок і барів, зокрема 7 зірок і 3 барів, так\({10 \choose 3}\) способи. Але це включає в себе способи того, що одній або\(y_i\) декільком змінним можна привласнити більше 3 одиниць. Отже, відніміть, використовуючи PIE. Ми отримуємо

\ begin {рівняння*} {10\ вибрати 3} - {4\ вибрати 1} {6\ вибрати 3}. \ end {рівняння*}

\({4 \choose 1}\)Підраховує кількість способів вибрати одну змінну, яка буде надмірно присвоєна,\({6 \choose 3}\) це кількість способів призначити решту 3 одиниць змінним 4. Зверніть увагу, що це остаточна відповідь, оскільки неможливо мати дві змінні, обидві отримують 4 одиниці.

5

Припустимо, ви планували дати 7 золотих зірок деяким із 13 зіркових учнів у вашому класі. Кожен учень може отримати не більше однієї зірки. Скільки способів ви можете це зробити? Використовуйте PIE, а також більш простий метод, і порівняйте свої результати.

6

Виходячи з попереднього питання, дайте комбінаторне підтвердження особи:

\ begin {рівняння*} {n\ вибрати k} = {n+k-1\ вибрати k} -\ sum_ {j=1} ^n (-1) ^ {j+1} {n\ вибрати j} {n+k- (2j+1)\ вибрати k}. \ end {рівняння*}

7

Проілюструйте, як працює підрахунок порушень, написавши всі перестановки\(\{1,2,3,4\}\) та перекреслення тих, які не є порушеннями. Слідкуйте за перестановками, які ви перекреслюєте не один раз, використовуючи PIE.

Рішення

9 порушень: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

8

Скільки перестановок\(\{1,2,3,4,5\}\) залишають рівно 1 елемент фіксованим?

Рішення

Спочатку виберіть один з п'яти елементів, які будуть закріплені. Для кожного такого вибору відваріть залишилися чотири, використовуючи стандартну вдосконалену формулу PIE. Отримуємо\({5 \choose 1}\left( 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4} 0!\right] \right)\) перестановки.

9

Десять дам певного віку скидають свої червоні капелюхи на перевірці капелюхів музею. Коли вони йдуть, секретар перевірки капелюхів дає капелюхи назад випадковим чином. Скільки способів можуть рівно шість дам отримати власну шапку (а інші чотири ні)? Поясніть.

10

Грінч пробирається в кімнату з 6 різдвяними подарунками 6 різдвяним людям. Він переходить до перемикання іменів-ярликів на презенти. Скільки способів він міг це зробити, якщо:

1. Жоден подарунок не дозволено в кінцевому підсумку зі своїм оригінальним лейблом? Поясніть, що являє собою кожен термін у вашій відповіді.
2. Точно 2 презенти зберігають свої оригінальні етикетки? Поясніть.
3. Рівно 5 подарунків зберігають свої оригінальні етикетки? Поясніть.

11

Розглянемо функції\(f: \{1,2,3,4\} \to \{a,b,c,d,e,f\}\text{.}\) Скільки функцій мають властивість, що\(f(1) \ne a\)\(f(2) \ne b\text{,}\) або обидва?

Рішення

Є\(5 \cdot 6^3\) функції, для яких\(f(1) \ne a\) і інші\(5 \cdot 6^3\) функції, для яких\(f(2) \ne b\text{.}\) є\(5^2 \cdot 6^2\) функції, для яких обидва\(f(1) \ne a\) і\(f(2) \ne b\text{.}\) так загальна кількість функцій, для яких\(f(1) \ne a\) або\(f(2) \ne b\) або обох є

\ begin {рівняння*} 5\ cdot 6^3 + 5\ cdot 6^3 - 5^2\ cdot 6^2 = 1260. \ end {рівняння*}

12

Розглянемо\(A\)\(B\) множини\(|A| = 10\) і з і\(|B| = 5\text{.}\) Скільки функцій\(f: A \to B\) є суб'єктивними?

Рішення

\(5^{10} - \left[{5 \choose 1}4^{10} - {5 \choose 2}3^{10} + {5 \choose 3}2^{10} - {5 \choose 4}1^{10}\right]\)функції. \(5^{10}\)Це всі функції від\(A\) до\(B\text{.}\) Ми віднімаємо ті, які не є суб'єктивними. Виберіть один з п'яти елементів,\(B\) щоб не мати в діапазоні (\({5 \choose 1}\)способами) і порахуйте всі ці функції (\(4^{10}\)). Але це переважає функції, де два елементи з\(B\) виключаються з діапазону, тому відніміть їх. І так далі, використовуючи PIE.

13

Нехай\(A = \{1,2,3,4,5\}\text{.}\) Скільки ін'єкційних функцій\(f:A \to A\) мають властивість, що для кожної\(x \in A\text{,}\)\(f(x) \ne x\text{?}\)

14

\(d_n\)Дозволяти кількість порушень\(n\) об'єктів. Наприклад, використовуючи прийоми цього розділу, знаходимо

\ begin {рівняння*} d_3 = 3! -\ left ({3\ вибрати 1} 2! - {3\ виберіть 2} 1! + {3\ виберіть 3} 0! \ праворуч)\ end {рівняння*}

Ми можемо використовувати формулу для\({n \choose k}\) того, щоб записати все це з точки зору факторіалів. Після спрощення, бо\(d_3\) ми отримаємо

\ begin {рівняння*} d_3 = 3! \ left (1 -\ гідророзриву {1} {1} +\ гідророзриву {1} {2} -\ frac {1} {6}\ праворуч)\ end {рівняння*}

Узагальніть це, щоб знайти приємнішу формулу для\(d_n\text{.}\) бонусу: Для великих\(n\text{,}\) приблизно яка частка всіх перестановок є порушеннями? Використовуйте свої знання про серії Тейлора з обчислення.