Биномиальная теорема.

Биномиальная формула (бином Ньютона).

Часто при решении комбинаторных задач используется биномиальная теорема (бином Ньютона).

(6.14)

Доказательство.

Перемножим последовательно (a+b) n раз. Получим сумму 2n слагаемых вида d1d2...dn, где di (i=1,…,n) равно либо a, либо b. Разобьем все слагаемые на n+1 группу B0,B1,…,Bn, относя к группе Bk все те произведения, в которых b встречается множителем k раз, а a — n–k раз. Число элементов в Bk очевидно равно (таким числом способов среди n произведений d1d2...dn можно выбрать k сомножителей, равных b), а каждый элемент в Bk равен . Отсюда и получаем формулу (6.14).