Сочетания

Сочетания из $n$ объектов по $k$ — все возможные варианты выбора $k$ различных элементов из набора $n$ объектов без учёта порядка.

Например, сочетания из $5$ объектов $\{a, b, c, d, e\}$ по $3$ это

abc,\quad abd,\quad abe,\quad acd,\quad ace,\quad ade,\quad bcd,\quad bce,\quad bde,\quad cde

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

Количество сочетаний из $n$ по $k$ ещё называется биномиальным коэффициентом и обозначается

\binom{n}{k} \defeq \frac{n!}{(n-k)! \cdot k!}

В нашем примере

\binom{5}{3} = \frac{5!}{(5-3)! \cdot 3!} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = 10

Треугольник Паскаля

Давайте нарисуем треугольную сетку. Самое верхнее число будет $1$ . Будем заполнять треугольник по рядам: в каждую ячейку будем вписывать сумму чисел, находящихся над этой ячейкой. Пустые ячейки будем считать нулями. Получится какой-то такой треугольник

\begin{array}{r c c c c c c} & & & & & & & 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 \\ 1 && 7 && 21 && 35 && 35 && 21 && 7 && 1 \\ \end{array}

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

Давайте раскроем скобки в выражении

(x+y)^n

Посмотрим на малые значения $n$ :

\aligned{ (x + y)^0 &= 1 \cdot x^0y^0 \\ (x + y)^1 &= 1 \cdot x^1y^0 + 1 \cdot x^0y^1 \\ (x + y)^2 &= 1 \cdot x^2y^0 + 2 \cdot x^1y^1 + 1 \cdot x^0y^2 \\ (x + y)^3 &= 1 \cdot x^3y^0 + 3 \cdot x^2y^1 + 3 \cdot x^1y^2 + 1 \cdot x^0y^3 \\ (x + y)^4 &= 1 \cdot x^4y^0 + 4 \cdot x^3y^1 + 6 \cdot x^2y^2 + 4 \cdot x^1y^3 + 1 \cdot x^0y^4 }

Как мы видим, коэффициенты совпадают с числами в треугольнике Паскаля.

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

(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} \, x^k \, y^{n-k} \quad\text{при}~ n \in \NN_0

Доказательство бинома Ньютона.

Мы раскрываем скобки в выражении

(x+y)^n = (x+y) \, (x+y) \, (x+y) \, \dotsm \, (x+y)

После раскрытия скобок, то есть после перемножения $n$ одинаковых двучленов, мы получаем сумму различных произведений $x$ и $y$ . При этом суммарная степень у каждого члене суммы получается $n$ .

Давайте разберемся, как появляется конкретный член $x^k \, y^{n-k}$ . Чтобы получился такой член, нам нужно ровно $k$ раз выбрать $x$ и, соответственно, $n-k$ раз выбрать $y$ из наших $n$ скобок.

Коэффициент перед этим членом $x^k \, y^{n-k}$ – это количество всех возможных способов выбрать, из каких именно $k$ скобок мы возьмем $x$ (а из оставшихся $n-k$ скобок автоматически будет взято $y$ ). Этот коэффициент по определению является биномиальным коэффициентом $\binom{n}{k}$ .

А поскольку $k$ у нас меняется в пределах от $0$ (во всех скобках выбрали $y$ ) до $n$ (во всех скобках выбрали $x$ ), получается, что

(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} \, x^k \, y^{n-k}

Вещественное обобщение

Формулу из определения биномиальных коэффициентов можно обобщить и на случай нецелых $n$

\binom{r}{k} \defeq \cases{ \displaystyle \frac{r^{\underline{k}}}{k!} = \prod\limits_{j=1}^k \frac{r+1-j}{j} & k \ge 0 \\ 0 & k < 0 }

При этом, для определенности, при $k < 0$ полагаем $\binom{r}{k} = 0$ .

Различные свойства и формулы применимы при разных условиях на переменные. Далее я буду писать переменные $n$ и $k$ , подразумевая, что они целые, а $r$ у меня будет действительной переменной.

