Find the $x^n$ coefficient of $(1+x+x^2)^n$ 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.
 A: 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}$$
A: 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$
A: 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.
A: 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}$$
A: 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
