Тема 2. ЕЛЕМЕНТИ КОМБІНАТОРИКИ
Цілі і завдання вивчення теми
У даній темі розглядаються основи комбінаторики і алгоритми породження комбінаторних об'єктів.
Комбінаторика - один з розділів дискретної математики, який придбав велике значення в зв'язку з використанням його в теорії ймовірностей, математичної логіки, теорії чисел, обчислювальній техніці, кібернетиці.
Наведемо приклад найпростішої комбінаторної задачі. Нехай з міста А до міста В можна добиратися пароплавом, поїздом, автобусом, літаком; з міста В до міста С - пароплавом і автобусом. Скількома способами можна здійснити подорож за маршрутом А - В - С?
Рішення. Очевидно, число різних шляхів з А до С дорівнює 4 × 2 = 8, так як, вибравши один з чотирьох можливих способів подорожі від А до В, маємо два можливих способу подорожі від В до С.
Виходячи з цих міркувань, сформулюємо основне правило комбінаторики - правило твори.
Правило твори. Якщо деякий вибір A можна здійснити m способами, а для кожного з цих способів деякий інший вибір B можна здійснити n способами, то вибір "A і B" в зазначеному порядку можна здійснити m × n способами.
Це правило можна узагальнити наступним чином.
Нехай потрібно виконати одну за іншою k дій. Якщо перша дія виконати n1 способами, друга дія - n2 способами, третя дія - n3 способами і так до k -го дії, яке можна виконати nk способами, то всі k дій можуть бути виконані n1 × n2 × n3 × ... × nk способами.
При підрахунку числа різних комбінацій використовується також правило суми.
Правило суми. Якщо деякий вибір A можна здійснити m способами, а вибір B іншими n способами, то вибір "або A. або B" можна здійснити m + n способами.
Правило суми також може бути узагальнене на довільне число дій.
У разд.1.1.1 було дано поняття безлічі. Кінцеве безліч S будемо ставити списком його елементів: S = s1, s2, ..., sn>, де s1, s2, ..., sn - елементи S (обов'язково різні).
Введемо поняття мультимножини. Мультімножество є об'єднання не обов'язково різних об'єктів. Його можна вважати великою кількістю, в якому кожному елементу поставлено у відповідність натуральне число, зване кратністю.
Кінцеве мультімножество S будемо записувати в наступному вигляді:
Тут все si різні і ki - кратність елемента si. Тоді потужність S дорівнює.
Тепер розглянемо деякі з комбінаторних об'єктів.
Підмножини. Безліч M називається підмножиною множини S (позначення М ÌS або S ÉМ; читається М входить в S, S містить М) тоді і тільки тоді, коли будь-який елемент безлічі М належить множині S.
Теорема. Число підмножин n -елементного безлічі S дорівнює 2 n.
Доведення. Поставимо у відповідність кожному підмножині M безлічі S двійковий набір довжини n за таким правилом: si ÎМ. якщо і тільки якщо i -й розряд дорівнює одиниці. Число двійкових наборів довжини n. згідно з правилом твори, дорівнює 2 × 2 × ... × 2 = 2 n. Отже, число всіх підмножин n -елементного безлічі дорівнює 2 n.
Перестановки. Перестановкою називається розташування елементів безлічі в певному порядку.
Теорема. Число перестановок n -елементного безлічі S. тобто число способів його упорядкування виражається формулою Pn = n!.
Символом n. (Читається n -факторіал) позначається твір натуральних чисел від 1 до n: n! = 1 × 2 ×. × n. Вважається, що 0! = 1.
Доведення. Будемо послідовно вибирати елементи безлічі S і розташовувати їх в певному порядку на n місцях. На перше місце можна поставити будь-який з n елементів. Після того, як заповнене перше місце, на друге місце можна поставити будь-який з решти n -1 елементів і т.д. Тоді за правилом твори все n місць можна заповнити n × (п -1) × (п -2) ×. × 2 × 1 = n. способами. Следо-вательно, n -елементное безліч можна впорядкувати n! Способами.
Розміщення. Впорядковані k -елементние підмножини безлічі з n елементів називаються розміщеннями з n елементів по k.
Теорема. Число розміщень з n по k визначається формулою:
.
Доведення. Будемо послідовно вибирати k-елементів з n -елементного безлічі, і розташовувати їх в певному порядку на k місцях. На перше місце можна поставити будь-який з n елементів, потім на друге - будь-який з n -1оставшіхся і т.д. За правилом вироб-ведення маємо
.
Сполучення. Поєднанням з n елементів по k називається k -елементное підмножина безлічі з n елементів.
Теорема. Число сполучень з n елементів по k виражається сліду-нього формулою:
.
Доведення. З n -елементного безлічі можна утворити різних упорядкованих k -елементних підмножин. Кожне k -елементное підмножина може бути впорядковане Рk способами. Тоді число поєднань з n по k - число невпорядкованих k -елементних підмножин n -елементного безлічі дорівнюватиме
.
Для числа поєднання справедливі рівності
,
,
.
Остання властивість випливає з теореми про кількість підмножин кінцевого безлічі (поясніть чому).
Перестановки з повтореннями. Перестановкою з повтореннями називається розташування елементів мультимножини в певному порядку.
Теорема. Число перестановок з повтореннями для мультимножини виражається формулою
,
Доказ 1. Розглянемо одну перестановку мультимножини і замінимо в ній всі однакові елементи різними. Тоді, число різних перестановок, які можна скласти з даної перестановки, так само k1! × k2! × ... × km!. Проробивши це для кожної перестановки, отримаємо n. перестановок. отже,
Число Cn (k1, k2, ..., km) називається поліноміальним коефіцієнтом. Наведемо ще один доказ даної теореми.
Доказ 2. Для упорядкування мультимножини необхідно з n місць вибрати k1 місць для елемента s1, що можна зробити способами, потім з n -k1 залишилися місць вибрати k2 місць для елемента s2. що можна зробити способами і т.д. Тоді число способів упорядкування мультимножини S за правилом твори одно (нагадавши, що 0! = 1)
.
Сполучення з повтореннями. Поєднаннями з m елементів по n елементів з повтореннями називаються групи, які містять n елементів, причому кожна елемент належить до одного з m типів.
Приклад. З трьох елементів (m = 3) a. b. c можна скласти такі поєднання по два з повтореннями: aа. ab. ас. bb. bc. cc.
Теорема. Число різних сполучень з m елементів по n з повтореннями одно
.
Доведення. Кожне поєднання повністю визначається, якщо вказати, скільки елементів кожного з m типів в нього входить. Поставимо у відповідність кожному поєднанню послідовність нулів і одиниць, складену за таким правилом: ставимо поспіль стільки одиниць, скільки елементів першого типу входить в поєднання, далі ставимо нуль, і після нього пишемо стільки одиниць, скільки елементів другого типу містить це поєднання і т.д . Наприклад, написаним вище сполученням з трьох букв по дві відповідатимуть такі послідовності:
1100, 1010, 1001, 0110, 0101, 0011.
Таким чином, кожному поєднанню з m по n відповідає послідовність з n одиниць і m -1 нулів. Число таких послідовностей дорівнює числу способів, якими можна вибрати m -1 місць для нулів з n + m -1 загального числа місць (), або те ж саме числу способів вибору n місць для одиниць з n + m -1мест (). Рівність випливає з рівності.
Композиції та розбиття. Наприклад, потрібно породження розбиття позитивного числа n в послідовність невід'ємних цілих чисел p1, p2, ..., pk>, так що p1 + p2 + ... + pk = n причому на рi можуть накладатися різні обмеження.
Якщо порядок чисел рi важливий, то (p1, p2, ..., pk) називається композицією n. Пошук композицій ведеться з обмеженням рi> 0.
Якщо k фіксоване, то такі композиції називаються композиціями n з k частин. При їх пошуку обмеження рi> 0 може зніматися, тобто дозволяється рi = 0.
Пояснимо різницю між композиціями, композиціями з k частин і розбиття на наступному прикладі:
композиції: (3), (1,2), (2,1), (1,1,1),
композиції з двох частин (рi> 0): (1,2), (2,1),
композиції з двох частин (рi ³0): (0,3), (1,2), (2,1), (3,0),
Теорема. Число композицій n дорівнює 2 n -1.
Доведення. Розділимо відрізок довжини n на n відрізків одиничної довжини з допомогою (n -1) точки. Тоді композиції n взаємно однозначно відповідає позначка деяких з точок поділу. Елемен-тами композиції в цьому випадку буде відстань між суміжними точками. Наприклад, композиція (2,2,1), n = 5 представлена на рис.2.1.
Отже, кожна композиція n відповідає способу вибору підмножини з (n -1) точок. Тобто число композицій n дорівнює 2 n -1.
Теорема. Число композицій n з k частин з обмеженням рi> 0 дорівнює.
Доведення. Уявімо композицію також як при доказі попередньої теореми. Кожна композиція n з k частин (рi> 0) відповідає способу вибору (k -1) - елементного підмножини точок з n -1 точок. Тобто число таких композицій одно.
Теорема. Число композицій n з k частин, якщо pi ³0 одно.
Доведення. Кожній композиції n з k частин при рi ³0 взаємно однозначно відповідає двійковий набір, такий, що перший доданок дорівнює числу одиниць, що стоять перед першим нулем в наборі, друге - числу одиниць, що стоять перед першим і другим нулями, і т.д. Приклад такого уявлення композиції n = 4, k = 3 наведено в табл.2.1.
Довжина набору дорівнює n + k -1, число нулів одно k -1, отже, число наборів (шуканих композицій) дорівнює числу способів вибору k -1 місць для нулів з n + k -1 місць () або те ж саме числу способів вибору n місць для одиниць з n + k -1мест ().
Ілюстрація до теоремі про кількість композицій n з k частин