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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, <tex>024321</tex>. Известно, что количество счастливых билетов из шести цифр равно <tex>55252</tex>.
 
Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, <tex>024321</tex>. Известно, что количество счастливых билетов из шести цифр равно <tex>55252</tex>.
 
{{Задача
 
{{Задача
|definition = Для натурального <tex>n</tex> найти количество <tex>2n</tex>-значных счастливых билетов (<tex>L_n</tex>).
+
|definition = Для натурального <tex>n</tex> найти количество <tex>2n</tex>-значных счастливых билетов <tex>L_n</tex>.
 
}}
 
}}
 +
__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>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>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>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>.
  
Строка 14: Строка 15:
 
G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}
 
G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}
 
</tex> и получим, что <tex>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</tex>. Так как <tex>\binom{-2n}{k}=(-1)^k\binom{2n+k-1}{k}</tex>, <tex>[z^{9n}]G^{2n}(z)=\sum_{j=0}^{\lfloor{9n/10}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}</tex>, что при <tex>n=3</tex> дает <tex>\binom{6}{0}\binom{32}{27}-\binom{6}{1}\binom{22}{17}+\binom{6}{2}\binom{12}{7}=55252</tex>.
 
</tex> и получим, что <tex>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</tex>. Так как <tex>\binom{-2n}{k}=(-1)^k\binom{2n+k-1}{k}</tex>, <tex>[z^{9n}]G^{2n}(z)=\sum_{j=0}^{\lfloor{9n/10}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}</tex>, что при <tex>n=3</tex> дает <tex>\binom{6}{0}\binom{32}{27}-\binom{6}{1}\binom{22}{17}+\binom{6}{2}\binom{12}{7}=55252</tex>.
 +
== Источники информации ==
 +
[http://www.genfunc.ru/theory/lucky/]
 +
== См. также ==
 +
[[Производящая функция]]
 +
 +
[[Динамическое программирование]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Комбинаторика]]
 
[[Категория:Комбинаторика]]

Версия 23:56, 31 мая 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]k[/math] в одной из частей равно [math](D_n^k)^2[/math]. Значит общее число билетов равно [math]L_n = \sum_{k=0}^{9n} (D_{n}^{k})^2[/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].

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

[1]

См. также

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

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