Pattern avoidance in canon permutations

Abstract

A canon permutation is a $k$-regular word over $[n]$ in which, for each $j$, the $j$-th copies of the letters form the same permutation $\sigma$. These were introduced by Elizalde as a generalization of nonnesting multipermutations, which are the case $k=2$. We study classical pattern avoidance in them for arbitrary $k$. We show that avoiding any one of $112$, $122$, $211$ or $221$ is counted by the $k$-Catalan numbers $\frac{1}{n}\left(\genfrac{}{}{0ex}{}{kn}{n-1}\right)$. We enumerate the classes obtained by forbidding one of these together with any $\tau \in {\mathcal{S}}_3$, and we give a bijection with $k$-ary trees that we use to generalize a theorem of Gabriel, Peske, Pudwell and Tay. We then show that avoiding a set of patterns closed under relabeling reduces, up to a factor of $n!$, to avoidance in $k$-regular lattice words. We use this to enumerate the canon permutations avoiding some natural generalizations of the nonnesting and noncrossing patterns, as well as the family $\{1^{a}21^b,2^{a}12^b\}$. We close with several conjectures and questions.

23 pages