Crossings and nestings in colored set partitions

Abstract

Chen, Deng, Du, Stanley, and Yan 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 \emph{$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 $\NN^r$, generalizing the correspondence between noncrossing (uncolored) set partitions and 2-Motzkin paths. Combining this with recent work of Bousquet-Mélou and Mishna 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.

arXiv comment25 pages; v2: material revised and condensed; v3 material further revised, additional section added