Лекція 2. ЕЛЕМЕНТИ КОМБІНАТОРИКИ
Комбінаторика – розділ математики, предметом якого є теорія скінченних множин.
Множина – сукупність об'єктів довільної природи, які володіють спільною для всіх них характеристичною властивістю.
Приклади:
- Множина всіх дійсних чисел.
- Множина цілих чисел – нескінченні множини.
- Множина цілих чисел від 1 до 100 – скінченна множина.
А, В, С,... – множини; a, b, c – їх елементи. Нагадаємо, що – відповідно об'єднання, перетин, різниця множин і порожня множина. Позначимо: N(A) – кількість елементів множини А. Якщо N(A)=n, то казатимемо, що А – n-множина.
В основі комбінаторики лежать два елементарні правила – суми і добутку. Сформулюємо правило суми.
.
Правило добутку (основне правило комбінаторики): якщо I-у дію можна здійснити n1 способами, II-у, яка не залежить від першої, – n2 способами, ..., k- ту, яка не залежить від усіх попередніх, – nk способами, то першу, другу, ..., k-ту дії послідовно можна здійснити n1n2...nk способами.
Приклад.
Скількома способами можна потрапити з п.А до п.D, якщо з А до В веде m доріг, з В до D – k доріг, з А до С – n доріг і з С до D – l доріг?
Розв'язання. За правилом добутку рух шляхом ABD можна здійснити mk способами, а шляхом ACD – nl способами. Згідно з правилом суми з А до D можна потрапити mk + nl способами.
Впорядковані множини
Озн. Множина М називається впорядкованою, якщо в ній встановлено відношення порядку, що має такі властивості:
1)
2)якщо
Для впорядкування n-множини досить кожному з її елементів приписати один з номерів 1,2,...,n, або просто записати її елементи в певному порядку.
Ту саму множину, очевидно, можна впорядкувати по-різному. Наприклад, для множини М={1, 2, 3} можливі такі впорядкування:
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Розміщення, перестановки, комбінації
Озн. Нехай М – n-множина; . Розміщенням з n елементів по k називають будь-яку впорядковану k-підмножину множини М.
Кількість розміщень з п елементів по k обчислюють за формулою:
Приклад.
М={1, 2, 3}; п=3, k=2; Справді, можливі розміщення такі:
(1;2), (1;3), (2;1), (2;3), (3;1), (3;2) – всього шість.
Озн. Перестановкою з n елементів називається розміщення з n елементів по п, тобто будь-яке впорядкування п-множини, яка складається з різних елементів.
Щоб задати перестановку з п елементів, досить якимось чином впорядкувати п-множину.
Кількість перестановок з п елементів обчислюють за формулою:
Зокрема, P3=3!=6, в чому можна переконатися, повернувшись до прикладу про можливі впорядкування множини М={1, 2, 3}.
Озн. Нехай М – n-множина; . Комбінацією з n елементів по k називають будь-яку k-підмножину множини М.
Кількість комбінацій з п елементів по k обчислюють за формулою:
Приклад.
М={1, 2, 3}; п=3, k=2; . Справді, можливі комбінації такі: {1;2}, {1;3}, {2;3} – всього три.
Числа називають біномними коефіцієнтами, оскільки вони фігурують у відомій формулі біному Ньютона . Поклавши у ній a = b = 1, одержимо: - кількість підмножин n-множини.
Розміщення з повтореннями
Озн. Нехай М – n-множина; довільне натуральне число.
Розміщенням з повтореннями з n елементів по k називають будь-яку впорядковану множину вигляду (a1,a2,...,an), де аi, i=1, k − елементи множини М, не обов'язково різні.
Кількість розміщень з повтореннями з п елементів по k обчислюють за формулою:
Приклади. 1) М={1, 2}; п=2, k=3; Справді, можливі розміщення такі:
(2,1,1), (1;2,1), (1,1,2), (1,2,2), (2,1,2), (2;2,1), (1,1,1), (2,2,2) – всього вісім.
2) М={1, 2, 3}; п=3, k=2; Справді, можливі розміщення такі:
(1;2), (1;3), (2;1), (2;3), (3;1), (3;2), (1;1), (2;2), (3;3) – всього дев'ять.
Перестановки з повторенням
Озн. Перестановкою з повтореннями з n елементів називається будь-яке впорядкування n-множини, серед елементів якої є однакові.
Якщо серед елементів n-множини є n1 елементів першого типу, n2 елементів другого типу, ..., nk елементів k-ого типу, причомy , то кількість перестановок з повтореннями з п елементів обчислюють за формулою: . Остання формула задає також кількість способів розбиття п-множини на k підмножин, що містять відповідно n1,n2,...,nk елементів.
Приклад.
М={1, 2, 2}; n=3, n1=1, n2=2, k=2; . Справді, можливі перестановки такі: (1,2,2), (2,1,2), (2,2,1) – всього три.
Комбінації з повтореннями
Озн. Нехай М – n-множина; - довільне натуральне число. Комбінацією з повтореннями з n елементів по k називають будь-яку k-множину вигляду, де - елементи множини М, не обов'язково різні.
Кількість комбінацій з повтореннями з п елементів по k обчислюють за формулою: .
Приклади.
1) М={1, 2}; n=2, k=3;. Справді, можливі комбінації такі: {2,1,1}, {1,2,2}, {1,1,1}, {2,2,2} – всього чотири.
2) М={1, 2, 3}; n=3, k=2; . Справді, можливі комбінації такі: {1;2}, {1;3}, {2;3}, {1;1}, {2;2}, {3;3} – всього шість.