Partition of a set

A partition of a set into 6 parts: an Euler diagram representation

In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X. More formally, these "cells" are both collectively exhaustive and mutually exclusive with respect to the set being partitioned.

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 nonempty sets is a partition of X if

1. The union of the elements of P is equal to X. (The elements of P are said to cover X.)
2. The intersection of any two distinct elements of P is empty. (We say the elements of P are pairwise disjoint.)

In mathematical notation, these two conditions can be represented as

or

Where is the empty set. The elements of P are sometimes called the blocks or parts of the partition.^[1]

Examples

• Every singleton set {x} has exactly one partition, namely { {x} }.
• For any nonempty set X, P = {X} is a partition of X.
• For any non-empty proper subset A of a set U, this A together with its complement is a partition of U.
• The set { 1, 2, 3 } has these five partitions:
  • { {1}, {2}, {3} }, or 1/2/3.
  • { {1, 2}, {3} }, or 12/3.
  • { {1, 3}, {2} }, or 13/2.
  • { {1}, {2, 3} }, or 1/23.
  • { {1, 2, 3} }, or 123 (in contexts where there will be no confusion with the number).
• The following are not partitions of { 1, 2, 3 }:
  • { {}, {1,3}, {2} } is not a partition (because it contains the empty set, which is still registered as something).
  • { {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

For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent.^[2]

Refinement of partitions

Any partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that α ≤ ρ.

This finer-than relation on the set of partitions of X is a partial order (so the notation "≤" is appropriate); it is a complete lattice. For the simple example of X = {1, 2, 3, 4}, the partition lattice has 15 elements and is depicted in this Hasse diagram:

Another example illustrates the refining of partitions from the perspective of equivalence relations. If D is the set of cards in a standard 52-card deck, the same-color-as relation on D – which can be denoted ~_C – has two equivalence classes: the sets {red cards} and {black cards}. The 2-part partition corresponding to ~_C has a refinement that yields the same-suit-as relation ~_S, which has the four equivalence classes {spades}, {diamonds}, {hearts}, and {clubs}.

Noncrossing partitions

A partition of the set N = {1, 2, ..., n} with corresponding equivalence relation ~ is noncrossing provided that there are no distinct numbers a, b, c, and d in N with a < b < c < d for which a ~ c and b ~ d. The lattice of noncrossing partitions of a finite set has recently taken on importance because of its role in free probability theory. These form a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree.

Counting partitions

The total number of partitions of an n-element set is the Bell number B_n. The first several Bell numbers are B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, and B₆ = 203. Bell numbers satisfy the recursion

and have the exponential generating function

The number of partitions of an n-element set into exactly k parts is the Stirling number of the second kind S(n, k).

The number of noncrossing partitions of an n-element set is the Catalan number C_n, given by

See also

• Data clustering
• Equivalence relation
• Exponential formula
• Faà di Bruno formula
• List of partition topics
• Partial equivalence relation

Notes

References

• Brualdi, Richard A. (2004). Introductory Combinatorics (4th edition ed.). Pearson Prentice Hall. ISBN 0131001191. 
• Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0126227608.