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

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

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

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

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

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

Давайте сразу определимся с обозначениями. Правильное обозначение для биномиальных коэффициентов не , как учат в российских школах (и в университетах), а $\binom{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)ⁿ в ряд согласуется с формулой Тейлора, в соответствие с которой коэффициент, стоящий при z^k равен

$\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}$