A noncrossing partition is a set partition of a cyclically ordered finite set such that no two distinct
set blocks interlace. For labels 1, 2, ..., 
in cyclic order, this means there are no 
with 
and 
in one set block and 
and 
in another. Equivalently, placing the labels on a circle
makes the convex hulls of distinct set
blocks disjoint (Simion 2000). Labels are fixed;
rotations and reflections are not identified.
The number of noncrossing partitions of 
labels is the Catalan number
 |
(1)
|
The number with exactly 
set blocks is the Narayana
number
 |
(2)
|
for 
(Simion 2000). Excluding singleton set blocks gives
the Riordan numbers.
If every set block has at least three elements, its convex hull is a polygon.
These disjoint polygons
partition the vertices, rather than dissecting the entire polygonal area. The number
with 
set blocks is
 |
(3)
|
for 
(OEIS A350248). With 
, the generating
function 
satisfies
![F(z,u)=1+(u[zF(z,u)]^3)/(1-zF(z,u)).](/images/equations/NoncrossingPartition/NumberedEquation4.svg) |
(4)
|
The set block containing the first label separates the remaining labels into gaps, each carrying an independent noncrossing partition of
the same kind. This gives the functional equation;
Lagrange inversion theorem then gives
. The total counts for 
, 1, 2, ... are 1, 0, 0, 1, 1, 1, 4, 8, 13, 31, ...
(OEIS A114997). In particular, a labeled hexagon has three partitions into two triangles,
in addition to its single-block partition.
