Загальні правила комбінаторики

Розглянемо ті узагальнення, які можна провести на основі задач, розв’язаних у §2. Зокрема, виділимо два правила, за допомогою яких розв’язується більшість комбінаторних задач — правила суми і добутку.

Уявімо собі, що на поличці є n різних книг. Довільним способом із цієї полички вибирають книгу. Зрозуміло, що є n різних можливостей провести цей вибір. Нехай тепер ці книги перенесли і розклали на дві полички: на одну поклали k книг, а на іншу — m. Очевидно, що k + m = n. Якби ми знову захотіли вибрати одну книгу, то існувало б k можливостей вибрати її з першої полички та m можливостей — з другої. Тому кількість способів вибрати одну книгу з першої або з другої полички дорівнює n, оскільки k + m = n.

Отже, якщо деякий об’єкт А можна вибрати k способами, а об’єкт В — m способами, то вибрати один з об’єктів А або В можна k + m способами.Це і є так зване правило суми.

До другого правила ми прийдемо, розв’язуючи таку задачу: З міста А до міста В можна дістатися шістьма маршрутами, а з міста В до міста С — трьома. Скільки можна утворити різних маршрутів, аби дістатися з міста А до міста С, відвідавши при цьому місто В?

Якщо проаналізувати зображену схему, то бачимо, що існує 18 різних маршрутів з А в С. Справді, з А до В можна дістатися, наприклад, першим маршрутом, а далі продовжити поїздку одним з трьох маршрутів І, II або III. Маршрут стане іншим, якщо з А до В ми поїдемо другим маршрутом, а потім виберемо або І, або II, або III маршрут. І т. д.

Узагальнюючи розв’язання цієї задачі, маємо:

Якщо об’єкт А можна вибрати m способами, а після цього другий об’єкт В можна вибрати k способами (незалежно від того, як вибрали об’єкт А), то пару об’єктів А і В можна вибрати m× k способами.

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

Основні поняття комбінаторики

Перестановки

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

Така проблема виникає, наприклад, коли необхідно упорядкувати список учасників змагань, або серед поданих заявок встановити черговість їхнього розгляду. Ученого, який розшифровує анаграму з декількох букв, цікавить питання, скільки змістовних фраз можна скласти із цих букв. Наприклад, з п’яти букв а, к, н, о, р можна скласти такі змістовні слова, як ранок, коран та норка. З аналогічними задачами зустрічаються і тоді, коли необхідно відімкнути замок сейфа, автоматичної камери зберігання тощо, код до яких загубився. Замок відмикається лише тоді, коли набрати певне «таємне слово», яке не обов’язково, має бути змістовним.

Будь-які упорядковані послідовності усіх елементів скінченної множини прийнято називати перестановками.Кількість можливих перестановок з п елементів позначають символом P_n (читається «пе з ен»).

Зрозуміло, що один предмет можна упорядкувати лише одним способом, а два предмети — двома способами. Неважко безпосередньо переконатися, що існує лише шість способів, якими можна упорядкувати три букви А, Б, В. Ось вони:

АБВ БАВ ВАБ

АВБ БВА ВБА.

Тому можна записати, що Р₁ = 1, Р₂ = 2, а Р₃ = 6.

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

Усі ці чотириелементні перестановки будуть різними, бо ми у різних триелементних перестановках вписували букву Г на кожне з можливих чотирьох місць. Тому Р₄ = 24.

Цей простий аналіз підводить нас до такої так званої рекурентної формули (recurentis в перекладі з латини означає «повертаючий назад»):

P_n = n × P_n–1 .

Справді, аби знайти всі можливі перестановки у множині з n елементів, потрібно у кожну перестановку, складену з перших n – 1 елементів, помістити останній n-й елемент відповідно на перше, друге, третє і т. д. місце. Оскільки різних місць буде n, то, отже, записана формула є правильною.

З цієї рекурентної формули, користуючись методом математичної індукції, можна вивести таке твердження:

Теорема 1. Число Р_n усіх перестановок з n елементів дорівнює добутку послідовних натуральних чисел від 1 до n включно, тобто:

Р_n = 1 × 2 × 3 ×…× (n – 1) × n = n!.

(При символом n! (читається «ен факторіал» — від англійського слова factor, що означає «множник») позначають добуток 1 × 2 × 3 ×…× (n – 1) × n усіх натуральних чисел від 1 до n.)

■ Справді, як уже зазначено вище, P₁ = 1, Р₂ = 1 · 2 = 2!.

Припустимо, що P_{n – 1} = (n – 1)!. Тоді, відповідно до рекурентної формулою P_n = n×P_{n – 1}, маємо: P_n = n × ((1 – 2 – 3 ×…× (n – 1)) = n!. ■

Надалі для зручності записів будемо вважати, що порожню множину теж можна упорядкувати — одним способом і що, отже, Р₀ = 0! = 1.

Наведемо перші значення чисел n!, які часто трапляються у практичних задачах:

Теорему 1 можна довести інакше, а саме, скориставшись правилом множення. Нехай маємо множину, у якій є n елементів. Перший елемент перестановки можна вибрати n способами, а другий — вже тільки (n – 1) способом. Тоді очевидно, що перші два елементи перестановки можна вибрати n (n – 1) способами. Оскільки для вибору третього елемента існує лише n – 2 можливості, то для вибору перших трьох елементів перестановки маємо n (n – 1)(n – 2) способів. Продовжуючи ці міркування й далі, з’ясуємо, що для вибору передостаннього елемента залишиться лише два способи, а останній елементи вибирається тоді лише одним способом. Тому:

P_n = n × (n – 1) · (n – 2) ×… × 2 × 1 = n!.

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

■ Шукана кількість шестицифрових чисел дорівнює числу всіх перестановок із шести елементів, тобто — числу Р₆ = 6! = 720. ■

Розміщення

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

У деяких задачах ставиться завдання визначити, скільки може існувати упорядкованих підмножин заданої множини. Якщо, наприклад, потрібно з’я-сувати, скількома способами у кооперативі з 25 членів можна обрати голову кооперативу, його заступника і скарбника, то мова йде про вибір упорядкованої трійки членів кооперативу.