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

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

. Отже,



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

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

.

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

,

,

(–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

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