The existence of apparently coincidental equalities (also called Wilf-equivalences) between the enumeration sequences or generating functions of various hereditary classes of combinatorial structures has attracted significant interest. We investigate such coincidences among non-crossing matchings and a variety of other Catalan structures including Dyck paths, 231-avoiding permutations and plane forests. In particular we consider principal subclasses defined by not containing an occurrence of a single given structure. An easily computed equivalence relation among structures is described such that if two structures are equivalent then the associated principal subclasses have the same enumeration sequence. We give an asymptotic estimate of the number of equivalence classes of this relation among structures of size $n$ and show that it is exponentially smaller than the $n^{th}$ Catalan number. In other words these "coincidental" equalities are in fact very common among principal subclasses. Our results also allow us to prove in a unified and bijective manner several known Wilf-equivalences from the literature.
@article{10_37236_5629,
author = {Michael Albert and Mathilde Bouvel},
title = {A general theory of {Wilf-equivalence} for {Catalan} structures},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {4},
doi = {10.37236/5629},
zbl = {1329.05006},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5629/}
}
TY - JOUR
AU - Michael Albert
AU - Mathilde Bouvel
TI - A general theory of Wilf-equivalence for Catalan structures
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/5629/
DO - 10.37236/5629
ID - 10_37236_5629
ER -
%0 Journal Article
%A Michael Albert
%A Mathilde Bouvel
%T A general theory of Wilf-equivalence for Catalan structures
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5629/
%R 10.37236/5629
%F 10_37236_5629
Michael Albert; Mathilde Bouvel. A general theory of Wilf-equivalence for Catalan structures. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/5629
