logo search
флеров

Биномиальные коэффициенты

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

(1.1)

Для доказательства справедливости написанного соотношения ( 1 .1) достаточно заметить, что коэффициент при xk равен числу способов, которыми из m сомножителей (1+x) ... (1+x) можно выбрать k сомножителей.

Отметим некоторые важнейшие соотношения для биномиальных коэффициентов (чисел сочетаний).

1.

(1.2)

Это важнейшее соотношение - прямое следствие того факта, что каждому k-элементному подмножеству YX однозначно соответствует (n-k) - элементное подмножество X\Y множества X.

2.

(1.3)

Зафиксируем некоторый элемент x из n- элементного множества X. Множество T всех k - элементных подмножеств множества X распадается на два непересекающихся класса:

,

класс T1 подмножеств, которые не содержат элемент x, и класс T2 подмножеств, которые его содержат. Мощность первого класса составляет , а второго , то есть столько, сколько имеется (k-1) - элементных подмножеств множества X\{x}.

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

3. Полагая в ( 1 .1) x=1 получим

Эта формула следует и из того, что сумма слева есть число всех подмножеств n-элементного множества.

4.

(1.4)

Дифференцируя ( 1 .1) и полагая x=1, получаем соотношение ( 1 .4) .

5.

(1.5)

Равенство легко следует из следующего равенства для производящих функций:

(1+x)m+n =(1+x)m (1+x)n .

Полагая в ( 1 .5) m = k = n, получим

.

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

6. Полагая в ( 1 .1) x = –1, получаем

.

Отсюда следует, что

,

где через обозначена целая часть числа m/2.