Central trinomial coefficient as number of lattice paths

Question

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.

Answer 1

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)] $$