Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Partition of a set
Main Page | See live article | Alphabetical index

Partition of a set


A partition of U into 6 blocks:
a Venn diagram representation.
In mathematics, a partition of a set X is a division of X into non-overlapping "parts" or "blocks" that cover all of X.

Table of contents
1 Definition
2 Examples
3 Partitions and equivalence relations
4 Partial ordering of the lattice of partitions
5 Noncrossing partitions
6 The number of partitions

Definition

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 subsets of X, is a partition of X if

  1. No element of P is empty.
  2. The union of the elements of P is equal to X. (We say the elements of P cover X.)
  3. The intersection of any two elements of P is empty. (We say the elements of P are pairwise disjoint.)

The elements of P are sometimes called the blocks of the partition.

Examples

Partitions and equivalence relations

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 iff there exists a member of P which contains both x and y. The notions of "equivalence relation" and "partition" are thus essentially equivalent.

Partial ordering of the lattice of partitions

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:

Noncrossing partitions

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 number of partitions

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 Stirling number S(n, k) of the second kind 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 (which see) of a set of size n is the nth Catalan number, given by