Cómo expresar $(1+x+x^2+\cdots+x^m)^n$ como una potencia de la serie?

Question

Es posible expresar $(1+x+x^2+\cdots+x^m)^n$ como una potencia de la serie?

Answer 1

Si intenta utilizar la multinomial teorema, se obtiene un $(m-1)$veces la suma iterada que podría no ser mucho progreso. Usted puede utilizar inclusión-exclusión para expresar el coeficiente de $x^k$ como una suma única en su lugar.

El coeficiente de $x^k$ $(1+\ldots+x^m)^n$ es el número de maneras de escribir $k$ como una suma de $n$ números enteros no negativos tales que ninguno son, al menos,$m+1$.

El número de maneras de escribir $k$ como una suma de $n$ números enteros no negativos es $k+n-1 \choose n-1$.

El número de maneras de escribir $k$ como una suma de $n$ números enteros no negativos, de modo que un determinado subconjunto de tamaño $s$ de los términos son, al menos,$m+1$, sin ninguna restricción sobre los demás, es el mismo que el número de maneras de escribir $k-s(m+1)$ como una suma de $n$ números enteros no negativos, sin restricciones, $k-s(m+1)+n-1 \choose n-1$.

Así, por medio de la inclusión-exclusión, el coeficiente de $x^k$ $(1+x+\ldots+x^m)^n$ es

$$\sum_{s=0}^{\lfloor k/(m+1) \rfloor} (-1)^s {n \choose s} {k-s(m+1)+n-1 \choose n-1}.$$

Por ejemplo, el coeficiente de $x^{50}$$(1+x+\ldots+x^{10})^{10}$$1018872811$, lo que es fácil de calcular, con una sola suma $(12565671261 - 16771066400 + 5598162900 - 374946000 + 1051050)$, pero es difícil calcular con un $9$veces la suma a lo largo de miles de términos.

Otra forma de obtener la misma respuesta es expandir$\left(\frac {1-x^{m+1}}{1-x}\right)^n$$(1-x^{m+1})^n \times (1-x)^{-n}$. Expanda el primer término con el teorema del binomio y, a continuación, utilizar$(1-x)^{-1} = 1 + x + x^2 + \ldots$$(1-x)^{-n} = \sum {n \choose k} x^k$, que es el teorema del binomio con exponente $-n$. Luego, multiplique los dos sumas, aislando el coeficiente de $x^k$.

Answer 2

Este es un polinomio, por lo que es trivialmente una potencia de la serie. Si desea ampliar se puede, por ejemplo, el uso de la multinomial teorema: http://en.wikipedia.org/wiki/Multinomial_theorem.

Answer 3

Aquí está una descomposición de los coeficientes que he trabajado últimamente y no he visto en otros lugares. Describe los coeficientes de la función general $$f(x)= 1 + ax + bx^2+cx^3+dx^4+\ldots...$$) y sus poderes.
Ver el scan de la tabla para la descomposición de abajo.(He publicado esto en otro stackexchange-pregunta recientemente)

Si todos los $a=b=c=d=\ldots=1 $, a continuación, las composiciones se reduce a simple binomios.
Esta descomposición también puede ser utilizado para encontrar la formal powerseries para la iteración de $f(x)$

Aquí la k'th coeficiente de $x^k$ de la $p$'th poder $f(x)^p=(1+x+x^2+x^3+...)^p $ es $$ f_{k,p} = \sum_{j=0}^{k-1} \left({\tbinom {k-1}{j} \over (1+j)! } \prod_{m=0}^j(p-m) \right) $$

[actualización] la Reformulación de que la descomposición permite una mucho más simple fórmula. La combinación de los términos adecuadamente al $k$'th coeficiente de $$f(x)^p = (1+x+x^2+x^3+...)^p = 1+c_1 ~ x+ c_2~x^2 + c_3 ~ x^3 + ... $$ $$ c_k = \sum_{j=1}^k \binom{p}{j}\binom{k-1}{j-1} $$ (este mucho más corta que la solución era ya dejó entrever en algunas de las respuestas anteriores comentarios, lo siento, no he entendido que los anteriores)

Answer 4

Sí, sólo tienes que multiplicar. O tratar $$\left( \frac{1-x^{m+1}}{1-x} \right)^n$$ como la generación de la función para la alimentación de la serie.

Pero sospecho que su pregunta real es si hay una forma simple de forma cerrada para el coeficiente de $x^k$ en el poder de la serie. No para general $k$, $m$ y $n$, aunque hay fórmulas y descripciones: son los llamados coeficientes multinomiales (binomial si $m=1$, trinomio si $m=2$ etc.)