In mathematics, a partition of a set X is a division of X into non-overlapping "parts" or "blocks" or "cells" that cover all of X. More formally, these "cells" are both collectively exhaustive and mutually exclusive with respect to the set being partitioned.
Contents |
A partition of a set X is a set of nonempty subsets of X such that every element x in X is in exactly one of these subsets.
Equivalently, a set P of nonempty sets is a partition of X if
In mathematical notation, these two conditions can be written as
The elements of P are sometimes called the blocks or parts of the partition.[1]
If an equivalence relation is given on the set X, then the set of all equivalence classes forms a partition of X. Conversely, if a partition P is given on X, we can define an equivalence relation on X by writing x ~ y if there exists a member of P which contains both x and y. The notions of "equivalence relation" and "partition" are thus essentially equivalent.[2]
Given two partitions π and ρ of a given set X, we say that π is finer than ρ, or, equivalently, that ρ is coarser than π, if π splits the set X into smaller blocks than ρ does, i.e. if every element of π is a subset of some element of ρ. In that case, one writes π ≤ ρ.
The relation of "being-finer-than" is a partial order on the set of all partitions of the set X, and indeed even a complete lattice. In case n = 4, the partial order of the set of all 15 partitions is depicted in this Hasse diagram:
The lattice of noncrossing partitions of a finite set has recently taken on importance because of its role in free probability theory. These form a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree.
The Bell number Bn, named in honor of Eric Temple Bell, is the number of different partitions of a set with n elements. The first several Bell numbers are B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203.
The exponential generating function for Bell numbers is
Bell numbers satisfy the recursion
The Stirling number of the second kind S(n, k) is the number of partitions of a set of size n into k blocks.
The number of partitions of a set of size n corresponding to the integer partition
of n is the Faà di Bruno coefficient
The number of noncrossing partitions of a set of size n is the nth Catalan number, given by