3. Бином Ньютона и свойства биномиальных коэффициентов

Числа обладают многими замечательными свойствами, из которых особенно важным является то, что они входят в качестве коэффициентов в разложение выражения по степеням x и y. Это разложение называется биномом Ньютона, а коэффициенты – биномиальными коэффициентами.

Теорема 7 (Бином Ньютона). .

Д о к а з а т е л ь с т в о. Запишем левую часть бинома в виде произведения n одинаковых сомножителей: . После раскрытия скобок (до приведения подобных членов) получаем сумму, в которой каждое слагаемое является произведением n переменных, по одной из каждого сомножителя. Запишем каждое такое слагаемое в виде слова, в котором i-тую позицию занимает переменная, выбираемая из i-того сомножителя, например, xxyyyx вместо x³y³. Нетрудно видеть, что в такой записи множество всех слагаемых, получаемых после раскрытия скобок, образует множество всех слов длины n в алфавите {x,y}. В этом множестве количество слов, содержащих в точности k символов x, равно (см. задачу 1). Таким образом, группируя в каждом слагаемом одинаковые сомножители в виде степени и приводя подобные, получаем правую часть бинома. 

Рассмотрим некоторые свойства биномиальных коэффициентов.

1. . 3. .

2. . 4. .

Свойства 1–4 можно доказать непосредственной проверкой, используя выражение биномиальных коэффициентов через факториалы. Особенно важным из них является последнее. Оно позволяет с помощью одних только операций сложения найти все числа сочетаний из n элементов, если известны числа сочетаний из элемента. Это лежит в основе построения таблицы биномиальных коэффициентов, называемой треугольником Паскаля. В треугольнике Паскаля биномиальные коэффициенты располагаются следующим образом:

1

1 1

= 1 2 1

1 3 3 1

. . . . . . . . . . . . . .

В этой бесконечной таблице строка с номером n (n = 0,1,2,...) образована числами , k пробегает все значения от 0 до n. При этом каждая следующая строчка сдвинута относительно предыдущей таким образом, что непосредственно над числом левее и правее его оказываются расположены числа и , сумма которых, по свойству 4, как раз и равна . Таким образом, если строка с номером заполнена, то легко заполняется строка с номером n: первый и последний элементы всегда равны 1, а каждый из остальных получается сложением двух расположенных над ним элементов предыдущей строки.

Некоторые свойства биномиальных коэффициентов легко выводятся из бинома Ньютона. Приведем два из них.

5. . Это получается из формулы бинома, если положить .

6. . Это получается при .

Задачи

1. Докажите тождества:

1) (совет: воспользуйтесь свойством 4);

2) ;

3) .

2. Докажите, что число слов длины n в алфавите E, имеющих четное число единиц, равно .