Введение

Общие абстрактные представления

Традиционно разговор о производящих функциях начинают с определения формального степенного ряда

\begin{displaymath}
G(z)=\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots,
\end{displaymath}

порождающего (производящего) последовательность (a0, a1, a2, ...). Однако такое изложение не даёт понимания того, почему ряд выбран именно в таком виде и что собственно означает символ z. После такого определения становится непонятным, почему различные математические манипуляции с таким рядом являются законными, когда нигде не идёт речь о его сходимости.

Такое абстрактное соответствие между некоторой последовательностью (an) и рядом, составленным из коэффициентов этой последовательности, обычно выражается словами «последовательность генерируется производящей функцией», «производящая функция генерирует (порождает, производит) последовательность», или математическими формулами вида

\begin{displaymath}
(a_0, a_1, a_2, \ldots)
\quad
\leftrightarrow
\quad
a_0+a_1z+a_2z^2+\cdots,
\end{displaymath}

Начиная разговор о производящих функциях, необходимо отметить, что это, в первую очередь, символьная конструкция, то есть вместо z может быть какой угодно объект, для которого определены операции сложения и умножения. Самое важное при работе с производящими функциям — преодолеть сложившийся в процессе изучения теории числовых рядов стереотип о том, что в зависимости от значения числа z (считая, что это может быть только число) ряд может сходиться или расходиться, поэтому, скажем, интегрировать или дифференцировать такой ряд не всегда возможно. На самом деле метод бесконечных сумм обладает гораздо бóльшими возможностями, которые обнаруживаются при использовании производящих функций, и совершенно не обязательно смотреть на z как на число и придавать ему свойства числа, хотя иногда это делать придётся.

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

Задача о расстановке
чёрных и белых шаров

Сколькими различными способами можно расположить в линию чёрные и белые шары, общее количество которых равно n? В этой задаче есть один параметр — это общее число шаров n. Решением такого рода комбинаторных задач считается формула (или какой-либо эффективный алгоритм), позволяющая получить ответ для любого заданного n (в данном случае n≥0). Этот ответ будем обозначать символом an.

Обозначим белый шар символом Б, а чёрный — Ч. Любое расположение шаров можно записать в виде последовательности этих символов Б и Ч. Нулевое количество шаров будем обозначать $\varnothing $. При решении комбинаторных задач с параметром, если ответ не очевиден, необходимо пытаться получить его для небольших значений этого параметра. Например, при n=2 найдется всего 4 способа: ББ, БЧ, ЧБ и ЧЧ. При n=1 таких способов два: Б и Ч.

Что делать, когда n=0? Единственный способ не располагать в линию ничего — это ничего не делать, причём ничего не делать можно одним способом. Если угодно, такое решение задачи с нулевым количеством шаров можно считать договором, который в будущем, когда мы получим общие представления о решении задачи, должен согласоваться с этими общими представлениями. Достаточно удобно считать, что отсутствие чего-то можно наблюдать одним способом.

Действительно, в математике существует много таких примеров, когда нужно выполнить действие с нулевым количеством объектов. Например, число перестановок n различных объектов равно n!, при этом 0!=1 (ничего не переставлять можно одним способом). Число способов выбрать k объектов из n различных есть число сочетаний $\binom{n}{k}$, причём $\binom{n}{0}=1$ (ничего не выбрать можно одним способом).

Рассмотрим случай n=3. В этом случае можно взять самый левый шар белым, и закончить комбинацию Б⋅⋅ четырьмя способами, а можно взять его чёрным, закончив комбинацию Ч⋅⋅ также четырьмя способами. Значит a3=2a2. Рассуждая аналогично, приходим к выводу, что an=2an-1 (для n≥1), это означает, что an=2n.

Ответом к поставленной задаче являются степени числа 2: 1, 2, 4, 8, 16, .... Заметьте, что наш договор о том, что a0=1. согласуется с полученной формулой. Действительно, 20=1.

Производящая функция

Причем здесь производящие функции? «Просуммируем» все возможные комбинации (включая пустую) следующим образом:

\begin{displaymath}
A = \varnothing + \mbox{\texttt{Б}}+ \mbox{\texttt{Ч}}+ \m...
... \mbox{\texttt{Б}}\mbox{\texttt{Б}}\mbox{\texttt{Б}}+ \cdots
\end{displaymath}

