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

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

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 written as

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

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

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

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 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 $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}.$

Notes

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

References

Brualdi, Richard A. (2004). Introductory Combinatorics (4th edition ed.). Pearson Prentice Hall. ISBN 0131001191 [Amazon-US | Amazon-UK].
Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0126227608 [Amazon-US | Amazon-UK].

Open source encyclopedia content modification information:

This page was last modified on 9 June 2009 at 15:38.

Authorship and Review

Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.

Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Partition of a set", which is available in its original form here:

http://en.wikipedia.org/w/index.php?title=Partition_of_a_set

All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.

Partition of a set -- Please Click to Return to Front Page