Matchings Avoiding Partial Patterns and Lattice Paths

  • Vít Jelínek
  • Nelson Y. Li
  • Toufik Mansour
  • Sherry H. F. Yan

Abstract

In this paper, we consider matchings avoiding partial patterns $1123$ and $1132$. We give a bijection between $1123$-avoiding matchings with $n$ edges and nonnegative lattice paths from $(0,2)$ to $(2n,0)$. As a consequence, the refined enumeration of $1123$-avoiding matchings can be reduced to the enumeration of certain lattice paths. Another result of this paper is a bijection between $1132$-avoiding matchings with $n$ edges and lattice paths from $(0,0)$ to $(2n,0)$ starting with an up step, which may go under the $x$-axis.

Published
2006-10-19
Article Number
R89