64
правки
Изменения
Нет описания правки
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>.
== Решение с помощью формулы включения-исключения <ref>[http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%B2%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D1%8F-%D0%B8%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D1%8F Формула включения-исключения — Викиконспекты]</ref>==
Как было замечено выше, ответ на задачу равен количеству шестизначных билетов с суммой <tex>27</tex>. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме 27; обозначим их множество <tex>A</tex>. Выделим шесть множеств <tex>C_i, i = 1 \ldots 6</tex>, где <tex>i</tex>-е множество состоит из расстановок, у которых в i-й позиции стоит число, не меньшее 10. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Посмотрим на расстановку n чисел с суммой k как на сочетание с повторениями из n по k, число означает количество повторений элемента, значит количество расстановок равно <tex>\binom{n+k-1}{n-1}</tex>. Число <tex>\left\vert{A}\right\vert</tex> всех расстановок неотрицательных целых чисел с суммой 27 в шесть позиций равно <tex>\binom{32}{5}</tex> Число расстановок <tex>\left\vert{C_i}\right\vert</tex> одинаково для всех i и равно <tex>\binom{22}{5}</tex>. В самом деле, мы можем поставить в i-ю позицию число 10, а оставшуюся сумму 17 произвольно распределить по шести позициям. Аналогично, число расстановок <tex>\left\vert{C_i \cap C_j}\right\vert</tex> одинаково для любой пары <tex>i, j, i \neq j</tex> и равно <tex>\binom{12}{5}</tex>: мы выбираем две позиции и ставим в них 10 и произвольно распределяем оставшуюся сумму 7 по шести позициям. Таким образом, искомое количество расстановок равно <tex>\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</tex>
== Решение путем интегрирования ==
== См. также ==
* [[Производящая функция]]
* [[Динамическое программирование]]
*[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 Интегральная формула Коши — Википедия]
== Примечания ==
<references />
== Источники информации ==
* [http://www.genfunc.ru/theory/lucky/ Задача о счастливых билетах :: Производящие функции]
