Noncrossing partition

In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory of free probability.

The number of noncrossing partitions of an n-element set with k blocks is found in the Narayana number triangle.

A partition of a set S is a set of non-empty, pairwise disjoint subsets of S, called "parts" or "blocks", whose union is all of S. Consider a finite set that is linearly ordered, or (equivalently, for purposes of this definition) arranged in a cyclic order like the vertices of a regular n-gon.

No generality is lost by taking this set to be S = { 1, ..., n }.

A noncrossing partition of S is a partition in which no two blocks "cross" each other, i.e., if a and b belong to one block and x and y to another, they are not arranged in the order a x b y.

Equivalently, if we label the vertices of a regular n-gon with the numbers 1 through n, the convex hulls of different blocks of the partition are disjoint from each other, i.e., they also do not "cross" each other.

The set of all non-crossing partitions of S is denoted

However, although it is a subset of the lattice of all set partitions, it is not a sublattice, because the subset is not closed under the join operation in the larger lattice.

Unlike the lattice of all partitions of the set, the lattice of all noncrossing partitions is self-dual, i.e., it is order-isomorphic to the lattice that results from inverting the partial order ("turning it upside-down").

This can be seen by observing that each noncrossing partition has a non-crossing complement.

The lattice of noncrossing partitions plays the same role in defining free cumulants in free probability theory that is played by the lattice of all partitions in defining joint cumulants in classical probability theory.

a non-commutative random variable with free cumulants

denotes the number of blocks of length

That is, the moments of a non-commutative random variable can be expressed as a sum of free cumulants over the sum non-crossing partitions.

This is the free analogue of the moment-cumulant formula in classical probability.