Задача о счастливых билетах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
__TOC__
 
__TOC__
 
== Решение с помощью динамического программирования ==
 
== Решение с помощью динамического программирования ==
Обозначим количество <tex>n</tex>-значных чисел с суммой <tex>k</tex> как <tex>D_n^k</tex> (число может содержать ведущие нули). <tex>2n</tex>-значный счастливый билет состоит из двух частей: левой (<tex>n</tex> цифр) и правой (тоже <tex>n</tex> цифр), причём в обеих частях сумма цифр одинакова. Количество счастливых билетов с суммой <tex>k</tex> в одной из частей равно <tex>(D_n^k)^2</tex>. Значит общее число билетов равно <tex>L_n = \sum_{k=0}^{9n} (D_{n}^{k})^2</tex>. Также можно сопоставить счастливому билету <tex>a_1a_2\ldots a_n b_1b_2 \ldots b_n</tex> <tex>2n</tex>-значное число с суммой <tex>9n</tex>: <tex>a_1a_2\ldots a_n (9-b_1)(9-b_2) \ldots (9-b_n)</tex>, причем это соответствие взаимно-однозначно, поэтому <tex>L_n=D_{2n}^{9n}</tex>.  
+
Обозначим количество <tex>n</tex>-значных чисел с суммой <tex>k</tex> как <tex>D_n^k</tex> (число может содержать ведущие нули). <tex>2n</tex>-значный счастливый билет состоит из двух частей: левой (<tex>n</tex> цифр) и правой (тоже <tex>n</tex> цифр), причём в обеих частях сумма цифр одинакова. Зафиксируем число в левой части (это можно сделать <tex>D_n^k</tex> способами), для него будет существовать <tex>D_n^k</tex> возможных вариантов числа в правой части, следовательно количество счастливых билетов с суммой <tex>k</tex> в одной из частей равно <tex>(D_n^k)^2</tex>. Значит общее число билетов равно <tex>L_n = \sum_{k=0}^{9n} (D_{n}^{k})^2</tex>. Верхний индекс суммирования равен <tex>9n</tex>, так как максимальная сумма цифр в одной части билета равна <tex>9n</tex>. Также можно сопоставить счастливому билету <tex>a_1a_2\ldots a_n b_1b_2 \ldots b_n</tex> <tex>2n</tex>-значное число с суммой <tex>9n</tex>: <tex>a_1a_2\ldots a_n (9-b_1)(9-b_2) \ldots (9-b_n)</tex>, причем это соответствие взаимно-однозначно, поэтому <tex>L_n=D_{2n}^{9n}</tex>.  
 
Осталось научиться вычислять <tex>D_n^k</tex>. Положим <tex>D_0^k=\begin{cases}1,&k=0\\0,&k>0\end{cases}</tex>. При <tex>n>0</tex> количество <tex>n</tex>-значных чисел с суммой цифр <tex>k</tex> можно выразить через количество <tex>(n-1)</tex>-значных чисел, добавляя к ним <tex>n</tex>-ю цифру, которая может быть равна <tex>0, 1, \ldots, 9</tex>: <tex>D_n^k=\sum_{j=0}^{k}D_{n-1}^{k-j}</tex>.
 
Осталось научиться вычислять <tex>D_n^k</tex>. Положим <tex>D_0^k=\begin{cases}1,&k=0\\0,&k>0\end{cases}</tex>. При <tex>n>0</tex> количество <tex>n</tex>-значных чисел с суммой цифр <tex>k</tex> можно выразить через количество <tex>(n-1)</tex>-значных чисел, добавляя к ним <tex>n</tex>-ю цифру, которая может быть равна <tex>0, 1, \ldots, 9</tex>: <tex>D_n^k=\sum_{j=0}^{k}D_{n-1}^{k-j}</tex>.
  
Строка 20: Строка 20:
 
[[Динамическое программирование]]
 
[[Динамическое программирование]]
 
== Источники информации ==
 
== Источники информации ==
[http://www.genfunc.ru/theory/lucky/]
+
* [http://www.genfunc.ru/theory/lucky/ Задача о счастливых билетах :: Производящие функции]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Комбинаторика]]
 
[[Категория:Комбинаторика]]
 +
[[Категория:Производящие функции]]

Версия 13:22, 6 июня 2017

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

См. также

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

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

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