Motzkin paths and central trinomial coefficient Let $ a_n $ be the coefficient of $ X^n $ in the polynomial: $ (1+X+X^2)^n $.
I would like to prove that $ a_n=\sum\limits_{k=0}^{k=\lfloor n/2\rfloor} \frac{n!}{(k!)^2(n-2k)!}$ is the number of Motzkin paths joining $ (0,0) $ to $ (n,0) $. How can I find a solution (using combinatorics, I guess)?
 A: The given formula for $a_n$ is not equal to the number of Motzkin paths connecting $(0,0)$ to $(n,0)$. For example for $n = 4$ it should be $9$, while the formula gives $13$. 
If you were looking to verify that $a_{n}=\sum_{k=0}^{k=\lfloor{n/2}\rfloor} \frac{n!}{(k!)^2(n-2k)!}$ is the coefficient of $X^n$ in $(1+X+X^2)^n$, then my earlier explanation does hold. For each $k$, the summand counts the number of ways to get a factor $X^n$ by taking  $k$ times a $1$, $n - 2k$ times an $X$ and $k$ times an $X^2$. Summing over all $k \leq n/2$, you then get all terms contributing to the coefficient of $X^n$.
If instead you were looking for formulas of Motzkin numbers, then Wolfram MathWorld and OEIS:A001006 should give you plenty of (correct) formulas. However the one you gave does not work.

Below is a proof for the formula, which anon mentioned in the comments.

Theorem The number of Motzkin paths from $(0,0)$ to $(n,0)$ is given by
  $$a_n = \sum_{k=0}^{[n/2]}\frac{n!}{k!(k+1)!(n-2k)!} = \frac{1}{n+1} \sum_{k=0}^{[n/2]} \binom{n+1}{k,k+1,n-2k}$$

Proof: The proof is analogous to the proof of the formula of the Catalan numbers (in particular the second proof). We first count all paths from $(0,0)$ to $(n,0)$ which may drop below the axis (denoted by $b_n$), then subtract all paths that indeed cross the axis (denoted by $c_n$), so that we finally get the desired number $a_n = b_n - c_n$.
Lemma 1: The total number of paths from $(0,0)$ to $(n,0)$ is 
$$b_n = \sum_{k=0}^{[n/2]}\frac{n!}{k!k!(n-2k)!} = \sum_{k=0}^{[n/2]} \binom{n}{k,k,n-2k}$$
Proof: Any path can be created by first selecting the number of up- and downmoves ($k$), and then deciding at which of the $n$ positions we move up and down. This means we have to partition $n$ in three sets of size $k$ (move up), $k$ (move down) and $n - 2k$ (horizontal movement). Summing over all values of $k$ we get the result.
Lemma 2: The number of paths from $(0,0)$ to $(n,0)$ crossing the axis is
$$c_n = \sum_{k=0}^{[n/2]}\frac{n!}{(k-1)!(k+1)!(n-2k)!} = \sum_{k=0}^{[n/2]} \binom{n}{k-1,k+1,n-2k}$$
Proof: Here we use a similar argument as on Wikipedia. If a path crosses below the axis, then it must do so for the first time once. After this point, we are at $(i,-1)$. We now flip the remaining part of the path, i.e. moving up becomes moving down and moving down becomes moving up. This flipped path will end up at $(n,-2)$ rather than $(n,0)$. In fact, there is a one-to-one correspondence between these flipped paths, and paths from $(0,0)$ to $(n,-2)$. By similar reasoning, such paths can be constructed by selecting a $k$, and moving down $k+1$ times and up $k-1$ times. This gives the result.
We now complete the proof of the theorem. 
$$\begin{array}{rcl}
a_n &=& b_n - c_n \\
&=& \sum_{k=0}^{[n/2]}\frac{n!}{k!k!(n-2k)!} - \sum_{k=0}^{[n/2]}\frac{n!}{(k-1)!(k+1)!(n-2k)!} \\
&=& \sum_{k=0}^{[n/2]} \frac{n!}{(k-1)!k!(n-2k)!} \left(\frac{1}{k} - \frac{1}{k+1}\right) \\
&=& \sum_{k=0}^{[n/2]} \frac{n!}{(k-1)!k!(n-2k)!} \left(\frac{1}{k(k+1)}\right) \\
&=& \sum_{k=0}^{[n/2]} \frac{n!}{k!(k+1)!(n-2k)!} \\
&=& \frac{1}{n+1} \sum_{k=0}^{[n/2]} \binom{n+1}{k,k+1,n-2k}
\end{array}$$
A: Let's rewrite the formula for the Motzkin numbers as follows:
$$
M_n=\sum_{k}\frac{n!}{k!(k+1)!(n-2k)!} = \sum_{k}\binom{n}{2k}\frac{1}{k+1}\binom{2k}{k}=\sum_{k}\binom{n}{2k}C_k,
$$
where the index $k$ ranges overs all values where the summands are nonzero (i.e. $0\le k\le\left\lfloor \frac{n}{2}\right\rfloor$), and $C_k$ is the $k$th Catalan number, which counts the number of Dyck paths from $(0,0)$ to  $(2k,0)$. Note that Dyck paths are just Motzkin paths that have no level steps. Now every Motzkin path can be uniquely constructed as follows:


*

*Choose an integer $k$ such that $0\le 2k\le n$.

*Choose a Dyck path $P$ of length $2k$ in $C_k$ ways.

*Choose a $2k$-element subset of $S\subseteq\{1,\dots,n\}$ in $\binom{n}{2k}$ ways.

*Insert the steps of $P$ in the positions in $S$ in the order in which they occur, then fill the remaining positions with the level steps.
This immediately yields the formula above.
