Початки комбінаторики

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

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

123 123 123

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).

123 123 123

k1 k2 … knТакій послідовності, у свою чергу, взаємно однозначно відповідає комбінація номерів місць у цій послідовності, на яких розташовані 1 (або 0). Кількість таких комбінацій є , що й є кількістю всіх можливих комбінацій по 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) називається формулою включень і виключень.