Me han pedido que resuelva el siguiente problema utilizando funciones generadoras:
¿Cuántas maneras hay de dividir $\$ 100 $ into bills of only $\$1$ et $\$ 5$?
Mi intento es el siguiente:
Dejemos que $$f_{1} = \sum_{n \ge 0}x^{n} = \frac{1}{1-x}$$ esta será la función generadora de $\$ 1 $ denominations. Let $$ f_{5} = \\Nsum_{x \ge 0}x^{5n} = \frac{1}{1-x^{5}} $$ this will be the generating function for $\$5$ denominaciones. Entonces la función generadora que buscamos es la convolución de las dos definidas anteriormente: $$\frac{1}{(1-x)(1-x^{5})}$$ Sin embargo, podemos escribir $f_{1}$ como $$f_{1} = f_{5}(1+x+x^{2}+x^{3}+x^{4})$$ Así que, en su lugar, miramos la función $$f_{5}^{2}(1+x+x^{2}+x^{3}+x^{4}) = \frac{1+x+x^{2}+x^{3}+x^{4}}{(1-x^{5})^{2}}$$
Aquí es donde estoy atascado. En las dos funciones que he descrito, la descomposición de la fracción parcial no es posible (¿o tal vez es extremadamente complicada?) debido a la $x^{5}$ término. A mi entender, tengo que escribir la convolución como una suma en términos de $x^{n}$ o $x^{5n}$ y a continuación, conecte $n=100$ o $n=20$ respectivamente y resolver para $a_{n}$ . Busco una pista más que una solución si es posible.
