Фундаментальная и компьютерная алгебра

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

Так называются комбинаторно определяемые числа -- число способов выбора k предметов из предметов. Здесь . Ясно, что и . Ясно также, что

ибо выбор предметов означает автоматический «невыбор» оставшихся предметов. Перейдем к выводу основного рекуррентного соотношения между биномиальными коэффициентами. Пусть у нас имеется предметов, составляющих множество А, среди которых фиксируем один предмет . Все выборы k предметов из A, т.е. все подмножества B⊆ A содержащие k предметов разбиваются на два класса -- те, что содержат и те, что не содержат . В первом классе подмножеств (остается выбрать k-1 предмет из A\ {a}, а во втором классе подмножеств (все k предметов выбираем из множества A\{a}). Получаем:

Вместе с граничными условиями это дает способ вычисления всех чисел . Соотношения (3) также представляют из себя рекуррентные формулы, только более сложные, чем те посредством которых определялось сложение и умножение натуральных чисел. Получаем так называемый треугольник Паскаля

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 ..... .. .. .. .. .. .. .. .. .. .. .. .....

В этом треугольнике n-ая строка сверху содержит числа при k=0,1,2,… , n. Любое число, кроме самых крайних слева и справа равно сумме чисел стоящих над ним (4=1+3, 6=3+3, и.т.д.) Имеется и прямая, не рекуррентная формула для чисел

Доказательство. Обозначим пока . Имеем:

Иными словами, краевые условия совпадают. Докажем, что числа удовлетворяют рекуррентному соотношению (4).

Теперь очень легко индукцией по n доказать, что имеет место равенство для всех допустимых k. Действительно, база индукции, n=1 проверяется прямым подсчетом. Предполагая далее верным равенство при всех 0≤ k≤ n докажем равенство для всех 0≤ k≤ n+1. Во-первых, это так для k=0 и для k=n+1 в силу совпадения граничных условий. Для остальных k воспользуемся рекуррентным соотношением:

□

ТЕОРЕМА 2 (бином Ньютона). Для любого натурального n имеет место равенство

Доказательство. Раскрывая скобки в произведении (a+b)(a+b)… (a+b) ( n раз) мы видим, что количество слагаемых, у которых степень по b равна k, а степень по a равна n-k совпадает с числом выборов k предметов из n предметов, т.е. с . □

Возможен и другой способ доказательства бинома Ньютона -- индукцией по степени n. Тогда следует применить рекуррентные формулы (4). В связи формулой бинома Ньютона числа называют (биномиальными коэффициентами.)

Содержание