Encyclopedia > Partition (mathematics)

  Article Content

Partition (mathematics)

A partition of a set X is a set P of nonempty subsets of X such that every element x in X is in exactly one of these subsets. The elements of P are sometimes called the blocks of the partition.

Table of contents

Examples:

The set {1, 2, 3} has the following partitions

  • { {1}, {2}, {3} },
  • { {1, 2}, {3} },
  • { {1, 3}, {2} },
  • { {1}, {2, 3} } and
  • { {1, 2, 3} }.
Note that
  • { {}, {1,3}, {2} } is not a partition because it contains an empty subset.
  • { {1,2}, {2, 3} } is not a partition because the element 2 is contained in more than one subset.
  • { {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3. It is a partition of {1, 2}.

Partitions and Equivalence Relations

If an equivalence relation is given on the set X, then the set of all equivalence classes forms a partition of X. Conversely, if a partition P is given on X, we can define an equivalence relation on X by writing x ~ y iff there exists a member of P which contains both x and y. The notions of "equivalence relation" and "partition" are thus essentially equivalent.

Partial ordering of partitions: the "lattice of partitions"

The set of all partitions of a set is a partially ordered set; one may say that one partition is "finer" than another if it splits the set into smaller blocks. This partially ordered set is a lattice.

The Number of Partitions

The Bell number Bn (named in honor of Eric Temple Bell) is the number of different partitions of a set with n elements. The first several Bell numbers are B0=1, B1=1, B2=2, B3=5, B4=15, B5=52, B6=203.


See also Integer partition



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
List of rare diseases starting with A

... microcephaly[?] Anonychia onychodystrophy brachydactyly type B[?] Anonychia onychodystrophy[?] Anophthalia pulmonary hypoplasia[?] Anophthalmia cleft lip palate ...

 
 
 
This page was created in 25.4 ms