Основні формули комбінаторики

В даному розділі ми займемося підрахунком числа «шансів». Про число шансів кажуть, коли можливо кілька результатів будь-якого дії (витяг карти з колоди, підкидання кубика або монетки). число шансів # 151; це число способів виконати цю дію або, що те ж саме, число можливих результатів цієї дії.

Нехай одну дію можна виконати п'ятьма способами, а інше # 151; двома. Яким числом способів можна виконати пару цих дій?

Теорема 1. Нехай безліч складається з елементів:, а безліч # 151; з елементів:. Тоді можна утворити рівно пар, взявши перший елемент з безлічі, а другий # 151; з безлічі.

Зауваження 1. Можна сформулювати твердження теореми 1 так: якщо перший елемент можна вибрати способами, а другий елемент # 151; способами, то пару елементів можна вибрати способами.

Доведення. З елементом ми можемо утворити пар:. Стільки ж пар можна скласти з елементом, стільки ж # 151; з елементом і з будь-яким іншим з елементів множини. Тобто всього можливо пар, в яких перший елемент вибраний з безлічі, а другий # 151; з безлічі.

Вправа 1. За допомогою теореми 1 довести, що: а) при підкиданні трьох монет можливо 2 · 2 · 2 = 8 різних результатів; б) кидаючи двічі гральну кістку, отримаємо 6 · 6 = 36 різних результатів; в) тризначних чисел буває 9 · 10 · 10 = 900; г) тризначних чисел, всі цифри яких різні, існує 9 · 9 · 8; д) парних тризначних чисел можливо 9 · 10 · 5.

Є урна (ящик), що містить пронумерованих об'єктів (куль). Ми вибираємо з цієї урни куль; результатом вибору є набір з куль. Нас цікавить, скількома способами можна вибрати куль з, або скільки різних результатів може вийти. На це питання не можна дати однозначну відповідь, поки ми не визначимося: а) з тим, як організований вибір (чи можна кулі повертати в урну), і б) з тим, що розуміється під різними результатами вибору.

Розглянемо наступні можливі способи вибору.

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

Домовимося, які результати вибору (набори з номерів куль) ми будемо вважати різними. Є рівно дві можливості.

1. Вибір з урахуванням порядку: два набору номерів куль вважаються різними, якщо вони відрізняються складом або порядком номерів. Так, при виборі трьох куль з урни, що містить 5 куль, набори (1, 5, 2), (2, 5, 1) і (4, 4, 5) різні, якщо порядок враховується. 2. Вибір без урахування порядку. два набору номерів куль вважаються різними, якщо вони відрізняються складом. Набори, що відрізняються лише порядком проходження номерів, вважаються однаковими.

Так, набори (1, 5, 2) і (2, 5, 1) не розрізняються і утворюють один і той же результат вибору, якщо порядок не враховується.

Підрахуємо, скільки можливо різних результатів для кожної з чотирьох схем вибору (вибір з поверненням або без, і в кожному з цих випадків # 151; з урахуванням порядку або без).

Вправа 2. Перерахувати всі можливі результати в кожній з чотирьох схем при виборі двох куль з чотирьох. Наприклад, при виборі з поверненням і без урахування порядку: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).

Теорема 2. Загальна кількість різних наборів при виборі елементів з без повернення і з урахуванням порядку дорівнює

і називається числом розміщень з елементів по елементів.

Доведення. Перший шар можна вибрати способами, його номер # 151; будь-який з можливих. При будь-якому виборі першої кулі є спосіб вибрати друга куля. По теоремі 1. число можливих пар

одно. Для кожної такої пари є способи вибрати третій шар. По теоремі 1. число можливих трійок

дорівнює добутку числа пар і числа способів вибору третього кулі, тобто одно. Продовжуючи міркування, отримаємо, що загальне число можливих наборів з куль одно. У цьому творі сомножителей останній множник є число способів вибору -го кулі, коли вже обрані попередні.

Слідство 1. Якщо в безлічі елементів, то існує рівно перестановок цих елементів.

Доведення. перестановка # 151; результат вибору без повернення і з урахуванням порядку елементів з. Тому загальне число перестановок одно