Какие-то простые тождества можно доказать прямо по этому определению, аккуратно раскрывая нисходящую степень. Сложные тождества (например, свёртка Вандермонда) для доказательства будут требовать других техник, например разложение функций в ряды Тейлора или бесконечные биномиальные свёртки.

Биномиальная теорема. Давайте рассмотрим функцию $(x+y)^r$ при $x, y, r \in \CC$ и получим обобщение бинома Ньютона, называемое в народе биномиальной теоремой. В процессе я покажу всю технику, необходимую для конструирования строгих доказательств.

Для начала разложим в ряд Маклорена функцию $(1+z)^r$ для $z \in \CC$ . Для этого нужно получить общую формулу для $k$ -ой производной этой функции.

\frac{d^k}{dz^k} \bigl( (1+z)^r \bigr) = r^{\underline{k}} \cdot (1+z)^{r-k}

Тогда ряд Маклорена для $(1+z)^r$ выражается следующим образом

(1+z)^r = \sum\limits_{k=0}^\oo \frac{r^{\underline{k}}}{k!} \cdot z^k = \sum\limits_{k=0}^\oo \binom{r}{k} \, z^k

Коэффициенты этого ряда равны биномиальному коэффициенту. Ряд сходится в окрестности $0$ , а радиус сходимости $R$ можно найти с помощью признака Даламбера

R = \lim\limits_{k \to \oo} \left| \binom{r}{k+1} \middle/ \binom{r}{k} \right| = \lim\limits_{k \to \oo} \left| \frac{r-k}{k+1} \right| = 1

То есть внутри круга $|z| < 1$ ряд сходится к некоторой аналитической функции, которая по теореме единственности аналитических функций совпадает с нашей функцией $(1+z)^r$ .

(1+z)^r = \sum\limits_{k=0}^\oo \binom{r}{k} \, z^k \quad\text{при}~ z \;\! \in \;\! \CC ~\text{и}~ |z| < 1

Сделаем замену $z = x/y$ . Тогда мы получим функцию $(1 + x/y)^r$ , и, чтобы превратить её в желаемую функцию $(x+y)^r$ , надо её ещё умножить на $y^r$ . Итак, запишем с использованием найденного разложения.

(x+y)^r = y^r \cdot (1 + x/y)^r = y^r \cdot \sum\limits_{k=0}^\oo \binom{r}{k} \cdot \left( \frac{x}{y} \right)^k = \sum\limits_{k=0}^\oo \binom{r}{k} \, x^k \, y^{r-k}

Исходный ряд сходится при $|z| < 1$ , значит полученный ряд будет сходиться при $|x/y| < 1$ , то есть при $|x| < |y|$ . Можно поменять местами $x$ и $y$ , то есть сделать замену $z = y/x$ , и тогда мы получим аналогичный ряд. Итого

(x+y)^r = \sum\limits_{k=0}^\oo \binom{r}{k} \, x^k \, y^{r-k} \quad\text{при}~ x, y \;\! \in \;\! \CC ~\text{и}~ |x| < |y| \qquad (x+y)^r = \sum\limits_{k=0}^\oo \binom{r}{k} \, x^{r-k} \, y^k \quad\text{при}~ x, y \;\! \in \;\! \CC ~\text{и}~ |y| < |x|

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

Симметрия. Из определения получаем, что биномиальные коэффициенты симметричны в том смысле, что

\binom{n}{k} = \binom{n}{n-k}

Вынесение и внесение. Опять же, из определения можно вынести по одному члену и получить формулу

\binom{r}{k} = \frac{r}{k} \cdot \binom{r-1}{k-1}

Используя это свойство, можно получить два очень полезных факта, которые используются повсеместно

k \cdot \binom{r}{k} = r \cdot \binom{r-1}{k-1} \quad\text{и}\quad \frac{1}{r} \cdot \binom{r}{k} = \frac{1}{k} \cdot \binom{r-1}{k-1}

Применяя поочередно свойства внесения-вынесения и симметрии, можно получить еще одну формулу

r \cdot \binom{r-1}{k} = (r-k) \cdot \binom{r}{k}

