Комбинаторные алгоритмы для программистов

         

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


Получим производящую функцию для конечной последовательности чисел

. Известно, что

и

Эти равенства являются частными случаями более общей формулы, дающей разложение для

. Запишем
в виде

(10.4)

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

запишем в виде

(10.5)

а

- в виде

(10.6)

Видно, что в формулу (10.5) входят все размещения с повторениями, составленные из букв

и
по две буквы в каждом размещении, а в формулу (10.6) - размещения с повторениями из тех же букв, но состоящие из трех букв каждое. То же самое и в общем случае — после раскрытия скобок в формуле (10.4) мы получим всевозможные размещения с повторениями букв
и
, состоящие из
элементов. Приведем подобные члены. Подобными будут члены, содержащие одинаковое количество букв
(тогда и букв
в них будет поровну). Найдем, сколько будет членов, в которые входит

букв

и, следовательно,
букв
. Эти члены являются перестановками с повторениями, составленными из
букв

и

букв
. Поэтому их число равно

Отсюда вытекает, что после приведения подобных членов выражение

войдет с коэффициентом
. Итак, мы доказали, что

(10.7)

Равенство (10.7) принято называть формулой бинома Ньютона. Если положить в этом равенстве

, то получим

(10.8)

Мы видим, что

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



Содержание раздела