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

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, [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]

См. также

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

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

• Интегральная формула Коши — Википедия

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

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