Enumeration of \((k,2)\)-noncrossing partitions (Q941401): Difference between revisions
From MaRDI portal
Latest revision as of 16:12, 28 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumeration of \((k,2)\)-noncrossing partitions |
scientific article |
Statements
Enumeration of \((k,2)\)-noncrossing partitions (English)
0 references
4 September 2008
0 references
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\).
0 references
partitions
0 references
forbidden subsequences
0 references
kernel method
0 references