Partition of a set

From Wikipedia, the free encyclopedia

In mathematics, a partition of a set X is a division of X into non-overlapping "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.

Contents 1 Definition 2 Examples 3 Partitions and equivalence relations 4 Refinement of partitions 5 Noncrossing partitions 6 Counting various partitions 7 See also 8 Notes 9 References

[edit] 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 written as

1. 
2. 

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

[edit] 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} }, sometimes denoted by 1/2/3.
  • { {1, 2}, {3} }, sometimes denoted by 12/3.
  • { {1, 3}, {2} }, sometimes denoted by 13/2.
  • { {1}, {2, 3} }, sometimes denoted by 1/23.
  • { {1, 2, 3} }, sometimes denoted by 123.
• Note that
  • { {}, {1,3}, {2} } is not a partition (because it contains the empty set).
  • { {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}.

[edit] 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]

[edit] 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, one writes π ≤ ρ.

This finer-than relation on the set of partitions of X is a partial order (so the notation "≤" is appropriate); indeed 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. Let D be the set of cards in a standard 52-card deck. The same-color-as relation on D, which we might denote ~_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}.

[edit] 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.

[edit] Counting various 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

[edit] See also

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

[edit] Notes

[edit] 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.