Правила комбінаторики

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

Приклад 1.1. Підрахуємо кількість двозначних чисел, які можна скласти з цифр 1, 2, 3. На перше місце цифру можна вибрати трьома способами, після чого на друге місце - теж трьома способами. Значить, все таких чисел за правилом множення буде 3 · 3 = 9. Можна перевірити відповідь, виписавши один за одним всі ці числа в порядку зростання:

У наведеному прикладі вибір другої цифри ніяк не пов'язаний з вибором першої. Але це далеко не завжди так.

Приклад 1.2. Підрахуємо кількість двозначних чисел, які можна скласти з цифр 1, 2, 3 так, щоб всі цифри були різні. На перше місце цифру можна вибрати трьома способами, після чого на друге місце - тільки двома способами (ту цифру, яка на першому місці, використовувати вже не можна). Значить, все таких чисел за правилом множення буде 3 · 2 = 6. Ось ці числа:

Тепер в кожній з трьох груп тільки по два елементи.

У даних прикладах дві принципово різні схеми вибору елементів:

а) без повернення (повторень) елементів (це означає, що відбираються або відразу все елементів, або послідовно по одному елементу, причому кожен відібраний елемент виключається з початкової множини);

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

Але бувають завдання, в яких після вибору одного з m об'єктів в якості першого елемента комбінації не можна однозначно сказати, скількома способами можна вибрати другий елемент - це залежить від того, який саме об'єкт був обраний першим. Розглянемо таку ситуацію на прикладі.

Приклад 1.3. Підрахуємо кількість двозначних чисел, які можна скласти з цифр 1, 2, 3 так, щоб перша цифра була меншою від другої. На перше місце цифру можна вибрати трьома способами, а ось на друге місце після цього:

- двома способами, якщо першою цифрою була обрана 1;

- одним способом, якщо 2;

- нулем способів, якщо 3.

Доводиться застосовувати комбинаторное правило складання: розбити всі комбінації на непересічні класи, підрахувати кількість комбінацій в кожному класі (наприклад, за правилом множення), а потім скласти ці кількості.

У попередньому прикладі кількість комбінацій одно: 2 + 1 = 3.

п -факторіал - твір всіх натуральних чисел від 1 до п включно.

Слід зазначити, що 0! = 1.

Перестановки - комбінації з n елементів, які відрізняються один від одного тільки порядком елементів. Загальна кількість перестановок з n елементів позначається і одно:

Приклад 1.5. З букв A, B, C можна скласти наступні перестановки:

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

Приклад 1.6. Скількома способами можна розставити на книжковій полиці зібрання творів Діккенса, що включає 30 томів?

Кожен такий спосіб - це перестановка з 30 елементів. Всього таких перестановок буде

30! = 265 252859 812191058636308 480 000000.

Число перестановок з повтореннями можна знайти застосувавши формулу:

Розміщення - комбінації з n елементів по m елементів, які відрізняються один від одного або самими елементами або їх порядком.

де n - числи всіх наявних елементів,

m - число елементів до кожної комбінації.

При цьому вважають, що. Число розміщень можна обчислити за формулами:

Приклад 1.7. Нехай є чотири літери А, В, С, D. Склавши всі комбінації тільки з двох букв, отримаємо: АВ, АС, АD,

Всі отримані комбінації відрізняються або буквами, або порядком (комбінації ВА і АВ вважаються різними). Коротко це можна записати так:

Приклад 1.8. На книжкову полицю влазить тільки 8 будь-яких томів з 30-томного зібрання Діккенса. Скількома способами можна заповнити цими томами таку полицю?

Кожен спосіб - це розміщення з 30 елементів по 8. Всього таких розміщень буде

Число розміщень з повтореннями одно:

Сполучення - всі можливі комбінації з n елементів по m елементів, які відрізняються один від одного, принаймні хоча б одним елементом.

Сполучення позначаються і знаходяться за формулою:

Приклад 1.9. З чотирьох різних букв А, В, С, D можна скласти наступні комбінації, що відрізняються один від одного хоча б одним елементом: АВ, АС, АD, ВС, ВD, СD.

Значить число поєднань з чотирьох елементів по два дорівнює 6.

Це можна знайти і за вищенаведеною формулою:

Для поєднань справедливі рівності:

Число перестановок, розміщень і сполучень пов'язані рівністю:

1. У чому сутність комбінаторики?

2. Сформулюйте правило додавання.

3. Сформулюйте правило множення.

4. У чому відмінність вибору елементів з поверненню і без поверненню?

5. Що називають перестановками?

6. За якою формулою обчислюють число перестановок з п різних елементів?

7. За якою формулою обчислюють число перестановок з п різних елементів з повтореннями?

8. Що називають розміщеннями?

9. За якою формулою обчислюють число розміщень з п різних елементів по m елементів?

10. Що називають поєднаннями?

11. За якою формулою обчислюють число поєднань з елементів п різних елементів по m елементів?

12. Яким рівністю пов'язані числа перестановок, розміщень і сполучень?

13. Чим відрізняються поєднання від розміщень? Що і у скільки разів більше?