Find the $x^n$ coefficient of $(1+x+x^2)^n$

Question

I've tried a bunch of different groupings of the three terms so that I could use the binomial expansion forumula, but I haven't been able to go much further than that. This is an example of what I've tried so far: $$(1+x+x^2)^n=\sum_{n=0}^{\infty} {n \choose k}(1+x)^{n-k}x^{2k} =\sum_{k=0}^{\infty}\sum_{i=0}^{\infty}{n \choose k}{{n-k} \choose i}x^{2k+i}$$

I decided to show this as it has the closest looking coefficient to the expected answer, which states that the coefficient of $x^n$ is $$\sum_{k=0}^{n}{n \choose k}{{n-k} \choose k}$$. I'm assuming I'm taking the wrong approach so I'd appreciate some input.

Answer 1

The terms that contribute to the coefficient on $x^n=x^{2k+i}$ can be thought of summing over the ways of writing $n$ as $2k+i=n$,

$$\sum_{2k+i=n} \binom{n}{k}\binom{n-k}{i}$$

Since $i=n-2k$ we can replace it in the binomial term $\binom{n-k}{i}=\binom{n-k}{n-2k}=\binom{n-k}{n-k-(n-2k)}=\binom{n-k}{k}$,

$$\sum_{2k+i=n} \binom{n}{k}\binom{n-k}{k}$$

The terms of the sum no longer have any dependence on $i$, so we can fixate on what values of $k$ are valid. Every choice of $k$ will automatically have a unique choice of $i$ that make $n$, if $n$ is even we can go all the way up to $2(\frac{n}{2})+0=n$ and if $n$ is odd we can go all the way up to $2(\frac{n-1}{2})+1=n$, so $k$ goes up to $\lfloor \frac{n}{2}\rfloor$,

$$\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k}\binom{n-k}{k}$$

Answer 2

Essentially you want as many $1$s as $x^2$s, but not more than $\frac n2$ of either

If you have $k$ of $1$s and $k$ of $x^2$s then you also have $n-2k$ of $x$s and these can be in any order so I would have written

$$\sum\limits_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{k!^2(n-2k)!}=\sum\limits_{k=0}^{\lfloor n/2 \rfloor} {n \choose k}{n-k \choose k}$$

As Mike Earnest has observed, this is the same as the expected answer since for larger $k$ you have ${n-k \choose k}=0$

Answer 3

Hint: There is no closed formula available for $$\sum_{k=0}^{n}{n \choose k}{{n-k} \choose k}$$

In fact it can be shown that \begin{align*} [x^n](a+bx+cx^2)^n=[x^n]\frac{1}{\sqrt{1-2bx+(b^2-4ac)x^2}} \end{align*} has a closed form solution if and only if $$abc(b^2-4ac)=0$$

In case of central trinomial coefficients we have $a=b=c=1$. Since then the expression $$\color{blue}{abc(b^2-4ac)=-3\ne 0}$$ there is no such closed form for the central trinomial coefficients.

A somewhat more detailed information is given in this answer.

Answer 4

This is same as the number of ways we can distribute $n$ balls among $n$ kids such that each receive $0,1$ or $2$ balls. Suppose $a$ kids receive $1$ ball and $b$ kids receive $2$ balls then there are $n-a-b$ kids who does not recieve a ball. $a+2b=n$ because the total number of balls is $n$ .

You can choose $b$ kids out of $n$ kids to give $2$ balls and $a$ balls out of the remaing $n-b$ kids to give $1$ ball.
This same as $${n \choose b}{n-b \choose a}={n \choose b}{n-b \choose n-2b}={n \choose b}{n-b \choose b}$$
$0\le b\le\lceil n/2\rceil$ so the total number of ways is $$\sum_{i=0}^{\lceil n/2\rceil}{n \choose b}{n-b \choose b}$$

Answer 5

For another way , let say that $$(1+x+x^2)^n= \bigg(\frac{1-x^3}{1-x} \bigg)^n$$

Then , it is obvious that $$\bigg(\frac{1-x^3}{1-x} \bigg)^n = (1-x^3)^n \times \bigg(\frac{1}{1-x} \bigg)^n$$

We can conclude that we obtain two $x$ values from this expression and the summation of their exponentials will be equal to $n$. So , lets say that our exponential coming from $(1-x^3)^n$ is equal to $3m$ (because $x^3$ gives always the exponentials which are multiplications of $3$ , and exponential coming from $\bigg(\frac{1}{1-x} \bigg)^n$ is equal to $k$. Then , $3m+k=n$..

We can see that $$\binom{n}{m}(-1)^m(x^{3m})\times \binom{n+k-1}{k}x^k$$ where $3m+k=n$

The bad aspect of this approach , you should see the all solutions for $m$ and $k$.However ,it is good for small numbers.For example , lets assume that $n=5$ , then $(m=0,k=5)$ or $(m=1 , k=2)$

In that cases ,

• If $(n=5,m=0,k=5)$ then $$\binom{5}{0}(-1)^0 \times \binom{5+5-1}{5}=126$$

• If $(n=5,m=1,k=2)$ then $$\binom{5}{1}(-1)^1 \times \binom{5+2-1}{2}=-75$$

Then , $126+(-75)=51$

CALCULATION BY WOLFRAM-ALPHA