4
$\begingroup$

Consider the following polynomial: $$ (1+x+\dots+x^n)^3 $$

The coefficients of the expansion for few values of $n$ ($n=1$ to $5$) are: $$ 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 $$

Is there a closed-form formula for the $i$th element of this sequence (for different values of $n$)?

Edit This looks similar to the sequence A109439 on OEIS corresponding to the coefficients of the expansion of: $ \left( \frac{1 - x^n}{1 - x} \right)^3 .$

  • 2
    See [Multinomial Theorem](http://en.wikipedia.org/wiki/Multinomial_theorem).2011-12-14
  • 3
    Note: $\frac{1 - x^n}{1 - x} = 1 + x +.. + x^{n-1}$2011-12-14
  • 0
    @ThomasAndrews then, please ignore the part on OEIS.2011-12-14
  • 0
    @Peteris I can not figure out how to use the multinomial theorem here (at least using the formulation in WP). It assumes that all monomials are distinct, which is not the case here. I will have to add up the similar monomial products in $\Pi {{x_t}^{k_t}}.$ I have no obvious way to do that.2011-12-14
  • 0
    J.D.: Do you understand how to get a formula for the expansion of $(1+x+\dots+x^n+\dots)^3$ (where your polynomial is replaced by an infinite sum)?2011-12-14
  • 1
    @KevinC. Not really. My attempt: the $i$th coefficient $=$ how many ways we can select three numbers $\in \{ 0, \dots, i \}$ such that their sum $= i.$2011-12-14

3 Answers 3

3

An alternative approach:

Just as the $x^i$ term in $(1+\dots+x^n+\dots)^3$ counts the number of ways of picking three numbers to add to $i$, the $x^i$ term in your expansion counts the number of non-negative integer solutions to the system $$y_1+y_2+y_3 = i$$ $$y_1, y_2, y_3 \leq n$$

If it wasn't for that pesky second condition we'd have a classic problem that can be solved by the Stars and Bars method (or whatever other name you wish to call it). There's a total of $\binom{i+2}{2}$ solutions. In fact, that second condition disappears once $n \geq i$, which explains why each term in your sequence eventually stabilizes (and matches the OEIS sequence you found).

We now need to subtract off solutions where some of the $y_i$ are too large. To avoid overcounting, we use Inclusion-Exclusion, which tells us that the number we want is equal to

$$\binom{i+2}{2}-3S_1+3S_2-S_3,$$ where $S_1$ is the number of solutions with $y_1>n$ (the $3$ comes from the fact that we also count $y_2>n$ and $y_3>n$), $S_2$ is the number of solutions with $y_1>n$ and $y_2>n$, and $S_3$ counts the number of solutions with all three variables too large.

Now we use one final trick. The number of solutions to $y_1+y_2+y_3=n$ with $y_1>n$ is the same as the number of solutions to $$(y_1-(n+1))+y_2+y_3=i-(n+1)$$ $$y_1-(n+1), y_2, y_3 \geq 0$$ which is just $\binom{i-(n+1)+2}{2}=\binom{i+1-n}{2}$. Doing an identical trick with $S_2$ and $S_3$ gives a final answer of $$\binom{i+2}{2}-3\binom{i+1-n}{2}+3\binom{i-2n}{2}-\binom{i-1-3n}{2}.$$

(correspondence fixed thanks to Thomas's helpful correction from his comment)

  • 1
    Your correspondence doesn't quite work, because it is possible for $y_1>2n+1,$ so that $y_1-(n+1)>n$.2011-12-14
2

Denote by $$\sum_{k=0}^{3n}{\binom{3}{k}}_{n+1}x^{k}=(1 + x + ... + x^{n})^3\,$$ the expansion of multinomial of degree $n$

From that relation follow that

$$ \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}\,$$

from binomial formula we have

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

and from Taylor formula

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

after substitutions we get

$$ \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}\,$$

then equate the coefficients next to x follow formula

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

formula for computing the coefficients of expansion

  • 0
    Note that the case $i=3$ always yields $2+k-(n+1)i<2$ so that term is zero. In particular, you have to be using ${m\choose 2} = 0$ if $m<2$, rather than ${m\choose 2} = m(m-1)/2$ for all $m$.2011-12-14
0

If the polynomial were replaced by an infinite sum, the coefficient of $x^i$ would be equal to the number of ways to choose $(a,b,c) \in \{0,1,2,...\}^3$ such that $a+b+c=i$. This is equal to the number of ways to choose two numbers $\le i$, or $\frac{1}{2}(i+1)(i+2)$. The only difference here is that you want to limit the count to cases where $a,b,c \le n$. Using the inclusion-exclusion principle, you can subtract the cases where one of the numbers is greater than $n$, add back the cases where two of the numbers are greater than $n$, and subtract the cases where all three are greater than $n$. For each of these counts, subtract $n+1$ (or $2n+2$ or $3n+3$) from the target sum first, returning you to the case where all three numbers are unrestricted. The result is $$ \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} $$ where $\Theta(x)=1$ for $x\ge 0$ and $0$ for $x<0$.