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

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

Задача:

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

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

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

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

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

Решение с помощью формулы включения-исключения

Как было замечено выше, ответ на задачу равен количеству шестизначных билетов с суммой [math]27[/math]. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме 27; обозначим их множество [math]A[/math]. Выделим шесть множеств [math]C_i, i = 1 \ldots 6[/math], где [math]i[/math]-е множество состоит из расстановок, у которых в i-й позиции стоит число, не меньшее 10. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Посмотрим на расстановку n чисел с суммой k как на сочетание с повторениями из n по k, число означает количество повторений элемента, значит количество расстановок равно [math]\binom{n+k-1}{n-1}[/math]. Число [math]\left\vert{A}\right\vert[/math] всех расстановок неотрицательных целых чисел с суммой 27 в шесть позиций равно [math]\binom{32}{5}[/math] Число расстановок [math]\left\vert{C_i}\right\vert[/math] одинаково для всех i и равно [math]\binom{22}{5}[/math]. В самом деле, мы можем поставить в i-ю позицию число 10, а оставшуюся сумму 17 произвольно распределить по шести позициям. Аналогично, число расстановок [math]\left\vert{C_i \cap C_j}\right\vert[/math] одинаково для любой пары [math]i, j, i \neq j[/math] и равно [math]\binom{12}{5}[/math]: мы выбираем две позиции и ставим в них 10 и произвольно распределяем оставшуюся сумму 7 по шести позициям. Таким образом, искомое количество расстановок равно [math]\left\vert{A}\right\vert - \binom{6}{1}\left\vert{C_i}\right\vert+\binom{6}{2}\left\vert{C_i \cap C_j}\right\vert = \binom{32}{5}-6\binom{22}{5}+15\binom{12}{5} = 55252[/math]

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

Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) [math]H(z)=G^3(z)G^3(1/z)[/math]. Заметим, что его свободный член равен [math]\sum_{i=0}^{27}[z^i]G^3(z)\cdot [z^{-i}]G^3(z^{-1})=\sum_{i=0}^{27}(D_3^i)^2[/math]. Воспользуемся теоремой Коши из комплексного анализа:

Теорема (Коши):

Для любого многочлена Лорана p(z) его свободный член p_0 равен [math]p_0=\dfrac{1}{2\pi i}{\displaystyle \int} \dfrac{p(z)}{z} dz[/math], где интегрирование происходит по любой окружности, ориентированной против часовой стрелки и содержащей внутри себя начало координат.

Упростим многочлен [math]H[/math]:

[math]H(z)=\left( \dfrac{1-z^{10}}{1-z} \right) ^3\left(\dfrac{1-z^{-10}}{1-z^{-1}}\right)^3=\left(\dfrac{2-z^{10}-z^{-10}}{2-z-z^{-1}}\right)^3[/math] и применим замену [math]z=e^{i\phi}[/math]:

[math]p_0=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi=\dfrac{1}{\pi}\displaystyle\int_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi=\dfrac{1}{\pi}\displaystyle\int_{-\pi/2}^{\pi/2}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi[/math]

Рассмотрим функцию [math]f(\phi)=\dfrac{\sin(10\phi)}{\sin\phi}[/math] на [math][-\pi/2,\pi/2][/math]. Вне отрезка [math][-\pi/10,\pi/10] f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3[/math], значит интеграл по этой части не больше [math]\pi3^6 \approx 2100[/math], основная часть сосредоточена на [math][-\pi/10,\pi/10][/math]. Оценим интеграл по промежутку с помощью метода стационарной фазы.

См. также

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

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

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

• Задача о счастливых билетах :: Производящие функции