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

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, $024321$. Известно, что количество счастливых билетов из шести цифр равно $55252$.

Задача:

Для натурального $n$ найти количество $2n$-значных счастливых билетов $L_n$.

Решение с помощью динамического программирования

Обозначим количество $n$-значных чисел с суммой $k$ как $D_n^k$ (число может содержать ведущие нули). $2n$-значный счастливый билет состоит из двух частей: левой ($n$ цифр) и правой (тоже $n$ цифр), причём в обеих частях сумма цифр одинакова. Количество счастливых билетов с суммой $k$ в одной из частей равно $(D_n^k)^2$. Значит общее число билетов равно $L_n = \sum_{k=0}^{9n} (D_{n}^{k})^2$. Также можно сопоставить счастливому билету $a_1a_2\ldots a_n b_1b_2 \ldots b_n$ $2n$-значное число с суммой $9n$: $a_1a_2\ldots a_n (9-b_1)(9-b_2) \ldots (9-b_n)$, причем это соответствие взаимно-однозначно, поэтому $L_n=D_{2n}^{9n}$. Осталось научиться вычислять $D_n^k$. Положим $D_0^k=\begin{cases}1,&k=0\\0,&k\gt 0\end{cases}$. При $n\gt 0$ количество $n$-значных чисел с суммой цифр $k$ можно выразить через количество $(n-1)$-значных чисел, добавляя к ним $n$-ю цифру, которая может быть равна $0, 1, \ldots, 9$: $D_n^k=\sum_{j=0}^{k}D_{n-1}^{k-j}$.

Решение с помощью производящей функции

Выпишем производящую функцию $G(z)$, коэффициент при $z^k$ у которой будет равен $D_1^k$: $G(z) = 1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9.$ Действительно, однозначное число с суммой цифр $k$ (для $k=0,\ldots,9$) можно представить одним способом. Для $k\gt 9$ — ноль способов. Заметим, что $G^n(z)$ — производящая функция для чисел $D_n^k$, поскольку коэффициент при $z^k$ получается перебором всех возможных комбинаций из $n$ цифр, равных в сумме $k$. Ответом на задачу будет $[z^{9n}]G^{2n}(z)$. Перепишем производящую функцию в ином виде: $G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}$ и получим, что $G^{2n}(z)=(1-z^{10})^{2n}(1-z)^{-2n}=\sum_{k=0}^{2n}\binom{2n}{k}(-z^{10})^k\sum_{j=0}^{\infty}\binom{-2n}{j}(-z)^k$. Так как $\binom{-2n}{k}=(-1)^k\binom{2n+k-1}{k}$, $[z^{9n}]G^{2n}(z)=\sum_{j=0}^{\lfloor{9n/10}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}$, что при $n=3$ дает $\binom{6}{0}\binom{32}{27}-\binom{6}{1}\binom{22}{17}+\binom{6}{2}\binom{12}{7}=55252$.

Источники информации

[1]

См. также

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

Динамическое программирование