Треугольник Паскаля.

Сочетаниями без повторений занимался еще великий Паскаль. Он предложил специальную таблицу значений сочетаний без повторений.
Значения   представлены в табл. 6, которая называется треугольни-ком Паскаля.
Таблица 6
Треугольник Паскаля
k
n 0 1 2 3 4 5 6 7 8
0 1               
1 1 1           
2 1 2 1           
3 1 3 3 1       
4 1 4 6 4 1       
5 1 5 10 10 5 1   
6 1 6 15 20 15 6 1   
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1

Заметим, что  .
Этот треугольник удивительно красив своей математической красотой, и в его числах можно при желании отыскать различные закономерности. Его можно представить несколько иначе – в виде [26]: равнобедренного треугольника (рис. 10).

Рис. 10. Треугольник Паскаля

Здесь каждое число, кроме единиц на боковых сторонах, является сум-мой двух чисел, стоящих над ним. Поэтому:

(приводим к общему знаменателю)

(выносим n! за скобку в знаменателе)

Из этого соотношения и вытекает эффективный способ рекуррентного вычисления значений биномиальных коэффициентов.
Докажем соотношение 1) 

Это может использоваться при вычислениях, например, вместо   можно вычислить  .
Докажем соотношение 2) 

3.7. Бином Ньютона

Имеется формула, называемая биномом Ньютона, которая использует выражения числа сочетаний с повторениями 

где а, b – действительные или комплексные числа.
Например:

Коэффициенты   называются биномиальными.
Докажем формулу бинома Ньютона по индукции. Доказательство по индукции предполагает:
1) базис индукции – доказательство того, что формула верна для кон-кретного n, например, для n=1. В нашем случае мы убедились, что формула верна для n=2,3,4. Убедимся, что она верна и для n=1.

2) индукционный шаг. Предполагая, что формула верна для некоторого n, убеждаются, что тогда она верна и для n+1.
3) при истинности шагов 1 и 2 заключают, что формула верна для лю-бого n.
Приступим к индукционному шагу.
Возьмем выражение   и получим из него выражение для n+1. Очевидно, что это можно сделать путем умножения на a+b:

Преобразуем полученное выражение:

Для выполнения индукционного шага необходимо показать, что это выражение равно выражению:
.
Рассмотрим подвыражение выражения (1):  и заменим i на i-1.
Получим  , т.е. одинаковые коэффициенты   перед вы-ражениями  ,   для числа сочетаний в первом и втором подвыраже-нии выражения (1).Это позволит вынести   за скобку. Но тогда в   не учтен n-й член подвыражения   (суммирование идет до n):   тогда, учитывая его, получаем:

Нетрудно видеть, что   можно заменить   на  , кроме того, мы уже доказали, что  , по-этому:  , что, очевидно, равно выражению:
.
По индукции получаем, что формула бинома Ньютона верна для любо-го n.
С использованием бинома Ньютона докажем следствие №1 о количест-ве подмножеств множества из n элементов:

Рассмотрим следствие №2:  .

На использовании бинома Ньютона основано понятие производящей функции – функции, позволяющей получать комбинаторные числа без вы-числения факториала:
. Здесь   – функция, производящая би-номиальные коэффициенты.
При n=1 получаем 1+x, т.е.   (коэффициент перед 1),   (ко-эффициент перед x).
При n=2 получаем (1+x)2=1+2x+x2, т.е.  и т.д.