Формула сложения. Используя несколько предыдущих свойств получаем одно из самых важных тождеств

\binom{r}{k} = \binom{r-1}{k} + \binom{r-1}{k-1}

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

Также эта формула показывает связь биномиальных коэффициентов с числами в треугольнике Паскаля. Элемент под номером $k$ в строке $n$ равен сумме его «родителей» под номерами $k$ и $k-1$ из строки $n-1$ .

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

\binom{r+n+1}{n} = \sum\limits_{k=0}^n \binom{r+k}{k} = \binom{r}{0} + \binom{r+1}{1} + \binom{r+2}{2} + \dotsb + \binom{r+n-1}{n-1} + \binom{r+n}{n}

Формула суммирования по верхнему индексу. Предыдущая формула выражает один биномиальный коэффициент в виде суммы других, верхний и нижний индексы которых остаются «равноудалёнными». Если раскладывать по-другому, чтобы нижний индекс сохранялся, то мы получим другую, не менее полезную формулу.

\binom{n+1}{m + 1} = \sum\limits_{k=0}^n \binom{k}{m} = \binom{0}{m} + \binom{1}{m} + \binom{2}{m} + \dotsb + \binom{n-1}{m} + \binom{n}{m}

Формула верхнего обращения. Она описывает связь между положительными отрицательными верхними индексами. Эта формула следует из определения, в котором каждый член числителя взяли с противоположным знаком и умножили весь числитель на $-1$ .

\binom{r}{k}=(-1)^k \cdot \binom{k-r-1}{k}

Простым следствием этой формулы является формула суммирования

\sum\limits_{k=0}^n (-1)^k \binom{r}{k} = \sum\limits_{k=0}^n \binom{k-r-1}{k} = \binom{-r+n}{n} = (-1)^n \binom{r-1}{n}

Ещё одну важную формулу можно получить, если взять целое $r = n$ и заменить $k = n - m$

\binom{n}{m} = (-1)^{n-m} \binom{-m-1}{n-m} \quad\text{где}~ n \ge 0

Из определения биномиальных коэффициентов можно получить довольно много важных тождеств, если выдёргивать из факториалов и нисходящих степеней разное количество членов. Давайте остановимся на особо важной формуле, которая позволяет нам менять местами нижние переменные в произведении биномиальных коэффициентов

\binom{r}{m} \cdot \binom{m}{k} = \binom{r}{k} \cdot \binom{r-k}{m-k}

Обратите внимание, что формула внесения-вынесения является частным случаем этой формулы при $k=1$ .

Некоторые полезные тождества

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

Для вашего удобства я буду сначала формулировать задачу, а потом приводить полное решение.

Двойное произведение.

\sum\limits_k k \, \binom{n}{k} \, \binom{m}{k} = \binom{n-m-1}{n-1} \cdot m \quad\text{для}~ n \ge 0

С помощью формулы внесения-вынесения избавляемся от множителя $k$ под суммой

\sum\limits_k k \, \binom{n}{k} \, \binom{m}{k} = \sum\limits_k \binom{n}{k} \, \binom{m-1}{k-1} \, m = m \cdot \sum\limits_k \binom{n}{k} \, \binom{m-1}{k-1}

Частичные суммы биномиального ряда. Давайте возьмём ряд, который возникал в биномиальной теореме, и обрежем его до $m \in \ZZ$ . Из этого мы можем получить ещё одну интересную формулу

\sum\limits_{k=0}^m \binom{m+r}{k} \, x^k \, y^{m-k} = \sum\limits_{k=0}^m \binom{-r}{k} \, (-x)^k \, (x+y)^{m-k}

Доказать эту формулу можно просто по индукции по $m$ .

При $m < 0$ обе части равны $0$ , а при $m = 1$ обе части равны $1$ .

Обозначим левую часть формулы за $S_m$ . Тогда, применив формулу сложения, получаем

