Расширенные биномиальные коэффициенты

В данном очень важном приложении речь пойдёт о биномиальных коэффициентах, точнее, об их расширении на случай произвольных значений верхнего индекса. Иногда такая тема в литературе называется «расширенный треугольника Паскаля», поскольку расширение биномиальных коэффициентов влечёт за собой расширение треугольника Паскаля, который из этих коэффициентов состоит, а также рассматриваемая здесь функция (1+z)n (точнее, её разложение в ряд) называется биномиальным рядом.

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

Основные определения

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

Биномиальный коэффициент обозначается символом $\binom{n}{k}$, или (что часто встречается в русской литературе) $C_n^k$.

Давайте сразу определимся с обозначениями. Правильное обозначение для биномиальных коэффициентов не $C_n^k$, как учат в российских школах (и в университетах), а $\binom{n}{k}$. К сожалению, я не знаю, по какой причине в России чаще используется обозначение $C_n^k$, а в остальном Мире — $\binom{n}{k}$. Поэтому учтите, что если вы пишите статью для российских журналов, вас поймут, как бы вы эти коэффициенты не обозначили, а для зарубежных журналов советую писать правильно.

Читается этот символ разными способами: «число сочетаний из n по k», или просто «из n по k», а также говорят «выбор k из n». Смысл указанных выражений заключён в комбинаторной интерпретации этого символа — это число способов выбрать k объектов из n различных объектов, причём порядок выбора не важен. Например, из множества {1,2,3,4,5} можно выбрать два элемента десятью способами:

\begin{displaymath}
\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}.
\end{displaymath}

Таким образом,

\begin{displaymath}
\binom{5}{2} = 10.
\end{displaymath}

В общем случае известно, что

\begin{displaymath}
\binom{n}{k}=\frac{n!}{k!(n-k)!}.
\end{displaymath}

В процессе вычислений, чтобы не считать лишние факториалы, можно сразу часть множителей сократить:

\begin{displaymath}
\binom{n}{k}=\frac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\mbox{\small {} множителей}}}{k!}.
\end{displaymath}

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

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

В XVII веке французский математик, физик, философ Блез Паскаль впервые в своем «трактате об арифметическом треугольнике» наиболее полно рассказал о свойствах этого самого треугольника (хотя сам треугольник встречался в работах других математиков задолго до Паскаля).

Строится этот замечательный треугольник очень просто:

\begin{displaymath}\begin{array}{ccccccccccccc}
& & & & & &1& & & & & & \\
...
...\ldots& &\ldots& &\ldots& &\ldots& &\ldots \\
\end{array}
\end{displaymath}

По краям треугольника ставятся единицы, а любое число, стоящее не с краю, вычисляется как сумма двух чисел, расположенных сверху слева и сверху справа от него. Например, 10=4+6, или 3=1+2. Итак, речь зашла о треугольнике Паскаля в связи с тем, что он как раз образован биномиальными коэффициентами:

\begin{displaymath}\begin{array}{ccccccccccccc}
& & & & & &\binom{0}{0}& & & &...
...\ldots& &\ldots& &\ldots& &\ldots& &\ldots \\
\end{array}
\end{displaymath}

Для наших целей (и для удобства) лучше записывать треугольник, выравнивая его по левому краю:

\begin{displaymath}
\begin{tabular}{\vert r\vert rrrrrrr\vert}
\hline
\ma...
...$&$1$&$5$&$10$&$10$&$5$&$1$&$0$ \\
\hline
\end{tabular}
\end{displaymath}

Нули появляются за счёт нуля в числителе (когда k>n). Заметьте, что в нулевом столбце ставятся единицы, так как

\begin{displaymath}
\binom{n}{0}=\frac{1}{0!}=1.
\end{displaymath}

В числителе стоит произведение нулевого числа элементов, которое по определению равно 1. Данная формула верна для любого (в том числе, комплексного) n.

Ну вот, мы уже приближаемся к тому, чтобы изучить биномиальные коэффициенты для любого n. Наше расширение, во-первых, должно быть таким, чтобы формула осталась прежней (для удобства), во-вторых, треугольник Паскаля, образованный биномиальными коэффициентами (с целым отрицательным значением индекса), не должен потерять своё основное свойство:

\begin{displaymath}
\binom{n\makebox[0pt]{\phantom{1}}}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},
\end{displaymath}

оно гласит, что число в клетке (n,k) равно сумме верхнего числа и верхнего левого (когда числа выровнены по левому краю).

В-третьих (что самое важное), должна остаться справедливой биномиальная теорема, утверждение которой напоминается в следующем пункте.

Биномиальная теорема

Содержание данной теоремы в классической формулировке известно еще из средних классов школы:

\begin{displaymath}
(a+b)^n = \sum_{k=0}^{n}\binom{n}{k} a^kb^{n-k}, \quad n\geq 0, \mbox{ целое}.
\end{displaymath}

Это выражение также носит название бином Ньютона. Коэффициенты бинома Ньютона и называются биномиальными коэффициентами.

Теперь, пользуясь биномом Ньютона и треугольником Паскаля, можно посчитать, например (взяв третью строчку треугольника),

