Початки комбінаторики, Детальна інформація

((((( ((((( (((((

k1 k2 … kn

Цю перестановку також будемо називати комбінацією по m елементів множини {a1, a2, …, an} з повтореннями складу (k1, k2, …, kn).

Приклади.

1. При A={a, b, c} усіма комбінаціями по 2 з повтореннями є послідовності (a,a), (a,b), (a,c), (b,b), (b,c), (c,c). Їм відповідають усі можливі склади (2,0,0), (1,1,0), (1,0,1), (0,2,0), (0,1,1), (0,0,2).

2. Нехай m однакових кульок розкладаються по n різних ящиках так, що у першому ящику k1 кульок, у другому – k2 кульок, …, у n-му – kn кульок, причому m=k1+k2+…+kn. Пронумеруємо ящики від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру ящика кількість кульок у ньому. Отже, маємо послідовність (k1, k2, …, kn), що є складом. Припишемо кожній кульці номер її ящика і утворимо послідовність номерів вигляду

(1, …, 1, 2, …, 2, …, n, …, n).

((( ((( (((

k1 k2 … kn

Як бачимо, множиною елементів, якими утворюється комбінація з повтореннями, тут є {1, 2, …, n}.

Комбінації по m елементів множини {a1, a2, …, an} з повтореннями складу (k1, k2, …, kn) можна взаємно однозначно поставити у відповідність послідовність довжини m+n-1 із m "1" і n-1 "0":

(1, …, 1, 0, 1, …, 1, 0, …, 1, …, 1).

((( ((( (((

k1 k2 … kn

, що й є кількістю всіх можливих комбінацій по m елементів n-елементної множини з повтореннями.

6. Формули включень і виключень

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

|A(B|=|A|+|B|-|A(B|. (*)

При обчисленні |A(B(C| додавання |A|+|B|+|C| веде до того, що елементи кожного з перетинів |A(B|+|B(C|+|A(C| враховуються двічі, тому їх треба по одному разу відняти. Якщо перетин A(B(C порожній, то в результаті кожний елемент об'єднання враховано по одному разу, і все гаразд. Якщо ні, то в результаті елементи цього перетину тричі додаються і тричі віднімаються, тобто у виразі

|A|+|B|+|C|–|A(B|–|B(C|–|A(C|

не враховані. Отже, їх треба додати:

|A(B|=|A|+|B|+|C|–|A(B|–|B(C|–|A(C|+|A(B(C|. (**)

Вирази (*), (**) наводять на припущення, що в загальному випадку об'єднання n множин A1, A2, …, An

|A1(A2(…(An|=|A1|+|A2|+…+|An|–|A1(A2|–|A1(A3|–…–|An-1(An|+

+|A1(A2(A3|+…+|An-2(An-1(An|–…+(-1)n+1|A1(A2(…(An|. (1)

Як бачимо, кількості елементів усіх можливих перетинів непарної кількості множин додаються, а парної – віднімаються. Формула (1) називається формулою включень і виключень.

Доведення формули (1) можна провести з використанням індукції за n, але тут ми його не наводимо.

Ця формула дає змогу за кількостями елементів у кожній з множин, в усіх можливих їх перетинах по дві, по три і т.д. множини обчислити кількість елементів об'єднання.

Приклад. Є група студентів, серед яких каву п'ють 12 (це множина A), чай – 10 (множина B), йогурт – 8 (C), каву і чай – 5 (A(B), каву і йогурт – 4 (A(C), чай і йогурт – 3 (B(C), усі три напої – 1 (A(B(C). Тоді всього студентів у групі 12+10+8-5-4-3+1=19.

За допомогою формули (1) можна обчислити кількість елементів деякої множини U, що не належать жодній з її підмножин A1, A2, …, An: