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

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