On trees and noncrossing partitions (Q1383385)

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 holds \[ \bigl| {\mathfrak P} (n,k;t) \bigr|= \bigl| {\mathfrak P}_2 (n-1,k-1;t-1) \bigr| \tag{4} \] for all integers \(n,k\) and \(t\) \((t\geq 2)\). To prove this last fact the author uses interplay of partitions on initial segments of \(\mathbb{N}\) with sequences of natural numbers. Any such sequence \(a=(a_1,a_2, \dots, a_n)\) uniquely determines the partition \({\mathbf P} =(\overline n; \pi)\), where \(i\) and \(j\) are considered to be in the same \(\pi\)-part iff \(a_i= a_j\). A sequence \(a\) is called normal iff \(\{a_1, \dots, a_n\}= \{1,\dots, k\}\) with \(k=n (\pi)\) and \(1\leq i<j\leq n\) implies that the first \(i\)-occurrence in \(a\) precedes the first \(j\)-occurrence. Let \({\mathfrak A}\) be the set of all nonempty normal noncrossing sequences \(a\) with \((a)\geq 2\), and let \({\mathfrak B}\) be the subset of all poor normal noncrossing sequences (empty sequence included). Using the standard lexicographical ordering \(\prec\) of sequences the author proves (Theorem 2.1) that there exists an isomorphism \(\Phi: ({\mathfrak A}; \prec)\to ({\mathfrak B}; \prec)\) such that, for any \(a \in {\mathfrak A}\), one has \(|\Phi (a)|+ 1=| a|\), \(\|\Phi (a)\| +1=\| a\|\), and \((\Phi(a)) +1=(a)\). This gives (4).