# Central trinomial coefficient as number of lattice paths

I have been interested in properties of the polynomials $$T(n,s,t)=\sum{\binom{n}{2j}\binom{2j}{j}t^{n-2j}s^j}.$$ They occur as coefficient of $$x^n$$ of $$(1+tx+sx^2)^n$$.

On the other hand they can also be interpreted as the weight of the set of lattice paths from $$(0,0)$$ to $$(n,0)$$ whose allowed steps are up-steps $$(1,1)$$, down-steps $$(1,-1)$$ and horizontal steps $$(1,0),$$ where the weight of an up-step is $$1$$, the weight of a down-step is $$s$$, the weight of a horizontal step is $$t$$, the weight of a path is the product of the weights of its steps and the weight of a set of paths is the sum of their weights.

For $$s=t=1$$ this reduces to the fact that the number $$T_n$$ of the above set of lattice paths is the trinomial coefficient $$t_n=T(n,1,1)$$.

This is a combinatorial statement and I wanted a purely combinatorial proof of this fact, which does not need the above formula. Such a proof has been given by Mike Earnest. Therefore my question has been answered.

It would be interesting if there is also a combinatorial proof for the general case.

• $(n,0)$ rather than $(0,n)$? Jun 17 at 12:20
• Yes of course. Thank you for noting this typo. Jun 17 at 13:05

## 1 Answer

By applying the distributive property, we see that $$(1+x+x^2)^n=\sum_{i_1=0}^2\sum_{i_2=0}^2\cdots \sum_{i_n=0}^2 x^{i_1}x^{i_2}\cdots x^{i_n}\tag1$$ In words, for each $$k\in \{1,\dots,n\}$$, $$i_k$$ represents the power of $$x$$ selected from the $$k^\text{th}$$ copy of $$(1+x+x^2)$$.

To calculate $$t_n$$, we only care about summands in $$(1)$$ which contribute to $$x^n$$. For each way of choosing the sequence $$(i_1,\dots,i_n)$$ defining a term in the sum, there is a contribution of $$+1$$ to the coefficient of $$x^{i_1+\dots+i_n}$$. This proves $$t_n$$ is the number of valid sequences. That is, $$t_n=\#\{(i_1,i_2,\dots,i_n)\mid \forall k: i_k\in \{0,1,2\}, i_1+\dots+i_n=n\}$$ Here is where the bijective proof comes in. We have represented $$t_n$$ in terms of sequences of $$\{0,1,2\}$$ with length $$n$$. If you subtract one from each entry of such a sequence, you get a sequence with entries in $$\{-1,0,1\}$$, corresponding to the possible $$y$$-coordinates of a step for your lattice paths. That is, the bijection from the $$\{0,1,2\}$$-sequences counted by $$t_n$$ to the lattice paths counted by $$T_n$$ is $$(i_1,i_2,\dots,i_n)\mapsto [(1,i_1-1),(1,i_2-1),\dots,(1,i_n-1)]$$

• Thank you, this is the proof I looked for. Jun 18 at 6:45