Determinando los coeficientes de$(1 + x + x^2 +\cdots+x^n)^{n-1}$

Question

Supongamos que tenemos los siguientes polinomios: $$f_1(x)=(1 + x + x^2)$$ $$f_2(x)=(1 + x + x^2 + x^3)^2$$ $$f_3(x)=(1 + x + x^2 + x^3 + x^4)^3$$ $$f_4(x)=(1 + x + x^2 + x^3 + x^4 + x^5)^4$$ $$\vdots$$ $$f_{n-1}(x)=(1 + x + x^2 + x^3 +x^4+ x^5+\cdots+x^n)^{n-1}$$ sobre la expansión de ellos se obtiene: $$f_1(x)=1 + x + x^2$$ $$f_2(x)=1 + 2 x + 3 x^2 + 4 x^3 + 3 x^4 + 2 x^5 + x^6$$ $$f_3(x)=1 + 3 x + 6 x^2 + 10 x^3 + 15 x^4 + 18 x^5 + 19 x^6 + 18 x^7 + 15 x^8 + 10 x^9 + 6 x^{10} + 3 x^{11} + x^{12}$$ $$f_4(x)=1 + 4 x + 10 x^2 + 20 x^3 + 35 x^4 + 56 x^5 + 80 x^6 + 104 x^7 + 125 x^8 + 140 x^9 + 146 x^{10} + 140 x^{11} + 125 x^{12} + 104 x^{13} + 80 x^{14} + 56 x^{15} + 35 x^{16} + 20 x^{17} + 10 x^{18} + 4 x^{19} + x^{20}$$ $$\vdots$$ $$f_{n-1}(x)=1 + ?x + ?x^2 + ?x^3 +?x^4+ ?x^5+\cdots+?x^{n(n-1)}$$ Me pregunto cómo determinar los coeficientes para el n-ésimo orden? Puedo observar que los coeficientes son simétricas.

Answer 1

$\sum_{i=0}^{k\cdot m}c_ix^i=(1+x^1+x^2+...+x^m)^{k}$ es la generación de la función de el número de débil entero composiciones (entero composiciones con repeticiones de $0$) de entero $i$ con $k$ partes donde todas las piezas son de menor igual a $m$.

Por desgracia, aún no está en OEIS.

$k,m>0$

Sus coeficientes son:

$$c_i=\sum_{j=0}^{\frac{i+k-1}{m+1}}(-1)^{j}\binom{k}{j}\binom{i+k-j(m+1)-1}{k-1}.$$

[Stanley, 1999], Error en la forma cerrada de la fórmula para el número restringido de composiciones?

con $n>0$, $k=n$, $m=n+1$:

$$c_i=\sum_{j=0}^{\frac{i+n-1}{n+2}}(-1)^{j}\binom{n}{j}\binom{i+n-j(n+2)-1}{n-1}$$

$\ $

[Stanley 1999] Stanley, R. P.: Combinatoria Enumerativa Vol. I. Cambridge University Press, 1999

Answer 2

Podemos pensar en el problema como una de las estrellas y de la barra de problema, que utiliza la inclusión-exclusión en el principio, como en la respuesta citada por IV_ y este uno.

Nos interprete \begin{equation}(1+x+x^2 + \cdots + x^{n})^{n-1} = \underbrace{(1+x+x^2 + \cdots + x^{n})(1+x+x^2 + \cdots + x^{n})\cdots (1+x+x^2 + \cdots + x^{n})}_{n-1\text{ times }}\end{equation} de la siguiente manera. Hay $n-1$ cajas, separados por $n-2$ bares. Puesto que estamos interesados en el coeficiente de $x^k$, queremos poner a $k$ indistiguishable bolas en los $n-1$ cajas. Se le permite tomar $n$ bolas de cada término del producto por encima, pero no más.

Supongamos que usted desea para evaluar el coeficiente de $x^{15}$en $$(1+x+x^2+x^3+x^4+x^5+x^6)^5,$$ sin la expansión de la totalidad del producto. Hay $5$ cajas separadas por $5-1=4$ bares, en la que tenemos que poner a $k=15$ bolas, con la restricción de que podemos elegir entre uno de los cinco términos en el producto en la mayoría de las $6$ bolas (la de mayor plazo es $x^6$). Un ejemplo de que es $$******\vert****\vert**\vert*\vert**,$$ que sería la contribución de $x^6$, $x^4$, $x^2$, $x$ e $x^2$ desde el primer, segundo, tercer, cuarto y quinto término del producto. El número de maneras de poner $15$ bolas indistinguibles en la $5$ cajas es $${15 + 5-1\choose 5-1} = 3876.$$ Ahora usted tiene que restar el número de maneras de poner $15$ bolas indistinguibles en $5$ cajas, para que en al menos un cuadro de más de $6+1=7$ aparecen pelotas. Ha ${5\choose 1}$ formas para elegir el cuadro en el que poner el $7$ bolas. El otro $15-7 = 8$ bolas puede ser colocado en ${8 + 5-1\choose 5-1}$ maneras. En total se han $${5\choose 1}{8 + 5-1\choose 5-1} = 2475 $$ maneras de poner $15$ indistinguibles de las pelotas en $5$ cajas, para que en al menos un cuadro de más de $7$ aparecen pelotas.

Ahora, aquí viene la inclusión principio de exclusión en el juego, también lo hizo restar los casos, donde en más de $1$ contenedor hubo, al menos, $7$ bolas. Para agregar el número de maneras de poner $15$ indistinguibles de las pelotas en $5$ cajas, donde en más de $2$ contenedor hubo, al menos, $7$ bolas. Ha ${5\choose 2}$ maneras de elegir los recipientes donde poner el $7$ bolas y ${1 + 5 -1 \choose 5-1}$ maneras de poner el resto de la pelota en los otros contenedores. Así que en total hay $${5 \choose 2}{1+5-1\choose 5-1} = 50$$ maneras de poner el $15$ indistinguibles de las pelotas en $5$ cajas, donde en más de $2$ contenedor hubo, al menos, $7$ bolas.

El coeficiente de $x^{15}$ en $(1+x+x^2+x^3+x^4+x^5+x^6)^5$ es por lo tanto $${15 + 5-1\choose 5-1} - {5\choose 1}{8 + 5 -1 \choose 5-1} + {5\choose 2}{1+5-1\choose 5-1} = 3876-2475+50 = 1451.$$

Answer 3

Insinuación

PS

y recuerde que $$p(x)=(1 + x + x^2 +\cdots+x^n)^{n-1}=\left(\frac{x^{n+1}-1}{x-1}\right)^{n-1}$ tiene un grado igual a $ $ . Asi que,

PS