8 Объяснить, что такое число сочетаний, треугольник Паскаля и бином Ньютона.

Число сочетаний из по равно биномиальному коэффициенту

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

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

Треугольник Паскаля — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Назван в честь Блеза Паскаля. Имеет применение в теории вероятностей.

Свойства

• Числа треугольника симметричны(равны) относительно вертикальной оси.

• В строке с номером n:

  • первое и последнее числа равны 1.

  • второе и предпоследнее числа равны n.

  • третье число равно треугольному числу , что также равно сумме номеров предшествующих строк[3].

  • четвёртое число является тетраэдрическим[3].

  • m-е число равно биномиальному коэффициенту .

• Сумма чисел восходящей диагонали, начинающейся с первого элемента (n-1)-й строки, есть n-е число Фибоначчи:[3] 


• Если вычесть из центрального числа в строке с чётным номером соседнее число из той же строки, то получится число Каталана.[3]

• Сумма чисел n-й строки треугольника Паскаля равна [3].

• Простые делители чисел треугольника Паскаля образуют симметричные самоподобные структуры.

• Если в треугольнике Паскаля все нечётные числа окрасить в чёрный цвет, а чётные — в белый, то образуется треугольник Серпинского.

• Все числа в n-й строке, кроме единиц, делятся на число n, если и только если n является простым числом (следствие теоремы Люка).

• Если в строке с нечётным номером сложить все числа с порядковыми номерами вида 3n, 3n+1, 3n+2, то первые две суммы будут равны, а третья на 1 меньше.

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

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

Числитель и знаменатель дроби в формуле (1.1) для числа сочетаний можно сократить на (n − k)!, переписав ее в виде

􏰑n􏰒 n(n − 1)(n − 2) . . . (n − k + 1) k= k! . (1.3)

Такое сокращение позволяет расширить круг значений, к которым она при- менима — в качестве аргумента n можно брать произвольное число, не обя- зательно натуральное. Например,

􏰑1/2􏰒 1/2(−1/2)(−3/2)(−5/2) . . . ((3 − 2k)/2) (−1)k−11 · 3 · 5 · (2k − 3) k= k! = 2kk! .

При таком подходе число сочетаний перестает быть целым и теряет прямой комбинаторный смысл (нельзя сказать, что это число k-элементных под- множеств в «полуэлементном множестве»). Вообще, число n может быть иррациональным и даже комплексным. Однако по-прежнему естественно полагать

􏰑n􏰒 0=1

для произвольного n. Если n натуральное или 0, то при k > n в знаменателе формулы (1.3)

встречается нулевой множитель, и поэтому все выражение равно 0. Напро-

тив, если n не является целым неотрицательным числом, то число сочетаний

􏰎n􏰏 не является нулевым ни при каком k.

k

Такие обобщенные числа сочетаний можно применить для получения разложения бинома в произвольной степени, не только в целой. А именно,

􏰑a􏰒 􏰑a􏰒 􏰑a􏰒 􏰑a􏰒 (1+s)a =1+ 1 s+ 2 s2+ 3 s3+ 4 s4+... (1.4)

Здесь в обозначениях n заменено на a, чтобы подчеркнуть, что мы больше не считаем показатель натуральным, а первая переменная заменена на 1, чтобы не было необходимости решать, что такое x в ненатуральной сте- пени (1a = 1 для любого показателя a). В случае, если число a является натуральным, разложение (1.4) совпадает с обычной степенью бинома. Для ненатурального показателя степени оно было введено Ньютоном и пред- ставляет собой бесконечный степенной ряд. Этот ряд можно считать опре- делением левой части (а можно — и в курсе математического анализа это делается — доказывать, что ряд сходится при |s| < 1, причем слева от знака равенства действительно написана функция, к которой он сходится).