\align{ S_m & = \sum\limits_{k=0}^m \binom{m+r}{k} \, x^k \, y^{m-k} = \sum\limits_{k=0}^m \binom{m-1+r}{k} \, x^k \, y^{m-k} + \sum\limits_{k=0}^m \binom{m-1+r}{k-1} \, x^k \, y^{m-k} = \\ &= \sum\limits_{k=0}^{m-1} \binom{m-1+r}{k} \, x^k \, y^{m-k} + \binom{m-1+r}{m} \, x^m + \sum\limits_{k=0}^m \binom{m-1+r}{k-1} \, x^k \, y^{m-k} = \\ &= y \cdot S_{m-1} + \binom{m-1+r}{m} \, x^m + x \cdot S_{m-1} = (x+y) \cdot S_{m-1} + \binom{-r}{m} \, (-x)^m }

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

Может показаться, что это тождество на практике бесполезно, ведь мы выразили одну сумму через другую, причём обе суммы в аналитическом виде не выражаются. Но иногда вычислить одну сумму гораздо проще другой.

Например, если положить $x=-1$ и $y=1$ , то можно получить интересный аналог формулы нижнего суммирования

\sum\limits_{k=0}^m \binom{m+r}{k} \, (-1)^k = \binom{-r}{m} \quad\text{для}~ m \in NN_0

А если положить $x=y=1$ и $r=m+1$ , то мы получим формулу

\sum\limits_{k=0}^m \binom{2m+1}{k} = \sum\limits_{k=0}^m \binom{m+k}{k} \, 2^{m-k}

В левой части находится сумма левой половины биномиальных коэффициентов с верхним числом $2m+1$ , а эти коэффициенты равны своим двойникам в правой половине, поскольку треугольник Паскаля симметричен. Значит, левая часть — это просто $1/2 \cdot 2^{2m+1} = 2^{2m}$ . И мы получаем совершенно неожиданную формулу

\sum\limits_{k=0}^m \frac{1}{2^k} \binom{m+k}{k} = 2^m

Свёртка Вандермонда

Одним из самых мощных и элегантных тождеств в комбинаторной алгебре является свёртка Вандермонда — тождество, связывающее сумму произведений биномиальных коэффициентов с одним биномиальным коэффициентом большего порядка.

Свёртка Вандермонда

Для любых $r, s \in \CC$ и целых $n, m \in \ZZ$

\sum\limits_k \binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}

Для начала стоит немного упростить сумму. Давайте произведем замену $k$ на $k-m$ и $n$ на $n-m$ . Тогда тождество свёртки Вандермонда преобразуется в

\sum\limits_k \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}

Теперь нам достаточно доказать это тождество, в котором фигурируют только три переменные вместо четырёх.

Давайте запишем биномиальную теорему для $(1+x)^r \cdot (1+x)^s$

(1+x)^r \cdot (1+x)^r = \left( \sum\limits_{k=0}^\oo \binom{r}{k} \, x^k \right) \cdot \left( \sum\limits_{m=0}^\oo \binom{s}{m} \, x^m \right) = \sum\limits_{n=0}^\oo \left( \sum\limits_k \binom{r}{k} \binom{s}{n-k} \right) \cdot x^n

С другой стороны, $(1+x)^r \cdot (1+x)^s = (1+x)^{r+s}$ , и

(1+x)^{r+s} = \sum\limits_{n=0}^\oo \binom{r+s}{n} \, x^n

Коэффициенты при $x^n$ в обоих частях должны совпадать, а значит

\sum\limits_k \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}

Отдельно приведу чисто комбинаторное доказательство для случая, когда $r, s \in \NN_0$ .

Предположим, у нас есть два непересекающихся конечных множества: множество мужчин $M$ , $|M| = r$ , и множество женщин $W$ , $|W| = s$ . Сколько существует способов выбрать группу из $n$ человек?

С одной стороны, это просто $\binom{r + s}{n}$ — выбираем из объединения. С другой — мы можем выбрать $k$ мужчин и $n - k$ женщин, где $k$ пробегает все допустимые значения. Число таких групп — $\binom{r}{k} \binom{s}{n - k}$ . Суммируя по $k$ , получаем левую часть.

