64
правки
Изменения
Нет описания правки
Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, <tex>024321</tex>. Известно, что количество счастливых билетов из шести цифр равно <tex>55252</tex>.
{{Задача
|definition = Для любого натурального <tex>n</tex> найти количество <tex>2n</tex>-значных счастливых билетов(<tex>L_n</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>
== Решение с помощью производящей функции ==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Комбинаторика]]
