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



             

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


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

C_n^0,C_n^1,\ldots,C_n^n
. Известно, что

(a + x)^2 = a^2 + 2ax + x^2

и

(a + x)^3 = a^3 + 3a^2 x + 3ax^2 + x^3.

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

(a + x)^n
. Запишем
(a + x)^n
в виде

(a + x)^n = \underbrace{(a + x)(a + x)\ldots (a + x)}_{n \text{ раз}}.

(10.4)

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

(a +x)^2
запишем в виде

(a + x)^2 = (a + x)(a + x) = aa + ax + xa + xx,

(10.5)

а

(a + x)^3
- в виде

 (a + x)^3 = (a + x)(a + x)(a + x) = aaa + aax + axa + axx + xaa + xax + xxa + xxx.

(10.6)

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

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

букв

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

и

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

P(k,n - k) = C_n^k = \frac{{n!}}{{k!(n - k)!}}.

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

x^k a^{n - k}
войдет с коэффициентом
C_n^k = \frac{{n!}}{{k!(n - k)!}}
. Итак, мы доказали, что

 (a + x)^n = C_n^0 a^n + C_n^1 a^{n - 1} x + \ldots + C_n^k a^{n - k} x^k + \ldots + C_n^n x^n.

(10.7)

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

a = 1
, то получим

 (1 + x)^n = C_n^0 + C_n^1 x + \ldots + C_n^k x^k + \ldots + C_n^n x^n.

(10.8)

Мы видим, что

(1 + x)^n
является производящей функцией для чисел
C_n^k
,
k = 0,1,\ldots
. С помощью этой производящей функции можно сравнительно просто доказать многие свойства чисел
C_n^k
.




Содержание  Назад  Вперед