Задача о счастливых билетах

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

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

Здесь будут рассмотрены некоторые известные методы решения данной задачи. Количество счастливых билетов из 2n цифр будем обозначать символом Ln.

Метод динамического программирования

Введём обозначение: $D_n^k$ — количество n-значных чисел с суммой цифр, равной k (число может начинаться с цифры 0). Понятно, что любой билет состоит из двух частей: левой (n цифр) и правой (тоже n цифр), причём в обеих частях сумма цифр одинакова. Количество счастливых билетов с суммой k в одной из частей, очевидно, равно $(D_n^k)^2$. Значит общее количество 2n-значных счастливых билетов равно

\begin{displaymath}
L_n = \sum_{k=0}^{9n} (D_{n}^{k})^2.
\end{displaymath}

Верхний индекс суммирования равен 9n, так как максимальная сумма цифр в одной части билета равна 9n.

Теперь осталось найти все значения $D_n^k$. Количество n-значных чисел с суммой цифр k можно выразить через количество (n-1)-значных чисел, добавляя к ним n-ю цифру, которая может быть равна 0, 1, ..., 9:

\begin{displaymath}
D_n^k = \sum_{j=0}^{9} D_{n-1}^{k-j}, \qquad n>0.
\end{displaymath}

Здесь неявно предполагается, что $D_n^{-1}=D_n^{-2}=\ldots=0$ для n≥0. Положим по определению $D_0^0=1$.

Вычисление значений $D_n^k$ по указанной формуле лучше представить с помощью таблицы:

Dtable

Любое число в этой таблице (кроме $D_0^0$) получается если просуммировать 10 элементов, стоящих слева и сверху от него. Например, в таблице красным цветом выделено число 73, а серым — числа, сумме которых оно равно. Само это число 73 означает, что именно столько существует трёхзначных чисел с суммой цифр 12.

Теперь нужно просуммировать квадраты чисел, стоящих в столбце n=3: 12+32+62 +⋅⋅⋅=55252. Если нужно было бы подсчитать восьмизначные билеты, то потребовалось бы вычислять столбец n=4 до значения k=36.

Метод производящих функций

Билет состоит из двух частей. Рассмотрим произвольный счастливый билет, скажем, 271334 и заменим цифры второй его части на величину, которой им не хватает до 9. То есть 271665. Теперь сумма всех цифр билета равна 27. Легко заметить, что такой фокус проходит с любым счастливым билетом. Таким образом, количество счастливых билетов из 2n цифр равно количеству 2n-значных чисел с суммой цифр, равной 9n. То есть

\begin{displaymath}
L_n = D_{2n}^{9n}.
\end{displaymath}

Теперь можно было бы воспользоваться техникой предыдущего пункта и найти число, стоящее в столбце n=6 и в строке k=27. Получилось бы в точности 55252. Но здесь можно воспользоваться техникой производящих функций.

Выпишем производящую функцию G(z), коэффициент при zk у которой будет равен $D_1^k$:

\begin{displaymath}
G(z) = 1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9.
\end{displaymath}

Действительно, однозначное число с суммой цифр k (для k=0,...,9) можно представить одним способом. Для k>9 — ноль способов.

Заметим, что если возвести функцию G в квадрат, то коэффициент при zk будет равен числу способов получить сумму k с помощью двух цифр от 0 до 9:

\begin{displaymath}\displaylines{
\ig{0.2}G^2(z) = 1+2z^2+3z^2+4z^3+5z^4+6z^5+...
...+6z^{13}+5z^{14}+4z^{15}+3z^{16}+2z^{17}+z^{18}.\ig{0.2}
}
\end{displaymath}

В общем случае, Gn(z) — это производящая функция для чисел $D_n^k$, поскольку коэффициент при zk получается перебором всех возможных комбинаций из n цифр от 0 до 9, равных в сумме k. Перепишем производящую функцию в ином виде:

\begin{displaymath}
G(z) = 1+z+\cdots+z^9 = \frac{1-z^{10}}{1-z}.
\end{displaymath}

В итоге, нам требуется отыскать

\begin{displaymath}[z^{27}]G^6(z).
\end{displaymath}

Для этого посмотрим, что будет получаться, если раскрывать скобки в следующем выражении (нас интересует только коэффициенты при z27):

\begin{displaymath}\displaylines{
G^6(z) = (1-z^{10})^6(1-z)^{-6}=
\sum_{k=0...
...{17}+
\binom{6}{2}\binom{-6}{7}\right)z^{27} + \cdots.
}
\end{displaymath}

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

\begin{displaymath}
D_6^{27}=\binom{6}{0}\binom{-6}{27}-\binom{6}{1}\binom{-6}...
...7}=
\binom{32}{5}-6\binom{22}{5}+
15\binom{12}{5}=55252.
\end{displaymath}

Решение путём интегрирования

Внимание, данный раздел предназначен для тех, кто знаком с курсом ТФКП.

Воспользуемся производящей функцией G(z) из предыдущего раздела:

\begin{displaymath}
G(z) = 1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9 = \frac{1-z^{10}}{1-z}.
\end{displaymath}

Составим ряд Лорана следующим образом:

\begin{displaymath}
H(z)=G^3(z)G^3(1/z)=\sum_{k=-\infty}^{\infty}a_kz^k.
\end{displaymath}

Значение a0 в данном разложении будет в точности равно [ проверьте ]

\begin{displaymath}
a_0=\bigl(D_3^0\bigr)^2+\bigl(D_3^1\bigr)^2+\cdots+\bigl(D_3^{27}\bigr)^2=L_3.
\end{displaymath}

Интегральная теорема Коши говорит, что

\begin{displaymath}[z^0]H(z) = \frac{1}{2\pi i} \oint \frac{H(z)}{z} dz,
\end{displaymath}

где интегрирование выполняется по любой простой замкнутой кривой, охватывающей начало координат. Удобно взять $z=e^{i\varphi }$, чтобы интегрировать вдоль окружности (такая замена равносильна переходу к полярным координатам):

\begin{displaymath}[z^0]
 H(e^{i\varphi }) = \frac{1}{2\pi i} \int\limits_{0}^{2\p...
...1}{2\pi} \int\limits_{0}^{2\pi} H(e^{i\varphi }) d\varphi .
\end{displaymath}

Теперь подставим сюда H(z):

\begin{displaymath}\displaylines{
a_0=\frac{1}{2\pi} \int\limits_{0}^{2\pi} \f...
...(\frac{\sin10\varphi }{\sin\varphi }\right)^6\,d\varphi
}
\end{displaymath}

Итак,

\begin{displaymath}
L_3=\frac{1}{\pi} \int\limits_{0}^{\pi}
\left(\frac{\sin10\varphi }{\sin\varphi }\right)^6 d\varphi =55252.
\end{displaymath}

Нетрудно видеть, что в общем случае

\begin{displaymath}
L_n=\frac{1}{\pi} \int\limits_{0}^{\pi}
\left(\frac{\sin10\varphi }{\sin\varphi }\right)^{2n} d\varphi .
\end{displaymath}

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

Также в одном из упражнений будет предложено вывести формулу:

\begin{displaymath}
L_n = \sum_{k=0}^{n-1} (-1)^k \binom{2n}{k}\binom{11n-1-10k}{2n-1},
\end{displaymath}

вычисление по которой представляется на сегодняшний день очень эффективным.