Вправа 3. Знайти, скільки всього можливо різних результатів в наступних експериментах: а) з колоди в 36 карт без повернення, з урахуванням порядку виймають три карти; б) Вася, Петя, Оля і Лена займають якісь чотири з десяти місць в класі; в) з українського алфавіту вибирають чотири різні літери і складають слово; г) з різних цифр, що не рівних нулю, складається тризначне число.

Теорема 3. Загальна кількість різних наборів при виборі елементів з без повернення і без урахування порядку дорівнює

і називається числом сполучень з елементів по елементів.

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

Вправа 4. Знайти, скільки всього можливо різних результатів в наступних експериментах: а) з колоди в 36 карт без повернення, без урахування порядку виймають три карти; б) з українського алфавіту викидають чотири літери.

Теорема 4. Загальна кількість різних наборів при виборі елементів з з поверненням і з урахуванням порядку дорівнює.

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

Вправа 5. Визначити, скільки всього можливо різних результатів в наступних експериментах: а) з колоди в 36 карт тягнуть три рази карту з урахуванням порядку і з поверненням; б) п'ятизначне число складається з одних непарних цифр; в) мавпа надрукувала на машинці слово з десяти букв.

Розглянемо урну з двома пронумерованими кульками та перерахуємо результати вибору двох кульок з цієї урни при виборі з поверненням.

з урахуванням порядку

без урахування порядку

Бачимо, що в схемі «без урахування порядку» вийшло три різних результату, на відміну від чотирьох результатів в схемі «з урахуванням порядку». Зауважимо також, що ніяким розподілом на «число яких-небудь перестановок», яке допомогло позбутися від обліку порядку при виборі без повернення, число 3 з числа 4 отримати не вдасться.

Теорема 5. Загальна кількість різних наборів при виборі елементів з з поверненням і без урахування порядку дорівнює

Вправа 6. Перевірити, що при і виходить рівно 3.

Доведення. Розглянемо докладно, чим відрізняються один від одного два різні результати такої схеми вибору. Нам не важливий порядок номерів, тобто ми враховуємо тільки, скільки разів в нашому наборі з номерів куль з'явився кожен номер. Тому результат вибору можна уявити набором чисел, в якому # 151; число появ кулі номер в наборі, і. Числа приймають значення з. Два результату вибору в схемі вибору з поверненням і без урахування порядку розрізняються, якщо відповідні їм набори не збігаються (порядок проходження елементів враховується).

Уявімо собі інший експеримент, який має точно такі ж результати, і порахуємо їх кількість. Є ящиків, в яких розміщуються куль. Нас цікавить тільки число куль в кожному ящику. Результатом експерименту знову є набір чисел, де дорівнює числу куль в ящику з номером, і. Числа приймають натуральні значення або дорівнюють нулю.

А тепер покажемо результат такого розміщення у вигляді схеми, в якій вертикальні лінії позначають перегородки між ящиками, а точки # 151; що знаходяться в ящиках кулі:

Ми бачимо результат розміщення дев'яти куль по семи скриньок. Перший ящик містить три кулі, другої та шостої ящики порожні, третій ящик містить один шар, в четвертому і п'ятому ящиках лежить по дві кулі. Перекладемо один шар з першого ящика в другій і зобразимо таким же чином ще два результату розміщення:

Бачимо, що всі розміщення можна отримати, змінюючи між собою кулі і перегородки, або розставляючи куль на місцях. Число виходить так: у ящиків є рівно перегородка, вважаючи крайні, але з них переміщати можна лише внутрішню перегородку. Таким чином, є місць, які можна зайняти кулями або внутрішніми перегородками. Перебравши всі можливі способи розставити куль на цих місцях (заповнюючи решту місць перегородками), переберемо всі потрібні розміщення.

Залишилося помітити, що способів розставити куль на місцях існує

Саме стільки є способів вибрати з номерів місць номерів місць для куль.

Вправа 7. а) Знайти кількість способів розкласти натуральне число в суму цілих невід'ємних доданків, якщо важливий порядок проходження цих доданків. б) Знайти число різних похідних порядку функції змінних. в) Знайти число можливих результатів підкидання двох гральних кісток, якщо кістки вважаються невиразними. Те ж саме для трьох гральних кісток.