Noncrossing partitions
published on October 13, 2023.
Noncrossing partitions are partitions $\pi$ of some linearly ordered set such that “no two blocks cross each other”: for any two blocks $A,B\in\pi$, $$\Bigl(\exists(i < j < k < \ell):\ i,k\in A\text{ and }j,\ell\in B\Bigr)\implies A=B.$$
Below are two examples of partitions of $\{1,\ldots,10\}$. Partition (b) is noncrossing whereas partition (a) is not noncrossing.
(a) $\Bigl\{\{1,6\},\{2,3,4,7\},\{5\},\{8,10\},\{9\}\Bigr\}$
(b) $\Bigl\{\{1,8\},\{2,3\},\{4,7\},\{5,6\},\{9,10\}\Bigr\}$
Figure 1. Two types of partitions.
## Enumerating noncrossing partitions
Focusing on the block containing the lowest element, one can see that each noncrossing partition $\pi$ is decomposed unambiguously as
where $k\ge1$ is the number of segments in that block, with respective lengths $n_1,\ldots,n_k\ge1$,
and $\pi_1,\ldots,\pi_k$ are noncrossing partitions with $\pi_1,\ldots,\pi_{k-1}$ non-empty.
Letting $\mathrm{NC}(n)$ denote the set of noncrossing partitions of $[n]:=\{1,\ldots,n\}$, it follows that the generating function
$$C(z):=\sum_{n\ge0}\sum_{\pi\in\mathrm{NC}(n)}z^n$$
fulfills (note that $\mathrm{NC}(0)=\{\emptyset\}$ is reduced to the empty partition)
$$C=1+\sum_{k\ge1}\sum_{n_1,\ldots,n_k\ge1}z^{n_1+\cdots+n_k}{(C-1)}^{k-1}\,C=\frac1{1-zC}.$$
This easily solves to $C(z)=\frac{1-\sqrt{1-4 z}}{2 z}$, the generating function of the ubiquitous Catalan numbers, $|\mathrm{NC}(n)|:=[z^n]\,C(z)=\frac1{n+1}\binom{2n}n$.
The following pure Python3 code generates all noncrossing partitions of a given sequence.
Python code.
## Noncrossing pair partitions
These are noncrossing partitions in which every block has cardinal $2$, such as the partition in Figure 1.(b). We can transform a noncrossing pair partition into a noncrossing partition thanks to the following inductive procedure $T$:
- $T(\emptyset)=\emptyset$;
- For any noncrossing pair partitions $\pi$ and $\pi'$,
$T\Biggl($
$\Biggr)\enspace=\enspace$
,
that is, we append an extra element $\bullet$ to the block of $T(\pi)$ containing the lowest element, and then concatenate $T(\pi')$ to the right.
For instance, applying $T$ to the noncrossing pair partition of Figure 1.(b) results in the noncrossing partition
This procedure is easily reversed and as it halves the total number of elements $\bullet$, the map $T$ induces a bijection between $\mathrm{NC}(n)$ and the set $\mathrm{NC}_2(2n)$ of all noncrossing pair partitions of $[2n]$. In particular, $|\mathrm{NC}_2(2n)|=|\mathrm{NC}(n)|$.
The following pure Python3 code generates all noncrossing pair partitions of a given sequence.
Python code.
