Рекуррентная формула для числа сочетаний без повторений. Треугольник Паскаля

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

Зафиксируем в n ‑множестве некоторый элемент и рассмотрим r ‑сочетания без повторений из этого n ‑множества. Относительно любого сочетания можно сказать, содержит ли оно данный зафиксированный элемент или нет.

Если содержит, то остальные (r -1) элементов сочетания выбираются из (n -1)-множества. Число способов выбрать (r -1) элемент из (n -1)-множества без учета порядка: .

Если не содержит (в сочетании этого элемента нет), то это r ‑сочетания из (n -1)-множества (то есть из множества, в котором удален данный элемент). Число способов выбрать r элементов из (n -1)-множества без учета порядка: .

Эти два случая взаимоисключающие, поэтому по правилу суммы

с начальными условиями

, и при r > n .

Таким образом, числа сочетаний без повторений (биномиальные коэффициенты) можно вычислять не только по прямой формуле, но и рекуррентно. Построим таблицу для биномиальных коэффициентов. Исходя из начальных условий, в столбце 0 и на диагонали находятся единицы, а все клетки, находящиеся выше диагонали, содержат нули. Из рекуррентной формулы следует, что для получения значения в n -й строке r -м столбце (заданная клетка) нужно сложить значение в (n- 1)‑й строке r -м столбце (клетка сверху над заданной) и значение в (n‑ 1)‑й строке (r- 1)-м столбце (клетка сверху слева от заданной).

r n

…

Бином

(a + b)^0= 1

1=2^0

(a + b)^1= 1 a +1 b

2=2^1

(a + b)^2= 1 a ^2+2 ab +1 b ^2

4=2^2

(a + b)^3= 1 a ^3+3 a ^2 b +3 ab ^2+1 b ^3

8=2^3

(a + b)^4= 1 a ^4+4 a ^3 b +6 a ^2 b ^2+4 ab ^3+1 b ^4

16=2^4

M

32=2^5

64=2^6

128=2^7

256=2^8

M

M

M

M

M

M

M

M

M

M

M

Эта таблица называется треугольником Паскаля. Он позволяет быстро находить числа сочетаний без повторений и не требует вычисления факториалов.

Видно, что в каждой строке таблицы сумма чисел равна степени двойки. Это свойство чисел сочетаний без повторений, которое будет доказано ниже.

Дата добавления: 2014-01-05