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
242

... - 4th century Decades: 190s 200s 210s 220s 230s - 240s - 250s 260s 270s 280s 290s Years: 237 238 239 240 241 - 242 - 243 244 245 246 247 Events Patriarch ...

 
 
 
This page was created in 36.8 ms