Publication at Faculty of Mathematics and Physics |
2006
Abstract
A matching on the vertex set [2n] can be represented as a sequence of length 2n of integers 1...n, where each integer occurs exactly twice and the first occurrence of an integer k precedes the occurrences of all the integers greater than k. We count the number of matchings whose representing sequence avoids the pattern 1123, as well as those avoiding the pattern 1132.
We achieve the enumeration by constructing a bijection between the corresponding set of matchings and a set of lattice paths with non-negativity constraints.