In
combinatorial mathematics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory of
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.
This theory was in ...
. The number of noncrossing partitions of a set of ''n'' elements is the ''n''th
Catalan number
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
. The number of noncrossing partitions of an ''n''-element set with ''k'' blocks is found in the
Narayana number
In combinatorics, the Narayana numbers \operatorname(n, k), n \in \mathbb^+, 1 \le k \le n form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathematic ...
triangle.
Definition
A
partition of a set
In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.
Every equivalence relation on a set defines a partition of this set, and every parti ...
''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
In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. In ...
like the vertices of a regular ''n''-gon. No generality is lost by taking this set to be ''S'' = . 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 is noncrossing.
Equivalently, if we label the vertices of a regular ''n''-gon with the numbers 1 through ''n'', the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
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'' is 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 , the set of all noncrossing partitions is a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an ornam ...
when
partially ordered
In mathematics, especially order theory, a partially ordered set (also poset) 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 r ...
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 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.
This theory was in ...
theory that is played by the lattice of ''all'' partitions in defining joint cumulants in classical
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
. To be more precise, let
be a
non-commutative probability space
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
(See
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.
This theory was in ...
for terminology.),
a
non-commutative random variable
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
with free cumulants
. 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
The Wigner semicircle distribution, named after the physicist Eugene Wigner, is the probability distribution on minus;''R'', ''R''whose probability density function ''f'' is a scaled semicircle (i.e., a semi-ellipse) centered at (0, 0):
:f(x)=\sq ...
.
References
*Germain Kreweras, "Sur les partitions non croisées d'un cycle", ''
Discrete Mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
'', volume 1, number 4, pages 333–350, 1972.
*
Rodica Simion
Rodica Eugenia Simion (January 18, 1955 – January 7, 2000) was a Romanian-American mathematician. She was the Columbian School Professor of Mathematics at George Washington University. Her research concerned combinatorics: she was a pioneer in t ...
, "Noncrossing partitions", ''Discrete Mathematics'', volume 217, numbers 1–3, pages 367–409, April 2000.
Roland Speicher, "Free probability and noncrossing partitions" Séminaire Lotharingien de Combinatoire', B39c (1997), 38 pages, 1997
Families of sets
Enumerative combinatorics