693
правки
Изменения
→Метод производящей функции
Действительно, однозначное число с суммой цифр <tex>k</tex> (для <tex>k=0,\ldots,9</tex>) можно представить одним способом. Для <tex>k>9</tex> — ноль способов. Заметим, что <tex>G^n(z)</tex> — производящая функция для чисел <tex>D_n^k</tex>, поскольку коэффициент при <tex>z^k</tex> получается перебором всех возможных комбинаций из <tex>n</tex> цифр, равных в сумме <tex>k</tex>. Ответом на задачу будет <tex>[z^{9n}]G^{2n}(z)</tex>. Перепишем производящую функцию в ином виде: <tex>
G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}
</tex> и получим, что <tex dpi="140">G^{2n}(z)=(1-z^{10})^{2n}(1-z)^{-2n}=\sum\limits_{k=0}^{2n}\dbinom{2n}{k}(-z^{10})^k\sum\limits_{j=0}^{\infty}\dbinom{-2n}{j}(-z)^j</tex>. Так как <tex dpi="140">\dbinom{-2n}{k}=(-1)^k\dbinom{2n+k-1}{k}</tex>, понятно, что <tex dpi="140">[z^{9n}]G^{2n}(z)=\sum\limits_{j=0}^{\lfloor{\frac{9n}{10}}\rfloor}(-1)^j\dbinombinom{2n}{j}\dbinom{11n-10j-1}{9n-10j}</tex>, что при <tex>n=3</tex> дает <tex dpi="140">\dbinom{6}{0}\dbinom{32}{27}-\dbinom{6}{1}\dbinom{22}{17}+\dbinom{6}{2}\dbinom{12}{7}=55252</tex>.
== Решение с помощью [[Формула включения-исключения | формулы включения-исключения]]==
