Noncrossing partition
Encyclopedia
Free probability
Free probability is a mathematical theory that studies non-commutative random variables. The "freeness" or free independence property is the analogue of the classical notion of independence, and it is connected with free products....
. The set of all noncrossing partitions is one of many sets enumerated by the Catalan number
Catalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...
s.
Definition
A partition of a setPartition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
S is a pairwise disjoint set of non-empty subsets, 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. If one draws an arch based at a and b, and another arch based at x and y, then the two arches cross each other if the order is a x b y but not if it is a x y b or a b x y. In the latter two orders the partition { { a, b }, { x, y } } is noncrossing.
| Crossing: | a x b y |
| Noncrossing: | a x y b |
| Noncrossing: | a b x y |
Equivalently, if we label the vertices of a regular n-gon with the numbers 1 through n, the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
s 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 are denoted
. There is an obvious order isomorphism between 
and 
for two finite sets 
with the same size. That is, 
depends essentially only on the size of 
and we denote by 
the non-crossing partitions on any set of size n.Lattice structure
Like the set of all partitions of the set { 1, ..., n }, the set of all noncrossing partitions is a latticeLattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
when partially ordered
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
by saying that a finer partition is "less than" a coarser partition. However, although it is a subset of the lattice of all partitions, it is not a sublattice of the lattice of all partitions, because the join operations do not agree. In other words, the finest partition that is coarser than both of two noncrossing partitions is not always the finest noncrossing partition that is coarser than both of them.
Unlike the lattice of all partitions of the set, the lattice of all noncrossing partitions of a set 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 complement. Indeed, every interval within this lattice is self-dual.
Role in free probability theory
The lattice of noncrossing partitions plays the same role in defining "free cumulants" in free probabilityFree probability
Free probability is a mathematical theory that studies non-commutative random variables. The "freeness" or free independence property is the analogue of the classical notion of independence, and it is connected with free products....
theory that is played by the lattice of all partitions in defining joint cumulants in classical probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
. To be more precise, let
be a non-commutative probability space, 
a non-commutative random variable with free cumulants 
. (See free probabilityFree probability
Free probability is a mathematical theory that studies non-commutative random variables. The "freeness" or free independence property is the analogue of the classical notion of independence, and it is connected with free products....
for terminology.) Then
where
denotes the number of blocks of length 
in the non-crossing partition 
.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.
See also Wigner semicircle distribution.