Свёртку Вандермонда можно применять для нахождения значений самых диких сумм с биномиальными коэффициентами.

Ниже я приведу несколько важных тождеств с суммами, которые можно легко вывести с помощью свёртки Вандермонда.

Парная нижняя восходящая сумма

\sum\limits_k \binom{l}{m+k} \binom{s}{n+k} = \binom{l+s}{l-m+n} \quad\text{для}~ l \in \NN_0 ~\text{и}~ s \in \CC ~\text{и}~ n, m \in \ZZ

Для доказательства этого тождества достаточно заменить первый биномиальный коэффициент на $\binom{l}{l-m-k}$ и применить свёртку Вандермонда

\sum\limits_k \binom{l}{m+k} \binom{s}{n+k} = \sum\limits_k \binom{l}{l-m-k} \binom{s}{n+k} = \binom{l+s}{l-m+n}

Докажите, что

\sum\limits_k (-1)^k \, \binom{l}{m+k} \binom{s+k}{n} = (-1)^{l+m} \, \binom{s-m}{n-l} \quad\text{для}~ l \in \N_0 ~\text{и}~ s \in \CC ~\text{и}~ n, m \in \ZZ

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

Рассматривая разложение $(x+y)^n$ мы получали в качестве коэффициентов при члене $x^k \, y^{n-k}$ биномиальный коэффициент $\binom{n}{k}$ . Давайте рассмотрим степень не биноме, а полинома с $m$ переменными $(x_1 + x_2 + \dotsb + x_m)^n$ . Какие коэффициенты мы получим?

(x_1 + x_2 + \dotsb + x_m)^n = \sum\limits_{\substack{k_1, k_2, \dotsc, k_m \;\! \ge \;\! 0 \\ k_1 + k_2 + \dotsb + k_m = n}} \binom{n}{k_1 ~ k_2 ~ \cdots ~ k_m} \, x_1^{k_1} \, x_2^{k_2} \, \dotsm \, x_m^{k_m}

Мы получим мультиномиальные коэффициенты, которые, по аналогии с биномиальными, выражают количество способов выбрать из $n$ предметов ровно $k_1$ предмет типа $1$ , $k_2$ предметов типа $2$ , ..., $k_m$ предметов типа $m$ .

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

Для $n = k_1 + k_2 + \dotsc + k_m$ мультиномиальный коэффициент порядка $m$

\binom{n}{k_1 ~ k_2 ~ \cdots ~ k_m} \defeq \frac{n!}{k_1! \, k_2! \, \dotsm \, k_m!}

Мультиномиальные коэффициенты можно выразить через биномиальные

\binom{n}{k_1 ~ k_2 ~ k_3 ~ \cdots ~ k_m} = \binom{n}{k_1} \cdot \binom{n-k_1}{k_2} \cdot \binom{n-k_1-k_2}{k_3} \dotsm \binom{n-k_1-k_2-\dotsb-k_{m-1}}{k_m}

Давайте посмотрим на симметричную сумму

\sum\limits_k (-1)^k \, \binom{a+b}{a+k} \binom{b+a}{b+k} = \frac{(a+b)!}{a! \, b!} = \binom{a+b}{a ~ b}

Увеличим количество переменных до трёх. Новая сумма

\sum\limits_k (-1)^k \, \binom{a+b}{a+k} \binom{b+c}{b+a} \binom{c+a}{c+k} = \frac{(a+b+c)!}{a! \, b! \, c!} = \binom{a+b+c}{a ~ b ~ c}

Далее, для четырёх переменных удобно записать сумму по парам не получится, и придётся суммировать по нескольким индексам

\sum\limits_{i, \- j, \- k} (-1)^{i+j+k} \, \binom{a+b}{b+i} \binom{a+c}{c+j} \binom{b+c}{c+k} \binom{a+d}{d-i-j} \binom{b+d}{d+i-k} \binom{c+d}{d+j+k} = \binom{a+b+c+d}{a ~~ b ~~ c ~~ d}

Обобщением на случай $n$ переменных выступает очень страшная формула Дайсона. Фриман Дайсон в 1962 году высказал предположение об верности этой формулы, и вскоре эта формула была доказана несколькими исследователями.

