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

Question

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.

Answer 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

Answer 2

Hint

$$p(x)=(1 + x + x^2 +\cdots+x^n)^{n-1}=\left(\frac{x^{n+1}-1}{x-1}\right)^{n-1}$$ $$ p(x)(x-1)^{n-1}\equiv(x^{n+1}-1)^{n-1}$$

and remember that $p(x)$ has degree equal to $(n+1)(n-1)-(n-1)=n^2-n$. So,

$$p(x)=a_0+a_1x+...+a_{n^2-n}x^{n^2-n}$$

Answer 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.$$

Answer 4

Putting (probably far too many) details around Gerry Myerson's comment and avoiding the awkward upper bounds in IV_'s answer's sums... \begin{align*} f_n(x) &= \left( \sum_{k=0}^{n+1} x^{k} \right)^n \\ &= \left( \frac{1}{1-x} - \frac{x^{n+2}}{1-x} \right)^n \\ &= \sum_{k=0}^n (-1)^k \binom{n}{k} \left( \frac{1}{1-x} \right)^{n-k} \left( \frac{x^{n+2}}{1-x} \right)^k \\ &= \sum_{k=0}^n (-1)^k \binom{n}{k} x^{(n+2)k} \left( 1-x \right)^{-n} \\ &= \sum_{k=0}^{n+1} (-1)^k \binom{n}{k} x^{(n+2)k} \sum_{d = 0}^{n(n+1) - (n+2)k} \binom{n+d-1}{d} x^d \\ &= \sum_{i=0}^{n(n+1)} \left( \sum_{k=0}^{n+1} (-1)^k \binom{n}{k} \binom{n+i-(n+2)k-1}{i-(n+2)k} \right.\\ &\qquad \left. \phantom{\sum_{i=0}^{n(n+1)}} \left[ 0 \leq i-(n+2)k \leq n(n+1)-(n+2)k \right] \right) x^i \\ &= \sum_{i=0}^{n(n+1)} \left( \sum_{k=0}^{n+1} (-1)^k \binom{n}{k} \binom{n+i-(n+2)k-1}{i-(n+2)k} \right.\\ &\qquad \left. \phantom{\sum_{i=0}^{n(n+1)}} \left[ (n+2)k \leq i\right] \right) x^i \text{.} \end{align*} Above, we have used (roughly in top-to-bottom order) geometric sums and series, the binomial theorem (twice), the fact that we need not retain powers of $x^d$ that end up producing powers above the largest power of $x$ in $f_n(x)$ (since such contributions will conspire to cancel to zero), forcing $d$ to satisfy $(n+2)k+d = i$, the Iverson bracket, and the facts that $(n+2)k \geq 0$ and $i$ is upper bounded.

There's really an exclusion-inclusion hiding here, fairly explicit in the fourth line. As an example, per that line, $$ f_3(x) = \frac{1}{(1-x)^3} - \frac{3x^5}{(1-x)^3} + \frac{3x^{10}}{(1-x)^3} - \frac{x^{15}}{(1-x)^3} \text{,} $$ where we can see that what we want is the sum of four degree-shifted and scaled copies of polynomials constructed directly from the third diagonal of Pascal's triangle.

We can also frame this example as counting lattice points in a finite cube. We include all the points in triangular numbers until we reach the first corner (at $x^4$), where we need to subtract off contributions from the $3$ missing cubes starting at those corners, until they overlap -- causing double-deletion of points past the second "layer" of vertices -- and we add in $3$ cubes starting at those vertices, until we reach the last vertex and deal with the final batch of overlapping and overcounting.

These coefficients count lattice points in layers (of constant coordinate sum) of:

• $n=1$: lattice points in layers of a line segment of length $3$,
• $n=2$: lattice points in layers of a square of side $4$,
• $n=3$: lattice points in layers of a cube of side $5$,
• $n=4$: lattice points in layers of a tesseract of side $6$,
• $n=5$: lattice points in layers of a pentaract of side $7$,
• and so on ...

Answer 5

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$.