Surprising Symmetries in Objects Counted by Catalan Numbers

  • Miklós Bóna
Keywords: permutations, patterns, plane trees, bijection

Abstract

We prove that the total number $S_{n,132}(q)$ of copies of  the pattern $q$ in all 132-avoiding permutations of length $n$ is the same for $q=231$, $q=312$, or $q=213$. We provide a combinatorial proof for this unexpected threefold symmetry. We then significantly generalize this result by proving a large family of non-trivial  equalities of the type $S_{n,132}(q)=S_{n,132}(q')$.

Author Biography

Miklós Bóna, University of Florida
Department of Mathematics
Published
2012-03-31
Article Number
P62