Coeficientes de $(1+x+\dots+x^n)^3$ ?

Question

Consideremos el siguiente polinomio: $$(1+x+\dots+x^n)^3$$

Los coeficientes de la expansión para pocos valores de $n$ ( $n=1$ a $5$ ) son: $$1, 3, 3, 1$$ $$1, 3, 6, 7, 6, 3, 1$$ $$1, 3, 6, 10, 12, 12, 10, 6, 3, 1$$ $$1, 3, 6, 10, 15, 18, 19, 18, 15, 10, 6, 3, 1$$ $$1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1$$

¿Existe una fórmula de forma cerrada para el $i$ de esta secuencia (para diferentes valores de $n$ )?

Editar Esto parece similar a la secuencia A109439 en OEIS correspondiente a los coeficientes de la expansión de: $\left( \frac{1 - x^n}{1 - x} \right)^3 .$

Answer 1

Un enfoque alternativo:

Al igual que el $x^i$ término en $(1+\dots+x^n+\dots)^3$ cuenta el número de formas de elegir tres números para sumar $i$ El $x^i$ en su expansión cuenta el número de soluciones enteras no negativas del sistema $$y_1+y_2+y_3 = i$$ $$y_1, y_2, y_3 \leq n$$

Si no fuera por esa molesta segunda condición tendríamos un problema clásico que se puede resolver con el Estrellas y barras (o cualquier otro nombre que quieras darle). Hay un total de $\binom{i+2}{2}$ soluciones. De hecho, esa segunda condición desaparece una vez que $n \geq i$ , lo que explica por qué cada término de su secuencia acaba estabilizándose (y coincide con la secuencia OEIS que encontró).

Ahora tenemos que restar las soluciones en las que algunos de los $y_i$ son demasiado grandes. Para evitar el recuento excesivo, utilizamos la inclusión-exclusión, que nos dice que el número que queremos es igual a

$$\binom{i+2}{2}-3S_1+3S_2-S_3,$$ donde $S_1$ es el número de soluciones con $y_1>n$ (el $3$ proviene del hecho de que también contamos $y_2>n$ y $y_3>n$ ), $S_2$ es el número de soluciones con $y_1>n$ y $y_2>n$ y $S_3$ cuenta el número de soluciones con las tres variables demasiado grandes.

Ahora utilizamos un último truco. El número de soluciones de $y_1+y_2+y_3=n$ con $y_1>n$ es el mismo que el número de soluciones de $$(y_1-(n+1))+y_2+y_3=i-(n+1)$$ $$y_1-(n+1), y_2, y_3 \geq 0$$ que es sólo $\binom{i-(n+1)+2}{2}=\binom{i+1-n}{2}$ . Haciendo un truco idéntico con $S_2$ y $S_3$ da una respuesta final de $$\binom{i+2}{2}-3\binom{i+1-n}{2}+3\binom{i-2n}{2}-\binom{i-1-3n}{2}.$$

(correspondencia arreglada gracias a la útil corrección de Thomas en su comentario)

Answer 2

Denota por $$\sum_{k=0}^{3n}{\binom{3}{k}}_{n+1}x^{k}=(1 + x + ... + x^{n})^3\,$$ la expansión del multinomio de grado $n$

De esta relación se deduce que

$$\sum_{k=0}^{3n)}{\binom{3}{k}}_{n+1}x^{k}=\left(\frac{1-x^{n+1}}{1-x}\right)^{3}=(1-x^{n+1})^{3}(1-x)^{-3}\,$$

de la fórmula binomial tenemos

$$(1-x^{n+1})^{3}=\sum_{i=0}^{3}(-1)^{i}\binom{3}{i}x^{(n+1)i}$$

y de la fórmula de Taylor

$$(1-x)^{-3}=\sum_{j=0}^{\infty}\binom{2+j}{j}x^{j}$$

tras las sustituciones obtenemos

$$\sum_{k=0}^{\infty}{\binom{3}{k}}_{n+1}x^{k}=\sum_{i=0}^{3}(-1)^{i}\binom{3}{i}x^{(n+1)i}\sum_{j=0}^{\infty}\binom{2+j}{j}x^{j}=$$

$$=\sum_{j=0}^{\infty}\sum_{i=0}^{3}(-1)^{i}\binom{3}{i}\binom{2+j}{j}x^{(n+1)i+j}=$$

$$=\sum_{k=0}^{\infty}\sum_{i=0}^{3}(-1)^{i}\binom{3}{i}\binom{2+k-(n+1)i}{2}x^{k}\,$$

entonces iguala los coeficientes junto a x sigue la fórmula

$${\binom{3}{k}}_{(n+1)}=\sum_{i=0}^{3}(-1)^{i}\binom{3}{i}\binom{2+k-(n+1)i}{2}\,$$

fórmula para calcular los coeficientes de expansión

Answer 3

Si el polinomio fuera sustituido por una suma infinita, el coeficiente de $x^i$ sería igual al número de formas de elegir $(a,b,c) \in \{0,1,2,...\}^3$ tal que $a+b+c=i$ . Esto es igual al número de formas de elegir dos números $\le i$ o $\frac{1}{2}(i+1)(i+2)$ . La única diferencia es que aquí se quiere limitar el recuento a los casos en los que $a,b,c \le n$ . Utilizando el principio de inclusión-exclusión, se pueden restar los casos en los que uno de los números es mayor que $n$ , vuelve a sumar los casos en los que dos de los números son mayores que $n$ y restar los casos en los que los tres son mayores que $n$ . Para cada uno de estos recuentos, reste $n+1$ (o $2n+2$ o $3n+3$ ) de la suma objetivo primero, volviendo al caso en el que los tres números no están restringidos. El resultado es $$\begin{eqnarray} a_{i,n}&=&\frac{1}{2}(i+1)(i+2) - \frac{3}{2}(i-n)(i-n+1)\Theta(i-n-1) \\ &=& + \frac{3}{2}(i-2n-1)(i-2n)\Theta(i-2n-2) - \frac{1}{2}(i-3n-2)(i-3n-1)\Theta(i-3n-3), \end{eqnarray}$$ donde $\Theta(x)=1$ para $x\ge 0$ y $0$ para $x<0$ .