Crossings and nestings in colored set partitions (Q396914): Difference between revisions

Summary: \textit{W. Y. C. Chen} et al. [Trans. Am. Math. Soc. 359, No. 4, 1555--1575 (2007; Zbl 1108.05012)] introduced the notion of \(k\)-crossings and \(k\)-nestings for set partitions, and proved that the sizes of the largest \(k\)-crossings and \(k\)-nestings in the partitions of an \(n\)-set possess a symmetric joint distribution. This work considers a generalization of these results to set partitions whose arcs are labeled by an \(r\)-element set (which we call \(r\)-colored set partitions). In this context, a \(k\)-crossing or \(k\)-nesting is a sequence of arcs, all with the same color, which form a \(k\)-crossing or \(k\)-nesting in the usual sense. After showing that the sizes of the largest crossings and nestings in colored set partitions likewise have a symmetric joint distribution, we consider several related enumeration problems. We prove that \(r\)-colored set partitions with no crossing arcs of the same color are in bijection with certain paths in \(\mathbb{N}^r\), generalizing the correspondence between noncrossing (uncolored) set partitions and 2-Motzkin paths. Combining this with recent work of \textit{M. Bousquet-Mélou} and \textit{M. Mishna} [Contemp. Math. 520, 1--39 (2010; Zbl 1209.05008)] affords a proof that the sequence counting noncrossing 2-colored set partitions is P-recursive. We also discuss how our methods extend to several variations of colored set partitions with analogous notions of crossings and nestings.