Determining the coefficients of $(1 + x + x^2 +\cdots+x^n)^{n-1}$

Suppose we have the following polynomials: $$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}$$ upon expanding them we get: $$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)}$$ I'm wondering how to determine the coefficients for the n-th order? I can observe that the coefficients are symmetric.

Solution 1:

$\sum_{i=0}^{k\cdot m}c_ix^i=(1+x^1+x^2+...+x^m)^{k}$ is the generating function of the number of weak integer compositions (integer compositions with repetitions of $0$) of integer $i$ with $k$ parts where all parts are lower equal to $m$.

Unfortunately, it is not yet in OEIS.

$k,m>0$

Their coefficients are:

$$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], Mistake in the closed form formula for the number of restricted compositions?

with $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.: Enumerative Combinatorics Vol. I. Cambridge University Press, 1999

Solution 2:

We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.

We obtain for $0\leq k\leq n(n-1)$: \begin{align*} \color{blue}{[x^{k}]}&\color{blue}{\left(1+x+x^2+\cdots+x^n\right)^{n-1}}\\ &=[x^k]\left(\frac{1-x^{n+1}}{1-x}\right)^{n-1}\tag{1}\\ &=[x^k]\sum_{j=0}^\infty\binom{-(n-1)}{j}(-x)^j\sum_{l=0}^{n-1}\binom{n-1}{l}\left(-x^{n+1}\right)^l\tag{2}\\ &=[x^k]\sum_{j=0}^\infty\binom{n-j-2}{j}x^j\sum_{l=0}^{n-1}\binom{n-1}{l}(-1)^lx^{(n+1)l}\tag{3}\\ &=\sum_{j=0}^{k}\binom{n-j-2}{j}[x^{k-j}]\sum_{l=0}^{n-1}\binom{n-1}{l}(-1)^lx^{(n+1)l}\tag{4}\\ &=\sum_{j=0}^{k}\binom{n-k+j-2}{k-j}[x^{j}]\sum_{l=0}^{n-1}\binom{n-1}{l}(-1)^lx^{(n+1)l}\tag{5}\\ &=\sum_{j=0}^{\left\lfloor\frac{k}{n+1}\right\rfloor}\binom{n-k+(n+1)j-2}{k-(n+1)j}[x^{(n+1)j}]\sum_{l=0}^{n-1}\binom{n-1}{l}(-1)^lx^{(n+1)l}\tag{6}\\ &\,\,\color{blue}{=\sum_{j=0}^{\left\lfloor\frac{k}{n+1}\right\rfloor}\binom{(n+2)j-k-2}{k-(n+1)j}\binom{n-1}{j}(-1)^j}\tag{7}\\ \end{align*}

Comment:

• In (1) we use the finite geometric series formula.

• In (2) we use the binomial series expansion and apply the binomial theorem.

• In (3) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (4) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and set the upper limit of the outer sum to $k$ since indices $j>k$ do not contribute.

• In (5) we reverse the order of summation of the outer sum: $j\to k-j$.

• In (6) we consider only $(n+1)$-multiples of $j$ since other values do not occur as exponent of $x$ in the inner sum.

• In (7) we finally select the coefficients of $x^{(n+1)j}$ by taking $l=j$.

Solution 3:

We can think at the problem as a stars and bar problem, that uses the inclusion-exclusion principle, as in the answer cited by IV_ and this one.

We 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} as follows. There are $n-1$ boxes, separated by $n-2$ bars. Since we are interested in the coefficient of $x^k$, we want to put $k$ indistiguishable balls in those $n-1$ boxes. You are allowed to take $n$ balls from each term of the product above, but no more.

Suppose you want to evaluate the coefficient of $x^{15}$ in $$(1+x+x^2+x^3+x^4+x^5+x^6)^5,$$ without expanding the whole product. There are $5$ boxes separated by $5-1=4$ bars, in which we have to put $k=15$ balls, with the restriction that we may pick from one of the five terms in the product at most $6$ balls (the highest term is $x^6$). One example of that is $$******\vert****\vert**\vert*\vert**,$$ which would be the contribution of $x^6$, $x^4$, $x^2$, $x$ and $x^2$ from the first, second, third, fourth and fifth term of the product. The number of ways to put $15$ indistinguishable balls in the $5$ boxes is $${15 + 5-1\choose 5-1} = 3876.$$ Now you have to subtract the number of ways to put $15$ indistinguishable balls in $5$ boxes, so that in at least one box more than $6+1=7$ balls appear. You have ${5\choose 1}$ ways to choose the box in which to put the $7$ balls. The other $15-7 = 8$ balls can be placed in ${8 + 5-1\choose 5-1}$ ways. In total you have $${5\choose 1}{8 + 5-1\choose 5-1} = 2475 $$ ways to put $15$ indistinguishable balls into $5$ boxes, so that in at least one box more than $7$ balls appear.

Now, here comes the inclusion exclusion principle in play, you also did subtract the cases, where in more than $1$ container there were at least $7$ balls. So you add the number of ways to put $15$ indistinguishable balls into $5$ boxes, where in more than $2$ container there were at least $7$ balls. You have ${5\choose 2}$ ways to choose the containers where to put the $7$ balls and ${1 + 5 -1 \choose 5-1}$ ways to put the remaining ball in the other containers. So in total there are $${5 \choose 2}{1+5-1\choose 5-1} = 50$$ ways to put the $15$ indistinguishable balls into $5$ boxes, where in more than $2$ container there were at least $7$ balls.

The coefficient of $x^{15}$ in $(1+x+x^2+x^3+x^4+x^5+x^6)^5$ is therefore $${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.$$