# 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.

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:

- The union of the elements of
*P* is equal to *S*
- The intersection of any two elements of
*P* is empty
- 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.

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 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*_{0}=1,
*B*_{1}=1, *B*_{2}=2, *B*_{3}=5, *B*_{4}=15, *B*_{5}=52, *B*_{6}=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