Сумма Дайсона для мультиномиальных коэффициентов

Для $n$ переменных $a_1, a_2, \dotsc, a_n \in \NN_0$

\sum\limits_{\substack{k_{i, \- j} \;\! \ge \;\! 0 \\ 1 \;\! \le \;\! i < j < n}} (-1)^{\sum\limits_{1 \;\! \le \;\! i < j < n} k_{i, \- j}} \, \prod\limits_{1 \;\! \le \;\! i < j < n} \binom{a_i + a_j}{a_j + k_{i, \- j}} \cdot \left( \prod\limits_{1 \;\! \le \;\! j < n} \bigbinom{a_j + a_n}{a_n + \sum\limits_{i=1}^{j-1} k_{i, \- j} - \sum\limits_{i=j+1}^n k_{j, \- i} } \right)

Суммирование производится по всем $\binom{n-1}{2}$ индексным переменным $k_{i, \- j}$ для $1 \le i < j < n$ .

Биномиальные последовательности

Давайте вспомним бином Ньютона

(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} \, x^k \, y^{n-k}

Эта формула описывает, как ведут себя обычные степени $x^n$ при сложении аргументов. Но что, если мы рассмотрим другие последовательности многочленов? Оказывается, существует целый класс последовательностей многочленов, которые ведут себя почти как степени — они удовлетворяют аналогичному биномиальному тождеству, но с заменой $x^k$ на другие многочлены. Такие последовательности называются биномиальными.

Биномиальные последовательности многочленов

Последовательность многочленов $p_0(x), \- p_1(x), \- p_2(x), \- \dotsc$ называется биномиальной, если

нормировка — $p_0(x) = 1$
$\deg p_n(x) = n$ и старший коэффициент многочлена $p_n(x)$ равен $[x^n] p_n(x) = 1$
для всех $n \in \NN_0$ выполняется биномиальное тождество
$p_n (x+y) = \sum\limits_{k=0}^n \binom{n}{k} \cdot p_k(x) \cdot p_{n-k}(y)$

Обычные многочлены $p_n(x) = x^n$ действительно образуют биномиальную последовательность. Первые два свойства, очевидно, выполняются, а третье — это в точности бином Ньютона.

Настоящая магия начинается, когда мы обнаруживаем, что существуют и другие последовательности с таким свойством. Например нисходящие степени $x^{\underline{n}}$ , восходящие степени $x^{\overline{n}}$ , многочлены Абеля $A_n(x) = x \, (x - an)^{n-1}$ .

Все эти последовательности удовлетворяют тому же биномиальному тождеству, что и обычные степени. Это означает, что структура бинома Ньютона — не уникальное свойство степеней, а более общий феномен, который проявляется во многих математических объектах.

Зачем вся эта прелесть нужна?

Биномиальные последовательности возникают в самых разных областях математики: в комбинаторике они описывают различные структуры на множествах; в теории вероятностей связаны с определёнными распределениями; в алгебре представляют естественные базисы в пространствах многочленов; в теории операторов соответствуют специальным дифференциальным операторам.

Изучение биномиальных последовательностей привело к созданию целого раздела математики — теневого исчисления (umbral calculus), который предоставляет мощные методы для работы с биномиальными и подобными последовательностями, а так же открывает возможность работать со сложными задачами, для решения которых стандартных методов было недостаточно.

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

Давайте вместо работы с отдельными многочленами $p_n (x)$ перейдём к их экспоненциальной производящей функции

P(x, t) = \sum\limits_{n=0}^\oo p_n(x) \cdot \frac{t^n}{n!}

Давайте умножим биномиальное тождество на $t^n/n!$ и просуммируем по всем $n$

\sum\limits_{n=0}^\oo p_n(x+y) \cdot \frac{t^n}{n!} = \sum\limits_{n=0}^\oo \sum\limits_{k=0}^n \binom{n}{k} \cdot p_k(x) \cdot p_{n-k}(y) \cdot \frac{t^n}{n!}

