Para el registro, voy a copiar un fragmento de forma que esta respuesta a una pregunta que estaba cerrada, como un duplicado a esta pregunta, como se explica exactamente cómo calcular el coeficiente usado explícitamente, lo que es realmente el mismo que el método dado en la respuesta por ray en una más algorítmica de la formulación. Me acaba de dar el procedimiento aquí, para más explicaciones, véase la respuesta vinculado.
Deje $c$ denotar una matriz de $101$ enteros indexado de$0$$100$.
- Inicializar la matriz de modo que $c[0]=1$ $c[i]=0$ todos los $i>0$.
- Para $k=1,5,10,25,50,100$ (en cualquier orden):
- para $i=0,1,\ldots,100-k$ (en este orden):
- Ahora $c[100]$ da su respuesta.
Este cálculo da el coeficiente de $x^{100}$ en el poder de la serie para $1/((1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100}))$, lo que equivale a $293$.
En este caso particular no es un truco que le ahorrará tiempo y la memoria, aprovechando el hecho de que todos los valores de $k$ con la excepción de $k=1$ son divisibles por$~5$. Ya que tenemos la libertad de elegir el orden de las$~k$, se puede mantener $k=1$ para el final, y observar que sólo los valores de $c[i]$ $i$ divisible por$~5$ será distinto de cero cuando llegamos a la última instancia del ciclo de $k=1$. Pero entonces bien podríamos inicial de bucles para calcular sólo a ellos (lo hacen sólo los $i$ en el bucle interno que sean divisibles por $5$). También el último bucle de $k=1$ es simplemente calculando la suma de todos los ingresos en $c[100]$, de modo que bien podría tomar sólo la suma de los distinto de cero entradas. Así se obtiene un procedimiento que sólo se trata de la $21$ múltiplos de $5$$100$, y se puede hacer incluso con la mano.
Voy a añadir que esto no es asintóticamente método más rápido para calcular el coeficiente de $x^n$ en la serie determinada por un gran $n$. Se puede hacer en un número constante de operaciones aritméticas, haciendo que el denominador una potencia de el mínimo común múltiplo de los factores escrito, que en este caso sería la sexta potencia de $1-x^{100}$ como es divisible entre otros factores, por ejemplo,$1-x^{100}=(1-x^{25})(1+x^{25}+x^{50}+x^{75})$. Los coeficientes involucrados para transformar todos los factores en este mínimo común múltiplo debe, por supuesto, también se multiplica en el numerador para mantener la expresión equivalente. El numerador ahora es un polinomio que puede ser explícitamente calculada de una vez por todas, y esto se multiplica por una potencia negativa, aquí $(1-x^{100})^{-6}$, cuyos coeficientes pueden ser calculadas (en la demanda!) el uso de los coeficientes binomiales. Para encontrar el coeficiente en el resultado de un solo monomio $x^n$ requiere de la multiplicación de cada uno de los número fijo de los coeficientes en el numerador factor por uno de los coeficientes del denominador factor y sumando; todo esto da un número constante de operaciones. Esto requiere más preparación y programación de hacer, a continuación, el método esbozado anteriormente, que para el valor como $n=100$ realmente no pagar. Sin embargo, si la pregunta fuera ¿cuántas maneras hay de hacer un cambio para mil millones (en el sentido de mil millones de dólares), sólo el uso de las mismas monedas (suponiendo suficiente existía), uno tendría $n=10^{11}$ y la correcta coeficiente de 13333333398333333445333333413833333354500000001 para ese caso habría sido difícil de calcular de manera diferente. Bono de la pregunta, explique por qué hay tantos dígitos repetidos en este coeficiente.