Вопрос о справедливости такой запись сейчас для нас не важен (вся строгость таких манипуляций может быть доказана). Сейчас нам важно выйти за рамки привычных арифметических представлений, когда кажется что складывать или перемножать можно только числа (или векторы). Здесь мы будем складывать и перемножать последовательности шаров. Сложение последовательностей в этой сумме вполне понятно — «суммируются» все допустимые способы, причем каждый по одному разу. Что означает умножение? Интуитивно понятно, что расположения шаров можно перемножать. Так, перемножив БЧ и ЧБ, мы получим БЧЧБ, но обратите внимание на то, что операция умножения здесь некоммутативна (Б⋅Ч ≠ Ч⋅Б), так как перемножение тех же разбиений в другом порядке может дать другое разбиение: ЧБ⋅БЧ=ЧББЧ. Отметим, что пустое разбиение $\varnothing $ в операции умножения играет роль мультипликативной единицы, например, ЧБ⋅$\varnothing $=$\varnothing $⋅ЧБ=ЧБ.

Теперь проведём с «рядом» A последовательность арифметических манипуляций:

\begin{displaymath}\displaylines{
A = \varnothing + \mbox{\texttt{Б}}+ \mbox{\...
...g + \mbox{\texttt{Б}}\cdot A + \mbox{\texttt{Ч}}\cdot A.
}
\end{displaymath}

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

Разрешив уравнение относительно A, получим

\begin{displaymath}\displaylines{
(\varnothing -\mbox{\texttt{Б}}-\mbox{\textt...
...ing }{\varnothing -\mbox{\texttt{Б}}-\mbox{\texttt{Ч}}}.
}
\end{displaymath}

Вспомним формулу для суммы геометрической прогрессии:

\begin{displaymath}
\frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots.
\end{displaymath}

Заменив Б + Ч на x, а $\varnothing $ на 1, получим

\begin{displaymath}
A = \frac{\varnothing }{\varnothing -\mbox{\texttt{Б}}-\mb...
... \sum_{n=0}^{\infty}(\mbox{\texttt{Б}}+\mbox{\texttt{Ч}})^n.
\end{displaymath}

В этой сумме также учтены все возможные разбиения в точности по одному разу. Например, разбиение ББЧБ встречается в (Б+Ч)4, а $\varnothing $ есть ни что иное как (Б+Ч)0. Далее воспользуемся формулой, известной как бином Ньютона (не заботясь о справедливости её применения):

\begin{displaymath}
(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}.
\end{displaymath}
\begin{displaymath}
A = \sum_{n=0}^{\infty}(\mbox{\texttt{Б}}+\mbox{\texttt{Ч}...
...}^{n}\binom{n}{k}\mbox{\texttt{Б}}^k\mbox{\texttt{Ч}}^{n-k}.
\end{displaymath}

Коэффициент при БkЧn−k, равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров Б и Ч, содержащих Б в количестве k и Ч в количестве n−k. Таким образом, общее число расположений n шаров (не важно каких сколько) есть сумма по всем возможным значениям k:

\begin{displaymath}
a_n = \sum_{k=0}^{n} \binom{n}{k}=2^n.
\end{displaymath}

Связь с определением

По определению производящая функция имеет вид:

\begin{displaymath}
G(z)=\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots.
\end{displaymath}

В нашей задаче не важно, какой шар на каком месте стоит, важно, что их общее количество равно n. По этой причине можно законно заменить оба символа — Ч и Б — одной буквой z и записать равенство:

\begin{displaymath}
A = \sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}\mbox{\te...
...{n-k} =
\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}z^n.
\end{displaymath}

Теперь очень хорошо видно в чём связь последней суммы с исходным определением производящей функции. Коэффициент, стоящий при zn, равен значению an (по исходному определению) и равен сумме всех биномиальных коэффициентов (как мы только что получили). Поэтому справедливо записать

\begin{displaymath}
a_n = \sum_{k=0}^{n} \binom{n}{k}=2^n.
\end{displaymath}

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

\begin{displaymath}
A = \frac{\varnothing }{\varnothing -\mbox{\texttt{Б}}-\mb...
...nothing -z-z}=
\frac{1}{1-2z}=1+(2z)+(2z)^2+(2z)^3+\cdots,
\end{displaymath}

откуда видно, что коэффициент, стоящий при zn, равен 2n.

Задача о некоммутативном разбиении

Как велико количество an способов представить неотрицательное целое число n в виде суммы чисел 1 и 2? Причём способы, отличающиеся перестановкой слагаемых, считаются различными (то есть 3=1+2 и 3=2+1 — разные способы; именно поэтому разбиение называется некоммутативным). Как и в предыдущей задаче, здесь есть один параметр — это число n, поэтому сначала научимся решать задачу для небольших значений n. Например, при n=3 можно получить 3 суммы: 3=1+1+1, 3=1+2 и 3=2+1. При n=2 имеются всего две суммы: 2=1+1 и 2=2. Когда n=1 есть всего один вариант разбиения на одно слагаемое, равное 1.

Возникает интуитивное подозрение, что an=n, но оно становится ошибочным уже при n=0. Что происходит в этом случае? Единственный способ представить число 0 в виде суммы слагаемых 1 и 2 — это не брать эти слагаемые совсем, причём сделать это можно одним способом (см. аналогичное замечание в предыдущей задаче).

Рассмотрим ещё одно значение n=4. В этом случае можно либо взять самое левое из слагаемых равным 1, либо — равным 2. Тогда в первом случае разбиение числа 4=1+⋅⋅⋅ можно завершить a3 способами, а во втором — разбиение числа 4=2+⋅⋅⋅ можно завершить a2 способами, поэтому a4=a3+a2=5. Рассуждая аналогично, получим, что an=an-1+an-2 (для n≥2). Таким образом, мы случайно решили задачу (предложив рекуррентное соотношение для an), исходя из чисто комбинаторных рассуждений.

Ответом к поставленной задаче являются числа Фибоначчи: 1, 1, 2, 3, 5, 8, .... Традиционно числа Фибоначчи начинаются от 0: f0=0, f1=1 и fn=fn-1+fn-2 (для n≥2), поэтому ответом к нашей задаче с заданным параметром n является (n+1)-e число Фибоначчи: an=fn+1.

Производящая функция

Каким образом здесь появляются производящие функции? Представим наши слагаемые 1 и 2, на которые нужно разбить число n, с помощью символов $\mbox{\ding{192}}$ и $\mbox{\ding{193}}$. Любое разбиение можно записать в виде последовательности этих символов. Так, если n=1+2+2+1+1, можно записать $\mbox{\ding{192}}$$\mbox{\ding{193}}$$\mbox{\ding{193}}$$\mbox{\ding{192}}$$\mbox{\ding{192}}$. Символ $\mbox{$\not\!\mathbf{0}$}$ будет играть роль нулевого количества слагаемых. Теперь запишем все возможные способы разбить числа n≥2 на сумму слагаемых $\mbox{\ding{192}}$ и $\mbox{\ding{193}}$:

\begin{displaymath}
A = \mbox{$\not\!\mathbf{0}$}+ \mbox{\ding{192}}+ \mbox{\d...
...\mbox{\ding{193}}+ \mbox{\ding{193}}\mbox{\ding{192}}+\cdots
\end{displaymath}

Обратим внимание на то, что операция умножения здесь снова некоммутативна ($\mbox{\ding{192}}$$\mbox{\ding{193}}$$\mbox{\ding{193}}$$\mbox{\ding{192}}$), Пустое разбиение $\mbox{$\not\!\mathbf{0}$}$ в операции умножения играет роль единицы, например, $\mbox{$\not\!\mathbf{0}$}$$\mbox{\ding{192}}$$\mbox{\ding{193}}$=$\mbox{\ding{192}}$$\mbox{\ding{193}}$$\mbox{$\not\!\mathbf{0}$}$=$\mbox{\ding{192}}$$\mbox{\ding{193}}$.

Снова попытаемся свести «ряд» к самому себе:

\begin{displaymath}\displaylines{
A = \mbox{$\not\!\mathbf{0}$}+ \mbox{\ding{1...
...\!\mathbf{0}$}+ \mbox{\ding{192}}A + \mbox{\ding{193}}A.
}
\end{displaymath}

Разрешив уравнение относительно A, получим

\begin{displaymath}
A = \frac{\mbox{$\not\!\mathbf{0}$}}{\mbox{$\not\!\mathbf{0}$}-\mbox{\ding{192}}-\mbox{\ding{193}}}.
\end{displaymath}

Отметим, что $\mbox{\ding{192}}$$\mbox{\ding{192}}$=$\mbox{\ding{193}}$ (равенство понимается в том смысле, что 1+1=2). Поэтому, заменив $\mbox{\ding{192}}$ на z, а $\mbox{$\not\!\mathbf{0}$}$ на 1, получим

\begin{displaymath}
A = \frac{\mbox{$\not\!\mathbf{0}$}}{\mbox{$\not\!\mathbf{0}$}-\mbox{\ding{192}}-\mbox{\ding{193}}} = \frac{1}{1-z-z^2}.
\end{displaymath}

Так мы получили второй вариант записи производящей функции. Забегая вперёд, отметим, что коэффициенты разложения этой функции в ряд по степеням z будут давать искомую последовательность (a0,a1,a2,...):

\begin{displaymath}
\frac{1}{1-z-z^2} = 1 + z + 2z^2+3z^3+5z^4+8z^5+\cdots.
\end{displaymath}

Более того, точная формула для чисел Фибоначчи fn имеет вид:

\begin{displaymath}
f_n = \frac1{2^n\sqrt{5}} \bigl( (1+\sqrt{5})^n - (1-\sqrt{5})^n \bigr),
\end{displaymath}

а искомое значение an=fn+1.

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

\begin{displaymath}
\frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots.
\end{displaymath}

Заменив $\mbox{\ding{192}}$+$\mbox{\ding{193}}$ на x, а $\mbox{$\not\!\mathbf{0}$}$ на 1, получим

\begin{displaymath}
A = \frac{\mbox{$\not\!\mathbf{0}$}}{\mbox{$\not\!\mathbf{...
... \sum_{n=0}^{\infty}(\mbox{\ding{192}}+\mbox{\ding{193}})^n.
\end{displaymath}

В этой сумме также учтены все возможные разбиения в точности по одному разу. Например, разбиение $\mbox{\ding{192}}$$\mbox{\ding{192}}$$\mbox{\ding{193}}$$\mbox{\ding{192}}$ встречается в ($\mbox{\ding{192}}$+$\mbox{\ding{193}}$)4. Далее воспользуемся биномом Ньютона:

\begin{displaymath}
A = \sum_{n=0}^{\infty}(\mbox{\ding{192}}+\mbox{\ding{193}...
...}^{n}\binom{n}{k}\mbox{\ding{192}}^k\mbox{\ding{193}}^{n-k}.
\end{displaymath}

Таким образом, коэффициент при $\mbox{\ding{192}}$k$\mbox{\ding{193}}$n−k, равный числу сочетаний из n по k, показывает общее количество разбиений из n слагаемых $\mbox{\ding{192}}$ и $\mbox{\ding{193}}$, содержащих $\mbox{\ding{192}}$ в количестве k и $\mbox{\ding{193}}$ в количестве n−k. Таким образом, общее количество разбиений числа n есть (внимание: почему?)

\begin{displaymath}
a_n = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}.
\end{displaymath}

Эта же сумма равна числу Фибоначчи fn+1, то есть числа Фибоначчи могут быть легко выражены и через биномиальные коэффициенты.

Задача о коммутативном разбиении

Рассмотрим предыдущую задачу с той разницей, что перестановка элементов разбиения не учитывается, то есть задачу со следующей формулировкой: как велико количество an способов представить неотрицательное целое число n в виде суммы чисел 1 и 2? Причём способы, отличающиеся перестановкой слагаемых, считаются одинаковыми (то есть 3=1+2 и 3=2+1 — одинаковые способы; именно поэтому разбиение называется коммутативным).

Как и прежде, рассмотрим ответы для некоторых небольших значений параметра n:

\begin{displaymath}
\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c...
...ne
$a_n$ & 1 & 1 & 2 & 2 & 3 \\
\hline
\end{tabular}
\end{displaymath}

Вернёмся к нашим обозначениям: 1=$\mbox{\ding{192}}$ и 2=$\mbox{\ding{193}}$. Читателю должно быть уже понятно, что, работая с производящими функциями, нужно завести какие-нибудь абстрактные символы, из которых можно сконструировать пересчитываемый объект, а затем попытаться все эти возможные объекты просуммировать. В данном случае суммировать удобно по частям. Пусть

\begin{displaymath}
T = \mbox{$\not\!\mathbf{0}$}+ \mbox{\ding{192}}+ \mbox{\d...
...mbox{$\not\!\mathbf{0}$}+ T\cdot\mbox{\ding{192}}\mbox{ ---}
\end{displaymath}

разбиения, состоящие только из единиц, тогда

\begin{displaymath}
A = T + T\mbox{\ding{193}}+ T\mbox{\ding{193}}\mbox{\ding{193}}+ \cdots = T + A \cdot\mbox{\ding{193}}\mbox{ ---}
\end{displaymath}

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

\begin{displaymath}\displaylines{
t = \frac{\mbox{$\not\!\mathbf{0}$}}{\mbox{$...
...= \frac{t}{\mbox{$\not\!\mathbf{0}$}-\mbox{\ding{193}}}.
}
\end{displaymath}

Подставляя T из первого уравнения во второе, получаем:

\begin{displaymath}
A = \frac{\mbox{$\not\!\mathbf{0}$}}{\mbox{$\not\!\mathbf{...
...!\mathbf{0}$}}{\mbox{$\not\!\mathbf{0}$}-\mbox{\ding{193}}}.
\end{displaymath}

Вспомним, что $\mbox{\ding{192}}$$\mbox{\ding{192}}$=$\mbox{\ding{193}}$, и, обозначив $\mbox{\ding{192}}$ через z, а $\mbox{$\not\!\mathbf{0}$}$ через 1, получим

\begin{displaymath}
A = \frac{1}{1-z}\cdot\frac{1}{1-z^2} = \frac{1}{(1-z)^2(1+z)}.
\end{displaymath}

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

\begin{displaymath}
\frac{1}{(1-z)^2(1+z)}=
\frac14\Biggl( \frac{3-z}{(1-z)^...
...fty} \biggl(\Bigl\lfloor\frac{n}{2}\Bigl\rfloor+1\biggr)z^n.
\end{displaymath}

Откуда $a_n=\lfloor n/2 \rfloor + 1$.