Правая часть — это просто $P(x+y, t)$ . А левая часть после перестановки суммирования превращается в произведение

\left( \sum\limits_{k=0}^\oo p_k(x) \cdot \frac{t^k}{k!} \right) \cdot \left( \sum\limits_{m=0}^\oo p_m(y) \cdot \frac{t^m}{m!} \right) = P(x, t) \cdot P(y, t)

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

P(x+y, t) = P(x, t) \cdot P(y, t)

А это уравнение уже легко решается. При фиксированном $t$ и естественных условиях регулярности решение этого функционального уравнения имеет вид

P(x, t) = e^{x \, c(t)}

где $c(t) = c_0 + c_1 \, t + c_2 \, t^2 + \dotsb$ — какой-то формальный степенной ряд по $t$ .

Чтобы $p_0 (x) = 1$ для всех $x$ , нужно, чтобы свободный член ряда $c(t)$ был равен $0$ . Также, чтобы старший коэффициент многочлена $p_n(x)$ был равен $1$ , нужно, чтобы $c_1 = 0$ . Получается, что

c(t) = t + c_2 \, t^2 + c_3 \, t^3 + \dotsb

Итак, мы получили мощную теорему, описывающую все биномиальные последоательности многочленов.

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

Последовательность многочленов $p_0(x), \- p_1(x), \- p_2(x), \- \dotsc$ является биномиальной тогда и только тогда, когда её экспоненциальная производящая функция равна экспоненте, то есть

\sum\limits_{n=0}^\oo p_n(x) \cdot \frac{t^n}{n!} = e^{x \, c(t)}

где $c(t) = t + c_2 \, t^2 + c_3 \, t^3 + \dotsb$ — формальный степенной ряд по $t$ .

Этот фундаментальный результат, восходящий к работам Джона Блиссара и Эдуарда Лукаса в XIX веке, показывает, что каждая биномиальная последовательность полностью определяется своей тенью — формальным степенным рядом $c(t)$ . Именно эта характеристика позволила систематически изучать все биномиальные последовательности одновременно и заложила основы современного теневого исчисления.

Теперь давайте применим эту теорему и получим полезные формулы для разных биномиальных последовательностей.

Обычные степени. $p_n(x) = x^n$ .

\sum\limits_{n=0}^\oo x^n \cdot \frac{t^n}{n!} = e^{xt} \quad\text{и здесь}~ c(t) = t

Нисходящие степени. $p_n(x) = x^{\underline{n}}$ .

\sum\limits_{n=0}^\oo x^{\underline{n}} \cdot \frac{t^n}{n!} = (1+t)^x = e^{x \cdot \ln (1+t)} \quad\text{и здесь}~ c(t) = \ln (1+t)

Восходящие степени. $p_n(x) = x^{\overline{n}}$ .

\sum\limits_{n=0}^\oo x^{\overline{n}} \cdot \frac{t^n}{n!} = (1-t)^{-x} = e^{-x \cdot \ln (1+t)} \quad\text{и здесь}~ c(t) = - \ln (1-t)

Многочлены Абеля. $p_n(x) = x \, (x-an)^{n-1}$ .

\sum\limits_{n=0}^\oo x \, (x-an)^{n-1} \cdot \frac{t^n}{n!} = e^{x \cdot W(at)/a} \quad\text{и здесь}~ c(t) = \frac{W(at)}{a}

Далее, записывая биномиальное тождество для каждых последовательностей, получаем аналоги бинома Ньютона.

Альфредо Капелли в 1887 году открыл тождество для восходящих степеней в рамках работ по комбинаторике и символьным методам.

(x+y)^{\overline{n}} = \sum\limits_{k=0}^n \binom{n}{k} \, x^{\overline{k}} \, y^{\overline{n-k}}

С нисходящими степенями всё гораздо проще, ведь они естественно возникают в исчислении конечных разностей, поэтому они появлялись в трудах Якова Бернулли, Исаака Ньютона и других математиков.

(x+y)^{\underline{n}} = \sum\limits_{k=0}^n \binom{n}{k} \, x^{\underline{k}} \, y^{\underline{n-k}}

