5.4 Бином Ньютона и полиномиальная теорема.

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

Исторически название бином Ньютона² несправедливо, ибо формулу (a+b)ⁿ знали еще среднеазиатские математики, начиная с Амара Хайяма³ (около 1100 г.), в Европе до Ньютона ее знал Паскаль⁴. Заслуга Ньютона, что он обобщил эту формулу для нецелого показателя п. Итак,

Биномиальное разложение служит основой для многих комбинаторных формул, например:

1. a=b=1. Получим . Это число равно числу всех возможных неупорядоченных подмножеств множества S_п, состоящего из п элементов. Действительно, т.к. - число k-элементных подмножеств ((п, k)-сочетаний) множества S_п, то сумма в левой части есть число всех подмножеств.

2. a=1, b=-1. Отсюда . Из этого равенства следует, что суммы биномиальных коэффициентов, стоящих на четных и на нечетных местах, равны между собой и каждая равна 2^п-1.

Полиномиальная теорема - обобщение формулы бинома на случай k слагаемых:

,

где суммирование проводится по всем решениям уравнения r₁+ r₂+… +r_k=п в целых неотрицательных числах, т.е. выражение равно сумме всех возможных слагаемых вида ; r₁+ r₂+… +r_k=п.

Пример. Вычислить (х+у+z)³

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

(х+у+z)³=х³+у³+ z³+3х²у+3х² z+3у²х+3у² z+3 z² х+3 z² у+6ху z

Всего в выражении 10 членов. Этот же результат легко найти по полиномиальной формуле при п=3, k=3. Система условий суммирования здесь имеет вид . Различных числовых коэффициентов тоже три: , , . Для более удобного написания конечного результата лучше составить все возможные комбинации индексов r₁, r₂,r₃ и поместить их в таблицу.

r1	r2	r3
3	0	0
0	3	0
0	0	3
2	1	0
2	0	1
1	2	0
0	2	1
1	0	2
0	1	2
1	1	1

Тогда

(х+у+z)³=1·(х³+у³+ z³)+3·(х²у+х² z+у²х+у²z+ z²х+ z²у)+6·хуz. То же самое, что было получено раньше.

ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ С ПОВТОРЕНИЕМ

Пусть S – множество, содержащее п неразличимых объектов. Тогда количество различных перестановок, образованных выбором k элементов с повторением, равно пk.

Пример 1. Лототрон содержит 500 шаров с номерами. Из него выбирают шар, номер которого записывают. Шар возвращают в лототрон и процедура повторяется. Так продолжается до тех пор, пока не наберется комбинация из пяти номеров. Подсчитаем количество возможных комбинаций чисел. Для каждого из пяти чисел имеется 500 способов выбора. Следовательно, число различных комбинаций составляет 500⁵.

Пример 2. Сколько существует индивидуальных номеров карточек социального страхования?

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

Количество различных сочетаний из k объектов по п с повторением равно

Пример 3. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать дюжину пончиков? Поскольку 12 пончиков выбираются из 10 различных типов с повторением, то имеются

различных способов выбрать дюжину пончиков.

Количество различных сочетаний из k объектов по п с повторением, когда необходимо выбрать хотя бы по одному объекту каждого типа, равно

Пример 4. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать две дюжины пончиков, если необходимо выбрать хотя бы по одному пончику каждого вида? Если бы не было последнего ограничения, то для выбора двух дюжин пончиков из 10различных видов существовало бы различных способов. Однако, учитывая ограничение, можно выбрать только 24-10=14 пончиков из 10 различных видов, что дает различных вариантов выбора.

Если среди п элементов п1 элементов одного вида, п1 элементов другого вида и т.д.. то число перестановок с повторениями определяется формулой , где п1+ п2+…+пk=п

Пример 5. Сколькими способами можно выбрать четыре набора по пять карт из колды, содержащей 52 карты? По сути, колода разбивается на пять множеств: четыре набора по пять карт и 32 оставшихся карты. Поэтому количество таких наборов равно .