Partition of a set

File:Set partition.png
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.

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

• Every singleton set {x} has exactly one partition, namely { {x} }.
• The empty set has exactly one partition, namely itself. (Axioms 1 and 3 are vacuously satisfied.)
• Forgetting momentarily about certain exotic cases, the set of all humans can be partitioned into two blocks: the males and the females.
• The set {1, 2, 3} has these five partitions.
  • { {1}, {2}, {3} }
  • { {1, 2}, {3} }
  • { {1, 3}, {2} }
  • { {1}, {2, 3} }
  • { {1, 2, 3} }
• Note that
  • { {}, {1,3}, {2} } is not a partition (of any set) because it contains the empty set.
  • { {1,2}, {2, 3} } is not a partition (of any set) because the element 2 is contained in more than one distinct subset.
  • { {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3; however, it is a partition of {1, 2}.

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 P and Q of a given set X, we say that P is finer than Q if it splits the set X into smaller blocks, i.e. if every element of P is a subset of some element of Q. In that case, one writes P ≤ Q.

With this relation of "being-finer-than", the set of all partitions of a set X is a partially ordered set and indeed even a complete lattice.

The number of partitions

The Bell number B_n, 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 B₀=1, B₁=1, B₂=2, B₃=5, B₄=15, B₅=52, B₆=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

$n=\underbrace {1+\cdots +1} _{m_{1}\ {\mbox{terms}}}+\underbrace {2+\cdots +2} _{m_{2}\ {\mbox{terms}}}+\underbrace {3+\cdots +3} _{m_{3}\ {\mbox{terms}}}+\cdots$

of n, is the Faà di Bruno coefficient

${n! \over m_{1}!m_{2}!m_{3}!\cdots 1!^{m_{1}}2!^{m_{2}}3!^{m_{3}}\cdots }.$