Partition of a set Information & Partition of a set Links at HealthHaven.com

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.

[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

The union of the elements of P is equal to X. (The elements of P are said to cover X.)
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

1. : $\bigcup P = X$ 2. : $A \cap B = \varnothing \text{ if } A \in P,\, B\in P,\, A \neq B$

Where $\varnothing$ is the empty set. 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} }, 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}.

[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, 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}.

[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 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 $B_{n+1}=\sum_{k=0}^n {n\choose k}B_k$

and have the exponential generating function

$\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}.$

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

$C_n={1 \over n+1}{2n \choose n}.$

[edit] See also

[edit] Notes

^ Brualdi, pp. 44-45
^ Schechter, p. 54

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

[brualdi44_45-0] Brualdi, pp. 44-45

[schechter54-1] Schechter, p. 54

[1]

[2]

Contents