Taylor series for $(x^n + x^m + 1)^s$

Question

Using the trinomial theorem one gets that $$ [x^t](x^n + x^m + 1)^s = \sum_{\substack{i + j + k = s\\mi + nj = t}}{s \choose i,j,k}. $$ I was wondering if one could point out to me a reference (I'm guessing in combinatorics) where this sum shows up? Any applications? Also does the sum simplify nicely (meaning a simpler identity) in special cases of $m,n$? Thanks.

Answer 1

One combinatorial interpretation is based upon lattice paths on a $\mathbb{Z}\times\mathbb{Z}$ grid with steps $(1,1),(1,0)$ and $(1,-1)$. Walks of length $n$ can be represented by the generating function \begin{align*} \left(xy+x+xy^{-1}\right)^n\qquad\text{or}\qquad\left(1+x+x^2\right)^n \end{align*}

Strongly connected with trinomial coefficients are Motzkin numbers.

You may want to check this classic from P. Flajolet and R. Sedgewick for more info.