Розділ 5. КОМБІНАТОРИКА

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

Нехай деяке агентство нерухомості має у своєму розпорядженні базу даних із n записів, причому кожний запис містить одну пропозицію (що є) і один запит (що потрібно) щодо об'єктів нерухомості. Потрібно знайти всі такі пари записів, в яких пропозиція першого запису збігається з запитом другого, і, навпаки, пропозиція другого запису збігається з запитом першого. На побутовій мові це називається добором варіантів обміну. Припустимо, що база даних дозволяє перевірити варіант за одну мілісекунду. Неважко зміркувати, що при «лобовому» алгоритмі пошуку варіантів (кожний запис зрівнюється з кожним) буде потрібно n(n-1)/2 порівнянь. Якщо n=100, то все в порядку - відповідь буде отримана за 4,95 секунди. Але якщо n = 100 000 (більш реальний випадок), то відповідь буде отримана за 4 999 950 секунд, що складає майже 1389 годин і навряд чи може вважатися прийнятною. Зверніть увагу, що ми оцінили тільки трудомісткість добору прямих варіантів, а існують ще варіанти, коли кількість учасників угоди більше двох...

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

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

5.1. Комбінаторні конфігурації

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

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

1. Дано n предметів. Їх потрібно розмістити по m ящиках так, щоб виконувалися задані обмеження. Скількома засобами це можна зробити?

2. Роздивимося множину функцій

F:X→Y, де |X|=n, |Y|=m, X={1,... ,n}.

Не обмежуючи спільності, можна вважати, що

Y={1, ... , m}, F=F(1), ... , F(n), 1≤ F(i)≤ m.

Скільки існує функцій F, що задовольняють заданим обмеженням?

5.1.1. Розміщення

Кількість усіх функцій (при відсутності обмежень), або кількість всіх можливих способів розмістити n предметів по m ящиках, називається кількістю розміщень і позначається U(m,n)

Доказом є те, що кожний із n предметів можна розмістити m способами.

Розглянемо приклад. При грі в кості кидаються дві кості й очки, що випали на верхніх гранях, складаються. Яка ймовірність викинути 12 очок? Кожний можливий вихід відповідає функції F:{1,2} → {1, 2, 3, 4, 5, 6} (аргумент - номер кості, результат - очко на верхній грані).

Таким чином, усього можливо різноманітних виходів. З них тільки один (6+6) дає дванадцять очок. Ймовірність 1/36.

5.1.2. Розміщення без повторень

Число ин'єктивних функцій або кількісь всіх можливих способів розмістити n предметів по m ящиках не більш ніж по одному в ящик, називається кількістю розміщень без повторень і позначається A(m, n) або (m)_n

Розглянемо доказ. Ящик для першого предмета можна вибрати m способами, для іншого - m-1 способами і т.д. таким чином

.

За визначенням вважають, що A(m,n) : =0 при n>m і A(m,0) : =1.

Приклад. У деяких видах спортивних змагань виходом є визначення учасників, що посіли перше, друге і третє місця. Скільки можливо різноманітних виходів, якщо в змаганні беруть участь n учасників? Кожний можливий вихід відповідає функції F:{1, 2, 3} → {1...n} (аргумент - номер призового місця, результат - номер учасника). Таким чином, усього можливо A(n,3) = n (n-1) (n-2) різноманітних виходів.

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

Кількість взаємно однозначних функцій, або кількість перестановок n предметів, позначається Р(n)

P(n) = n!

Доведення цієї формули має вигляд

P(n) = A(n,n) = n· (n-1) ···· (n-n+1) = n· (n-1) .... 1 = n!

Як приклад розглянемо послідовність  = ( ­­­) непустих підмножин множини Е ( ), що називається ланцюжком в Е, якщо



Ланцюжок  називається повним ланцюжком в Е, якщо . Скільки існує повних ланцюжків? Очевидно, що в повному ланцюжку кожна така підмножина E_i+1 отримана з попередньої підмножини E_i додаванням рівно одного елемента з Е і, таким чином,_1 _ _m   m. Отже, повний ланцюжок визначається порядком, в якому елементи Е додаються для утворення чергового елемента повного ланцюжка. Звідси кількість повних ланцюжків - це кількість перестановок елементів множини Е, рівне m!