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

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