Table of contents |
2 Definition 3 Partitions and equivalence relations 4 Partial ordering of the lattice of partitions 5 The number of partitions |
The set {1, 2, 3} has the following partitions
Suppose S is a set. P, a set of subsets of S, is a partition if:
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 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, also denoted by
The number of partitions of a set of size n corresponding to the partition
Examples
Note that
Definition
Partitions and equivalence relations
Partial ordering of the lattice of partitions
The number of partitions
is the number of partitions of a set of size n into k blocks. The second notation above was introduced by Donald Knuth.
of the integer n, is the Faà di Bruno coefficient