Get Adobe Flash player

Лекція 2. ЕЛЕМЕНТИ КОМБІНАТОРИКИ

Комбінаторика – розділ математики, предметом якого є теорія скінченних множин.

Множина – сукупність об'єктів довільної природи, які володіють спільною для всіх них характеристичною властивістю.

Приклади:

  1. Множина всіх дійсних чисел.
  2. Множина цілих чисел – нескінченні множини.
  3. Множина цілих чисел від 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} – всього шість.