1 2 3 4

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

Доведення формули (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:

|U\(A1ÈA2È…ÈAn)|=|U|-|A1|-|A2|-…-|An|+|A1ÇA2|+|A1ÇA3|+…+

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

Формулу (2) також називають формулою включень і виключень.

7. Біноміальні коефіцієнти

Означення. Біном Ньютона - це вираз вигляду (a+b)n.

Біном розкладається в суму одночленів, які є добутками деяких степенів його доданків a і b. Школярі-восьмикласники знають формули розкладу бінома Ньютона в многочлен із степенями a і b при n=2 та 3:

(a+b)2=a2+2ab+b2,

(a+b)3=a3+3a2b+3ab2+b3.

Спробуємо розкласти (a+b)n в многочлен у загальному випадку n. Запишемо його у вигляді, пронумерувавши дужки:

1 2 … n

(a+b)(a+b)…(a+b).

Очевидно, що кожний доданок містить n множників - k множників a і n-k множників b, тобто має вигляд akbn-k, де k£n, k³0. Кожний такий доданок взаємно однозначно відповідає підмножині номерів дужок, з яких для утворення цього доданка ми брали множники a. Таким чином, доданків akbn-k рівно стільки, скільки таких підмножин, тобто =. Отже,

(a+b)n =

Коефіцієнти при akbn-k називаються біноміальними, оскільки записуються в розкладі бінома (a+b)n.

Біноміальні коефіцієнти мають очевидну властивість симетрії:

= =..

Розглянемо окремі випадки бінома Ньютона:

при b=1 маємо (a+1)n = ,

при a=b=1 маємо (1+1)n = 2n = ,

при a= -1, b=1 маємо (-1+1)n = 0n = (-1)k.

За останньою рівністю, зокрема, природно означити 00 як 1, слідуючи за Доналдом Кнутом [****].

Запишемо біноміальні коефіцієнти для початкових значень n=0, 1, …, 5 у трикутну таблицю:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

З таблиці видно, що кожний елемент, який не є першим у своєму рядку, є сумою елемента над ним і елемента, розташованого над ним і ліворуч:

= +

Ця тотожність називається правилом додавання. Існує багато різних її доведень. Ось "лобове":

Доозначимо біноміальні коефіцієнти при k<0 та k>n як =0. Тоді правило додавання справджується за будь-яких значень k. Скористаємося цим доозначенням також і далі, розглядаючи суми, в яких додавання ведеться за нижнім коефіцієнтом k у виразах вигляду . Це дозволить не записувати межі, у яких змінюється k.

Доведемо ще одну тотожність, яка називається згорткою Вандермонда:

.

Якщо замінити k на k-m, а n - на n-m, то одержимо рівність

.

1 2 3 4