2
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you, this is the proof I looked for. $\endgroup$ Jun 18 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.