On trees and noncrossing partitions
type: Item
instance of: scholarly article
title: On trees and noncrossing partitions
zbMATH Open document ID: 0904.05003
DOI: 10.1016/S0166-218X(97)00118-2
author: Martin Klazar
published in: Discrete Applied Mathematics
publication date: 1999-01-11T00:00:00Z
full work available at URL: dam
review text: Bijective proofs of some identities for partitions are given. In this paper a partition is a pair \({\mathbf P} =(P;\pi)\), with \(P\) a (finite) ground set together with a set-theoretical partition \[ \pi= \left\{P_1, \dots, P_k\left|\varnothing \neq P_i\subseteq P\text{ and }P = \bigcup^k_{i=1} P_i\right.\right\}. \] Such a partition (for \(P= \overline n=\{1,2, \dots, n\})\) is called noncrossing if there do not exist four distinct elements \(a<b<c<d\) and two distinct \(\pi\)-parts \(P_i\) and \(P_j\) such that \(\{a,c\} \subseteq P_i\) and \(\{b,d\} \subseteq P_j\). A partition \({\mathbf P}\) is called poor if every part of it has at most two elements. For a partition \({\mathbf P}\) we set \( | {\mathbf P} |= | P|\), \(\| {\mathbf P} \|= n(\pi)=k\), and \(({\mathbf P}) =\min \{ | y-x| \mid x\neq y\) and \(\{x,y\} \subseteq P_i\) for some \(i\}\). Further, denote by \({\mathfrak P} (n,k;t)\) the set of all noncrossing partitions \({\mathbf P}\) with \(| {\mathbf P} |=n\), \(\| {\mathbf P} \|=k\) and \(({\mathbf P}) \geq t\). Let \({\mathfrak P}_2 (n,k;t)\) be the set of all poor partitions in \({\mathfrak P} (n,k;t)\). The author gives bijective proofs for the identities \[ \begin{aligned} \bigl | {\mathfrak P} (n,k;1) \bigr| & ={1\over n} {n\choose k} {n\choose k-1} \tag{1}\\ \bigl| {\mathfrak P} (n,k;2) \bigr| & ={1\over n-k+1} {2n-2k\choose n-k} {n-1\choose 2n-2k} \tag{2}\\ \bigl | {\mathfrak P} (n,k;3) \bigr| & ={1\over k-1} {k-1\choose n-k+1} {k-1\choose n-k}. \tag{3} \end{aligned} \] Other proofs for (1) by \textit{G. Kreweras} [Discrete Math. 1, 333-350 (1972; Zbl 0231.05014)] and for (2) by \textit{D. Gardy} and \textit{D. Gouyou-Beauchamps} [Inform. Theor. Appl. 26, No. 5, 387-402 (1992; Zbl 0769.05007)] have been known. An equivalent to (3) was found by \textit{W. R. Schmitt} and \textit{M. S. Waterman} [Discrete Appl. Math. 51, No. 3, 317-323 (1994; Zbl 0799.92006)]. The proofs of (2) and (3) in this paper use the following fact (Theorem 1.1): it ho…
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1139446
zbMATH Keywords: trees
zbMATH Keywords: identities for partitions
zbMATH Keywords: noncrossing partitions
zbMATH Keywords: normal noncrossing sequences
reviewed by: U. Kaljulaid
MaRDI profile type: Publication
cites work: A general bijective algorithm for trees.
cites work: Chain enumeration and non-crossing partitions
cites work: Enumerating Davenport-Schinzel sequences
cites work: Q4881920
cites work: On \(abab\)-free and \(abba\)-free set partitions
cites work: Combinatorial aspects of Davenport-Schinzel sequences
cites work: Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
cites work: Étude et denombrement parallèles des partitions non-croisees d'un cycle et des decoupages d'un polygone convexe
cites work: Catalan numbers revisited
cites work: Linear trees and RNA secondary structure
cites work: Q4325546
cites work: Combinatorial statistics on non-crossing partitions
cites work: On the structure of the lattice of noncrossing partitions
cites work: On some new sequences generalizing the Catalan and Motzkin numbers
cites work: Q4871787
Recommended article: Ordered trees and non-crossing partitions
Recommended article: On tree partitions
Recommended article: TREE STRUCTURES ON CERTAIN FAMILIES OF PARTITIONS
Recommended article: On tree-partitions of graphs
Recommended article: On the partition dimension of trees
Recommended article: Q6102505
Recommended article: Partition complexes and trees
Recommended article: Aronszajn trees and partitions
Recommended article: Partitionability of trees
Recommended article: Partitions and normal trees
description: scientific article; zbMATH DE number 1139446