×

Surprising symmetries in objects counted by Catalan numbers. (English) Zbl 1243.05006

Summary: 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')\).

MSC:

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: EMIS