Help me to simplify $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}$

Question

I tried to simplify $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}$ by using generating function in the similar way of markus-scheuer's answer to the question How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$. What I got is $[u^r](1+u+u^2)^r$. I don't know how to compute the coefficient of $u^r$ in $(1+u+u^2)^r$. I tried using by trinomial expasion but I didn't suceed.

Answer 1

There is no closed form available for the central trinomial coefficients \begin{align*} [u^r](1+u+u^2)^r&=\sum_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}\binom{r-i}{r-2i} =\sum_{i=0}^{\lfloor r/2\rfloor}\binom{r}{2i}\binom{2i}{i} \end{align*}

Plausibility check:

We consider the more general expression $$\sum_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}\binom{r-i}{r-2i}t^{r-2i}$$ and obtain \begin{align*} \color{blue}{\sum_{i=0}^{\lfloor r/2\rfloor}}&\color{blue}{\binom{r}{i}\binom{r-i}{r-2i}t^{r-2i}}\\ &=\sum_{i=0}^\infty[z^{i}](1+z)^{r}[u^{r-2i}](1+tu)^{r-i}\tag{1}\\ &=[u^r](1+tu)^r\sum_{i=0}^\infty\left(\frac{u^2}{1+tu}\right)^i[z^i](1+z)^r\tag{2}\\ &=[u^r](1+tu)^r\left(1+\frac{u^2}{1+tu}\right)^r\tag{3}\\ &\color{blue}{=[u^r](1+tu+u^2)^{r}}\tag{4}\\ \end{align*}

We observe in case of $t=2$ the nice simplification \begin{align*} [u^r](1+2u+u^2)^{r}=[u^r](1+u)^{2r}=\binom{2r}{u} \end{align*} Regrettably there is no obvious similar simplification for other values of $t$.

Comment:

• In (1) we apply the coefficient of operator twice and set the upper limit of the sum to $\infty$ without changing anything, since we are adding zeros only.

• In (2) we use the linearity of the coefficient of operator, do some rearrangements and use the rule \begin{align*} [u^{p-q}]A(u)=[u^p]u^qA(u) \end{align*}

• In (3) we apply the substitution rule of the coefficient of operator with $z:=\frac{u^2}{1+tu}$ \begin{align*} A(u)=\sum_{i=0}^\infty a_i u^i=\sum_{i=0}^\infty u^i [z^i]A(z) \end{align*}

• In (4) we do some simplifications.

Notes from the experts:

D.E. Knuth gives in Concrete Mathematics, Appendix A 7.56 the following representation of a more general expression

\begin{align*} [u^r](a+bu+cu^2)^r=[u^r]\frac{1}{\sqrt{1-2bu+(b^2-4ac)u^2}} \end{align*}

He states that according to the paper Hypergeometric Solutions of Linear Recurrences with Polynomial Coeffcients by Marko Petkovšek there exists a closed form (more precisely: a closed form solution as a finite sum of hypergeometric terms) if and only if $$\color{blue}{abc(b^2-4ac)=0}$$

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

Answer 2

The central trinomial coefficient (A002426): the coefficient of $x^n$ in $(1+x+x^2)^n$, is given by:

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

because $i$ represents the number of $2$'s, $2n-2i-2\lfloor\frac{n}{2}\rfloor(=n-2i+n-2\lfloor\frac{n}{2}\rfloor)$ represents the number of $1$'s and $i$ represents the number of $0$'s in a partition of $n$ into $\{0,1,2\}$.

For example, $n=6$, we have $222000,221100,211110,111111$, represented in multinomial format as $303,222,141,6$.

So the sum is:

$$\frac{720}{3!0!3!}+\frac{720}{2!2!2!}+\frac{720}{1!4!1!}+\frac{720}{6!}$$ $$=20+90+30+1$$ $$=141$$