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 a set of n elements is the nth Catalan number. 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. 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 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 . 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.
Like the set of all partitions of the set { 1, ..., n }, the set of all noncrossing partitions is a lattice when partially ordered by saying that a finer partition is "less than" a coarser partition. 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. 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 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. Indeed, every interval within this lattice is self-dual.
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. To be more precise, let be a non-commutative probability space (See free probability for terminology.), a non-commutative random variable 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.
In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one talks about the product in category theory, which formalizes these notions.
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number a is equal to itself (reflexive). If a = b, then b = a (symmetric). If a = b and b = c, then a = c (transitive).
In mathematics, a set B of vectors in a vector space V is called a basis if every element of V may be written in a unique way as a finite linear combination of elements of B. The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to B. The elements of a basis are called basis vectors.
In probability theory and statistics, the Gumbel distribution is used to model the distribution of the maximum of a number of samples of various distributions.
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.
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
In probability theory and statistics, the cumulantsκn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. Any two probability distributions whose moments are identical will have identical cumulants as well, and vice versa.
In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.
Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives. It is named after Francesco Faà di Bruno, although he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French mathematician Louis François Antoine Arbogast had stated the formula in a calculus textbook, which is considered to be the first published reference on the subject.
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.
In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for obtaining a sequence of observations which are approximated from a specified multivariate probability distribution, when direct sampling is difficult. This sequence can be used to approximate the joint distribution ; to approximate the marginal distribution of one of the variables, or some subset of the variables ; or to compute an integral. Typically, some of the variables correspond to observations whose values are known, and hence do not need to be sampled.
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 initiated by Dan Voiculescu around 1986 in order to attack the free group factors isomorphism problem, an important unsolved problem in the theory of operator algebras. Given a free group on some number of generators, we can consider the von Neumann algebra generated by the group algebra, which is a type II1 factor. The isomorphism problem asks whether these are isomorphic for different numbers of generators. It is not even known if any two free group factors are isomorphic. This is similar to Tarski's free group problem, which asks whether two different non-abelian finitely generated free groups have the same elementary theory.
In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.
The Wigner semicircle distribution, named after the physicist Eugene Wigner, is the probability distribution on [−R, R] whose probability density function f is a scaled semicircle centered at :
In probability theory and mathematical statistics, the law of total cumulance is a generalization to cumulants of the law of total probability, the law of total expectation, and the law of total variance. It has applications in the analysis of time series. It was introduced by David Brillinger.
In set theory, a prewellordering on a set is a preorder on that is strongly connected and well-founded in the sense that the induced relation defined by is a well-founded relation.
In mathematics, a π-system on a set is a collection of certain subsets of such that
In mathematics, the disintegration theorem is a result in measure theory and probability theory. It rigorously defines the idea of a non-trivial "restriction" of a measure to a measure zero subset of the measure space in question. It is related to the existence of conditional probability measures. In a sense, "disintegration" is the opposite process to the construction of a product measure.
In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.
This is a glossary of algebraic geometry.
