Enumeration of \((k,2)\)-noncrossing partitions (Q941401): Difference between revisions

A partition \(\Pi\) of the set \([n]=\{1,2,\dots, n\}\) is a collection \(B_1,B_2,\dots, B_d\) of nonempty disjoint subsets of \([n]\), where \(B_1,B_2,\dots, B_d\) are listed in increasing order of their minimum elements. Let \(P(n, d)\) be the set of all partitions of \([n]\) with \(d\) blocks; the cardinality of \(P(n, d)\) is the Stirling number of the second kind. Any partition \(\Pi\) can be written in the canonical sequential form \(\pi = \pi_1\pi_2\dots \pi_n\), where J\(i\in B_{\pi_i}\). A reduced form of \(\pi\) on \(\{a_1,a_2,\dots, a_d\}\), where \(a_1 < a_2 < \dots < a_d\) is a word \(\pi'\) resulting from renaming the letters of \(\pi\). \textit{M. Klazar} [Eur. J. Comb. 17, No. 1, 53--68 (1996; Zbl 0840.05004)] showed that the number of noncrossing partitions of \([n]\) (partitions avoiding 1212), and the number of nonnesting partitions of \([n]\) avoiding 1221 are given by the \(n\)th Catalan number. A \(k\)-noncrossing partition avoids \(12\dots k12\dots k\) and a \((k,d)\)-noncrossing partition avoids \(12\dots k12\dots d\). The author constructs generating functions for the \((k,d)\)-noncrossing partitions of \([n]\) in the cases \(d= 1\) or \(2\).