Нильс Хенрик Абель в 1826 году открыл биномиальное тождество для многочленов Абеля при работе над доказательством неразрешимости уравнений в радикалах

(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} \, x \, (x-ak)^{k-1} \, (y+ak)^{n-k}

Тождество Абеля является обобщением бинома Ньютона. Его можно использовать для решения самых разных комбинаторных задач.

Пусть $A_n(x) = x \, (x+n)^{n-1}$ — многочлен Абеля при $a = -1$ . Запишем для него биномиальное тождество.

A_n(x+y) = \sum\limits_{k=0}^n \binom{n}{k} \cdot A_k(x) \cdot A_{n-k}(y)

Продифференцируем его по $x$ и по $y$

A_n''(x+y) = \sum\limits_{k=0}^n \binom{n}{k} \cdot A_k'(x) \cdot A_{n-k}'(y)

Производная многочлена Абеля равна $A_m'(x) = m \, (x+1) \, (x+m)^{m-2}$ .
И вторая производная при $n \ge 2$ равна $A_n''(x) = n \, (n-1) \, (x+2) \, (x+n)^{n-3}$ .

Подставим $x=0$ и $y=0$ в дважды продифференцированное биномиальное тождество. Также сразу подставим значения $A_m'(0) = m^{m-1}$ и $A_n''(0) = 2 \, (n-1) \, n^{n-2}$

2 \, (n-1) \, n^{n-2} = \sum\limits_{k=1}^{n-1} \binom{n}{k} \cdot k^{k-1} \cdot (n-k)^{n-k-1}

Заменив $n-k$ на $m$ и переписав сумму, получаем формулу

2 \, (n-1) \, n^{n-2} = \sum\limits_{\substack{k, m \;\! \ge \;\! 1 \\ k + m = n}} \binom{n}{k} \cdot k^{k-1} \cdot m^{m-1}

Полученное тождество имеет комбинаторный смысл в контексте деревьев. Посмотрите внимательно на формулу. В левой части написано количество ориентированных рёбер во всех деревьях на $n$ помеченных вершинах. В правой части написано количество способов построить два подвешенных дерева, соединённых ориентированным ребром между корнями. Каждому ориентированному ребру соответствует разбиение на два подвешенных дерева. Вот мы и построили биекцию между двумя величинами.

Поделив обе части на $2 \, (n-1)$ можно получить формулу для количества свободных деревьев.

n^{n-2} = \frac{1}{2 \, (n-1)} \sum\limits_{\substack{k, m \;\! \ge \;\! 1 \\ k + m = n}} \binom{n}{k} \cdot k^{k-1} \cdot m^{m-1}

Для биномиальной последовательности верно мультиномиальное тождество

p_n (x_1 + x_2 + \dotsc + x_k) = \sum\limits_{m_1 + m_2 + \dotsc + m_k = n} \binom{n}{m_1 ~ m_2 ~ \cdots ~ m_k} \cdot p_{m_1}(x_1) \, p_{m_2}(x_2) \dotsm \, p_{m_k}(x_k)

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

Эдуард Люка, исследуя свойства разных комбинаторных объектов, обнаружил ещё один аналог биномиальных коэффициентов, достаточно специфичный, но не менее интересный.

Вместо обычных чисел в произведении он рассматривал числа Фибоначчи.

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

Фибономиальный коэффициент — число

\fbinom{n}{k} \defeq \frac{F_{n} \, F_{n-1} \, F_{n-2} \, \dotsm \, F_{n-k+2} \, F_{n-k+1}}{F_k \, F_{k-1} \, F_{k-2} \, \dotsm \, F_2 \, F_1} = \prod\limits_{j=1}^k \frac{F_{n-k+j}}{F_j}

Из определения можно получить аналог формулы сложения для биномиальных коэффициентов. Эта формула служит основной рекуррентной формулой фибономиальных коэффициентов.

\fbinom{n}{k} = F_{k-1} \cdot \fbinom{n-1}{k} + F_{n-k+1} \cdot \fbinom{n-1}{k-1}