- •Розділ 1. Множини та відношення.
- •1.1. Основні поняття теорії множин.
- •1.2. Операції над множинами. Тотожні перетворення множин.
- •1.3. Відношення та відображення.
- •Розділ 2. Елементи комбінаторики.
- •2.1. Місце комбінаторики в математиці. Правила суми та добутку.
- •2.2. Розміщення та сполучення.
- •2.3. Біном н’ютона. Властивості біноміальної формули. Поліноміальна формула.
- •2.5. Композиції та розбиття. Досконалі розбиття.
- •2.4. Формула включень та виключень.
- •2.6. Рекурентні співвідношення.
- •Розділ 3. Основи теорії графів. Деякі алгоритми на графах.
- •3.1. Основні визначення.
- •3.2. Алгоритми. Обходи графів. Побудова ейлеревих та гамільтонових циклів графа.
- •3.3. Пошук найкоротших відстаней та шляхів у зважених графах.
- •3.4. Пошук максимальної течії в мережах. Розрахунки у мережах.
- •Список використаної та рекомендованої літератури
2.2. Розміщення та сполучення.
У комбінаториці важливими є поняття розміщення, сполучення та перестановки. Наведемо визначення цих понять.
Нехай
фіксована множина. Упорядковані
підмножини з
елементів
множини
називаються
-перестановками,
або
-розміщеннями,
або розміщеннями з
елементів по
.
Якщо у перестановці беруть участь всі
елементи множини (
-перестановка),
то використовують термін перестановка.
Два
розміщення з
по
вважають різними, якщо або вони складаються
з різних елементів, або з однакових
елементів, але розміщених у різному
порядку. Символом
позначають кількість розміщень із
елементів по
.
Символом
позначають кількість перестановок
-множини.
В тих
випадках, коли не цікавий порядок
елементів у вибірці, а важливий лише її
склад, говорять про сполучення (іноді
використовують термін „комбінація”).
Сполученням з
елементів по
називається будь-яке
-розміщення
з цих елементів, в якому враховується
лише склад елементів і не враховується
їх порядок. Кількість
-сполучень
з
елементів позначається
(або, зазвичай у англомовній літературі
).
Знайдемо кількісні характеристики вищенаведених позначень.
Твердження 2.1. Справедливі рівності
1)
(2.1.1);
2)
(2.1.2);
3)
(2.1.3).
Доведення.
Доведемо першу рівність. Перший елемент
перестановки можна обрати
способами (будь-який елемент множини);
другий елемент
способами (будь-який, окрім того, що
обрали на перше місце); третій
способами (будь-який, окрім тих, що обрали
на перше та друге місце) і так далі.
Останній
-й
елемент можна обрати 1 способом. За
правилом добутку
.
Доведемо
другу рівність. Перший елемент будь-якої
-розміщення
можна обрати
способами (будь-який елемент множини);
другий елемент
способами (будь-який, окрім того, що
обрали на перше місце); третій
способами (будь-який, окрім тих, що обрали
на перше та друге місце) і так далі.
Останній
-й
елемент можна обрати
способами. За правилом добутку
Доведемо
третю рівність. Нехай
будь-яке
-сполучення
множини
.
Тоді з цього сполучення шляхом перестановки
елементів можна одержати
різних розміщень. Кожне інше
-сполучення
дасть
розміщень, що не співпадають із
попередніми. Тому кількість сполучень
з
елементів по
в
разів менша, ніж розміщень з
елементів по
,
тобто
.
■
Для чисел та справедливо наступне корисне твердження.
Твердження 2.2. Справедливі рівності
1)
(2.2.1);
2)
(2.2.2);
3)
(2.2.3).
Доведення. Всі ці рівності можна довести шляхом підстановки відповідних значень у формули, що доведені у твердженні 2.1. Ми доведемо ці рівності комбінаторним шляхом з урахуванням змісту поняття розміщення та сполучення.
Доведемо
першу рівність. Зафіксуємо деякий
елемент
з множини
.
Всі розміщення з
елементів множини
можна поділити на два класи, що не
перетинаються: першому класу належать
ті і тільки ті розміщення, в яких є
елемент
;
другому
ті, в яких
відсутній. Знайдемо кількість елементів
у кожному класі. В першому класі елемент
можна виставити на будь-яке місце (всього
варіантів), а на
місце, що залишилось, виставляються
інші
елементи множини
,
утворюючи
-розміщення.
Тобто, кількість елементів у першому
класі дорівнює
.
Елементами другого класу є
-розміщення
із
елементів множини
.
Кількість таких розміщень дорівнює
.
За правилом суми кількість всіх розміщень
з
елементів по
дорівнює сумі кількості елементів з
вищенаведених класів, тобто
.
Доведемо
другу рівність. Аналогічно до попереднього
випадку зафіксуємо деякий елемент
з множини
і всі сполучення з
елементів множини
розділимо на два класи, що не перетинаються:
першому класу належать ті сполучення,
в яких є елемент
;
другому
ті, в яких
відсутній. Знайдемо кількість елементів
у кожному класі. У першому класі треба
на вільне
місце розставити
елементів (це можна зробити
способами). У другому класі всі
місць вільні, а кількість елементів,
які можна розміщувати дорівнює
(всі, крім елементу
).
Тому у другому класі
елементів. За правилом суми
.
Доведемо
третю рівність. Кожному сполученню з
елементів по
однозначно відповідає сполучення з тих
елементів, які не увійшли до першого
сполучення. Тому
.
■
Зауважимо, що рівність (2.2.2) ми використаємо при доведенні теореми в наступному підрозділі. Рівність (2.2.3) часто називають правилом симетрії. Використовуючи відповідні формули з твердження 2.2 можна скласти таблицю значень – так званий трикутник Паскаля, що зображено на рис. 2.1.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
2 |
1 |
2 |
1 |
|
|
|
|
|
|
|
3 |
1 |
3 |
3 |
1 |
|
|
|
|
|
|
4 |
1 |
4 |
6 |
4 |
1 |
|
|
|
|
|
5 |
1 |
5 |
10 |
10 |
5 |
1 |
|
|
|
|
6 |
1 |
6 |
15 |
20 |
15 |
6 |
1 |
|
|
|
7 |
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
|
|
8 |
1 |
8 |
28 |
56 |
70 |
56 |
28 |
8 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 2.1. Трикутник Паскаля.
В цій
таблиці на перетині
-го
рядка і
-го
стовпчика міститься число
.
Кожний рядок таблиці починається з
одиниці та закінчується (на головній
діагоналі) одиницею. Всі інші значення
можна швидко заповнити за допомогою
рівності (2.2.2), а саме елемент, що
знаходиться на перетині
-го
рядка і
-го
стовпчика дорівнює сумі двох елементів
з попереднього
-го
рядка: елемента з
-го
та
-го
стовпчиків. Цю таблицю ще записують у
вигляді рівнобедреного трикутника
(тому і назва «трикутник Паскаля»).
Вищенаведені перестановки, розміщення та сполучення зображують вибірки попарно різних елементів початкової множини . Часто доводиться робити вибірки з повторенням деяких елементів. Наведемо необхідні означення.
Нехай
маємо множину
видів предметів, кількість предметів
кожного виду необмежена, та будь-які
предмети одного виду є нерозрізненими
між собою. Впорядковані
-послідовності
з цих предметів називають
-перестановками
з необмеженими повтореннями із
елементів.
Кількість таких
-перестановок
позначають через
.
Аналогічно,
невпорядковані
-послідовності
з цих предметів називають
-комбінаціями
з необмеженими повтореннями із
елементів.
Кількість таких
-комбінацій
позначають через
.
Знайдемо кількісні характеристики вищенаведених позначень.
Твердження 2.3. Справедливі рівності
1)
(2.3.1);
2)
(2.3.2).
Доведення.
Доведемо першу рівність. Кожний елемент
-перестановки
з необмеженими повтореннями можна
обрати
способами (будь-який елемент множини).
За правилом добутку
.
Доведемо
другу рівність. Кожній
-комбінації
з необмеженими повтореннями із
елементів поставимо у взаємнооднозначну
відповідність послідовність з
одиниць і
нулів за таким правилом: кількість
одиниць, що розташовані зліва від першого
нуля дорівнюють кількості предметів
першого виду; кількість одиниць, що
розташовані між першим та другим нулем
кількості предметів другого виду і так
далі. Кількість одиниць, що розташовані
справа від останнього,
-го
нуля дорівнюють кількості предметів
-го
виду предметів. Неважко пересвідчитися,
що ця відповідність є взаємнооднозначною
(кожній комбінації однозначно відповідає
деяка послідовність, і навпаки, кожній
послідовності однозначно відповідає
деяка комбінація). Тому кількість таких
-комбінацій
дорівнює кількості послідовності з
одиниць і
нулів. Підрахуємо кількість послідовностей.
Для однозначного визначення послідовності
треба або визначити всі місця, на яких
знаходяться нулі (тобто з
місць треба вибрати
,
і це можна зробити
способами), або визначити всі місця, на
яких знаходяться одиниці (тобто з
місць треба вибрати
,
це можна зробити
способами).
■
Розглянемо
ще один випадок сполучення із повтореннями.
Розглянемо впорядковані
-послідовності,
що складаються з
елементів першого виду,
елементів другого виду,...,
елементів
-го
виду. Такі послідовності називають
-перестановками
із заданою специфікацією
.
Кількість всіх таких перестановок
позначають через
.
Знайдемо цю величину.
Твердження 2.4.
Справедлива рівність
(2.4).
Доведення.
елементів першого виду можна розташувати
на будь-які місця перестановки
способами. Залишилось
вільних місць, на будь-які з них можна
розмістити
елементів другого виду (
способів).
елементів третього виду можна розмістити
на
вільних місць
способами і так далі.
елементів
-го
виду можна розташувати на
місць
способами. За правилом добутку:
.
В цьому
виразі чисельник кожного дробу, починаючи
з другого співпадає з одним із множників
знаменника попереднього. Після виконання
скорочень, та взявши до уваги, що
одержимо
.
■
Зауважимо, що перестановки із заданою специфікацією будуть використані у поліноміальній формулі.