\begin{displaymath}
(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3.
\end{displaymath}

Данный сайт посвящён производящим функциям, поэтому нас данная теорема интересует лишь с этой позиции. Запишем производящую функцию в следующем виде:

\begin{displaymath}
(1+z)^n = \sum_{k=0}^{n}\binom{n}{k} z^k, \quad n\geq 0, \mbox{ целое}.
\end{displaymath}

Представленная производящая функция генерирует последовательность биномиальных коэффициентов с верхним индексом, равным n. Верхний индекс в сумме можно записать равным , это ничего не меняет, когда n целое неотрицательное (почему?). Обратите внимание, что подстановка z=1 даёт замечательное тождество (ряд конечный, поэтому подстановка справедлива):

\begin{displaymath}
\sum_{k=0}^{n}\binom{n}{k} = 2^n, \quad n\geq 0, \mbox{ целое},
\end{displaymath}

которое показывает, что сумма всех чисел в n-й строке треугольника Паскаля равняется двойке, возведённой в степень n.

Данное разложение функции (1+z)n в ряд согласуется с формулой Тейлора, в соответствие с которой коэффициент, стоящий при zk равен

\begin{displaymath}
\frac{1}{k!}\left.\frac{d^k}{dz^k}f(z)\right\vert _{z=0} =
\frac{1}{k!}n(n-1)(n-2)\cdots(n-k+1)=\binom{n}{k}.
\end{displaymath}

Напомню, что для этой функции ряд Тейлора сходится при |z|<1 (когда n произвольно). Эта функция также носит название «Биномиальный ряд».

Расширение

Теперь нас интересует ответ на вопрос: можно ли допустить в биномиальной теореме, чтобы n было целым отрицательным? Можно, причём треугольник Паскаля расширяется «вверх» единственным образом, если мы хотим сохранить его основное свойство:

\begin{displaymath}
\binom{n\makebox[0pt]{\phantom{1}}}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},
\end{displaymath}

при этом $\binom{n}{0}=1$. Рассмотрим отрицательные строчки подробнее:

\begin{displaymath}
\begin{tabular}{\vert r\vert rrrrrrr\vert}
\hline
\ma...
...$2$&$1$&$2$&$1$&$0$&$0$&$0$&$0$ \\
\hline
\end{tabular}
\end{displaymath}

Например, минус первая строка треугольника может быть только такой, и никакой иначе, поскольку $\binom{-1}{0}=1$, а остальные элементы вычисляются однозначно:

\begin{displaymath}
\binom{-1}{k}=\binom{0}{k}-\binom{-1}{k-1}, \quad k\geq1.
\end{displaymath}

Для чего нужны расширенные биномиальные коэффициенты? Для того, чтобы раскладывать в ряд простые дроби. Например,

\begin{displaymath}
\frac1{1+z}=(1+z)^{-1}=\sum_{k=0}^{\infty}\binom{-1}{k}z^k=
\sum_{k=0}^{\infty}(-1)^kz^k.
\end{displaymath}

Поэтому, кстати (читайте о разложении 1/(1−z)),

\begin{displaymath}
\frac1{1-z}=(1-z)^{-1}=\sum_{k=0}^{\infty}\binom{-1}{k}(-z)^k=
\sum_{k=0}^{\infty}z^k.
\end{displaymath}

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

\begin{displaymath}\displaylines{
\ig{0.2}\binom{-n}{k}=\frac{(-n)(-n-1)\cdots...
...n(n+1)\cdots(n+k-1)}{k!}=(-1)^k\binom{n+k-1}{k}.\ig{0.2}
}
\end{displaymath}

Таким образом,

\begin{displaymath}
\frac1{(1+z)^n}=(1-z)^{-n}=
\sum_{k=0}^{\infty}\binom{-n}{k}z^k=
\sum_{k=0}^{\infty}(-1)^k\binom{n+k-1}{k}z^k.
\end{displaymath}

Данная формула также согласуется с разложением этой функции в ряд Тейлора для |z|<1.

Пойдём дальше. На практике могут пригодиться рациональные показатели степени, например, рассмотрим биномиальный ряд для n=1/2:

\begin{displaymath}\begin{array}{rcl}
\displaystyle\binom{1/2}{k}&{}={}&\displ...
...c{(-1)^{k-1}}{(2k-1)4^k}\cdot\binom{2k}{k}.\\
\end{array}
\end{displaymath}

Эта формула даёт нам возможность раскладывать в ряд функцию

\begin{displaymath}\displaylines{
\ig{0.2}\sqrt{1+z}=\sum_{k=0}^{\infty}\binom...
...8}z^4+\frac7{256}z^5-\frac{21}{1024}z^6+ o(z^7).\ig{0.2}
}
\end{displaymath}

Аналогично (мы оставляем подробный вывод читателю),

\begin{displaymath}
\binom{-1/2}{k} = \frac{(-1)^k}{4^k}\binom{2k}{k},
\end{displaymath}

а это, в свою очередь, позволяет записать ещё одну полезную производящую функцию:

\begin{displaymath}\displaylines{
\ig{0.2}\frac{1}{\sqrt{1+z}}=\sum_{k=0}^{\in...
...-\frac{63}{256}z^5+\frac{231}{1024}z^6 + o(z^7).\ig{0.2}
}
\end{displaymath}