Funciones generadoras de facturas

Question

Con generación de funciones, encontrar el número de maneras de hacer cambiar un $\$ $100

cuenta usando sólo monedas de dólar y $\$$1, $ \$$5, and $\$$10 cuentas.

Mi respuesta: tuve $1/(1-x)^2*(1-x^5)*(1-x^{10})=1/(1-x)^2*(1-x^5)^2*(1+x^5)$. Sé que necesito encontrar el coeficiente de $x^{100}$. ¿Qué debo hacer a continuación? Mi conjetura es fracciones parciales pero el cálculo parece muy largo. ¿Hay una manera más fácil de determinar el coeficiente de?

Answer 1

Reescribir la función generadora $G(x)$ como

\begin{align*} G(x) &= \frac{1}{\left(1-x\right)^2\left(1-x^5\right)\left(1-x^{10}\right)}\\ &= \frac{\left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3}{\left(1-x^{10}\right)^4}\\ &= \left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3\sum_k \binom{k+3}{3} x^{10\, k} \end{align*}

Ahora, extraer $x^{10k}$ da %#% $ #%

$$[x^{10k}]G(x) = \binom{k+3}{3} + 15 \binom{k+2}{3}+4 \binom{k+1}{3}$, Obtenemos %#% $ #%

Answer 2

Por lo que la generación de la función de expansión puede ser trunca a: $ (1+x+x^2+\cdots +x^{100})^2. (1+x^5+x^{10}+\cdots +x^{100}). (1+x^{10}+x^{20}+\cdots + x^{100})$

Entonces, usted buscando el coeficiente de $x^{100}$.

Los dos primeros términos (para el 1 de monedas de dólar y el 1 de billetes de un dólar) se convierten en $1+2x+3x^2+\cdots +101x^{100}$ , además de los poderes superiores. Sólo los poderes que son múltiplos de 5 que son relevantes. Tan sólo necesita considerar: $1+6x^5+11x^{10}+\cdots+101x^{100}$.

Esto puede ser multiplicado por el siguiente término, y de una manera similar, deseche todos los poderes que son impares múltiplos de 5: $1+18x^{10}+(1+6+11+16+21)x^{20}+...$

Repita el procedimiento para el final de la multiplicación.