Lattice Polynomials, 12312-Avoiding Partial Matchings and Even Trees

Abstract

The lattice polynomials $L_{i,j}(x)$ are introduced by Hough and Shapiro as a weighted count of certain lattice paths from the origin to the point $(i,j)$. In particular, $L_{2n,n}(x)$ reduces to the generating function of the numbers $T_{n,k}=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n-1+k}{n-1}\right)\left(\genfrac{}{}{0ex}{}{2n-k}{n+1}\right)$, which can be viewed as a refinement of the $3$-Catalan numbers $T_n=\frac{1}{2n+1}\left(\genfrac{}{}{0ex}{}{3n}{n}\right)$. In this paper, we establish a correspondence between $12312$-avoiding partial matchings and lattice paths, and we show that the weighted count of such partial matchings with respect to the number of crossings in a more general sense coincides with the lattice polynomials $L_{i,j}(x)$. We also introduce a statistic on even trees, called the $r$-index, and show that the number of even trees with $2n$ edges and with $r$-index $k$ equal to $T_{n,k}$.

11 pages, 9 figures