Bell Number - Partitions of A Set

Partitions of A Set

In general, B_n is the number of partitions of a set of size n. A partition of a set S is defined as a set of nonempty, pairwise disjoint subsets of S whose union is S. For example, B₃ = 5 because the 3-element set {a, b, c} can be partitioned in 5 distinct ways:

{ {a}, {b}, {c} }

{ {a}, {b, c} }

{ {b}, {a, c} }

{ {c}, {a, b} }

{ {a, b, c} }.

B₀ is 1 because there is exactly one partition of the empty set. Every member of the empty set is a nonempty set (that is vacuously true), and their union is the empty set. Therefore, the empty set is the only partition of itself.

Note that, as suggested by the set notation above, we consider neither the order of the partitions nor the order of elements within each partition. This means the following partitionings are all considered identical:

{ {b}, {a, c} }

{ {a, c}, {b} }

{ {b}, {c, a} }

{ {c, a}, {b} }.