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


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
Reformed churches

... in their official definitions of doctrine, is no longer necessarily typical of these churches. Table of contents 1 Continental Reformed churches 2 Reformed ...

This page was created in 38 ms