Partition of a set

A partition of a set X is a set P of nonempty subsets of X such that every element x in X is in exactly one of these subsets. The elements of P are sometimes called the blocks of the partition.

Table of contents

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

Examples

The set {1, 2, 3} has the following partitions

• { {1}, {2}, {3} },
• { {1, 2}, {3} },
• { {1, 3}, {2} },
• { {1}, {2, 3} } and
• { {1, 2, 3} }.

Note that

• { {}, {1,3}, {2} } is not a partition because it contains an empty subset.
• { {1,2}, {2, 3} } is not a partition because the element 2 is contained in more than one subset.
• { {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3. It is a partition of {1, 2}.

Definition

Suppose S is a set. P, a set of subsets of S, is a partition if:

1. The union of the elements of P is equal to S
2. The intersection of any two elements of P is empty
3. No element of P is empty

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 an 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 in particular a 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, also denoted by

is the number of partitions of a set of size n into k blocks. The second notation above was introduced by Donald Knuth.

The number of partitions of a set of size n corresponding to the partition

of the integer n, is the Faà di Bruno coefficient