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

Розглянемо ті узагальнення, які можна провести на основі задач, розв’язаних у §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 способами.

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

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

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

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

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

Будь-які упорядковані послідовності усіх елементів скінченної множини прийнято називати перестановками. Кількість можливих перестановок зпелементів позначають символом 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!, які часто трапляються у практичних задачах:

0! 1	3! 6	6! 720	9! 362880
1! 1	4! 24	7! 5040	10! 3628800
2! 2	5! 120	8! 40320	11! 39916800.

Теорему 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.■