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

Рассмотрим задачу, сочетающую правило сложения и нахождение числа сочетаний. Вывести рекуррентную формулу для подсчета биномиальных коэффициентов.

Выделим из n элементов один и разобьем все k-элементные подмножества на два класса:

- содержащие выделенный элемент и

- не содержащие его.

Первых будет , так как один элемент уже выбран, и из оставшихся n-1 элементов надо выбрать еще k-1 элемент.

Вторых будет , так как один элемент запрещается выбирать, и надо выбрать все k элементов из оставшихся n-1.

Так как любое подмножество (сочетание) принадлежит либо одному, либо другому классу и классы не пересекаются, получаем рекуррентную формулу:

Процесс вычислений по этому рекуррентному соотношению можно представить в виде пирамиды, которая называется треугольником Паскаля:

В этом треугольнике каждое число по выведенной рекуррентной формуле есть сумма двух, стоящих над ним, а по границам треугольника стоят единицы.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

………………..

Например, (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴.