Mathematics – Combinatorics
Scientific paper
2005-03-16
European Journal of Combinatorics, vol. 28 (1), 202-213, 2007
Mathematics
Combinatorics
18 pages, 4 figures, important references added
Scientific paper
10.1016/j.ejc.2005.07.013
How many matchings on the vertex set V={1,2,...,2n} avoid a given configuration of three edges? Chen, Deng and Du have shown that the number of matchings that avoid three nesting edges is equal to the number of matchings avoiding three pairwise crossing edges. In this paper, we consider other forbidden configurations of size three. We present a bijection between matchings avoiding three crossing edges and matchings avoiding an edge nested below two crossing edges. This bijection uses non-crossing pairs of Dyck paths of length 2n as an intermediate step. Apart from that, we give a bijection that maps matchings avoiding two nested edges crossed by a third edge onto the matchings avoiding all configurations from an infinite family, which contains the configuration consisting of three crossing edges. We use this bijection to show that for matchings of size n>3, it is easier to avoid three crossing edges than to avoid two nested edges crossed by a third edge. In this updated version of this paper, we add new references to papers that have obtained analogous results in a different context.
No associations
LandOfFree
Dyck paths and pattern-avoiding matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dyck paths and pattern-avoiding matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dyck paths and pattern-avoiding matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-569195