A set of stamps partitioned into bundles: No stamp is in two bundles, and no bundle is empty.
The
52 partitions of a set with 5 elements
The traditional Japanese symbols for the chapters of the
Tale of Genji are based on the 52 ways of partitioning five elements.
In mathematics, a partition of a set is a grouping of the set's elements into nonempty subsets, in such a way that every element is included in one and only one of the subsets.
Contents

Definition 1

Examples 2

Partitions and equivalence relations 3

Refinement of partitions 4

Noncrossing partitions 5

Counting partitions 6

See also 7

Notes 8

References 9
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^{[1]} (i.e., X is a disjoint union of the subsets).
Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold:^{[2]}

P does not contain the empty set.

The union of the sets in P is equal to X. (The sets in P are said to cover X.)

The intersection of any two distinct sets in P is empty. (We say the elements of P are pairwise disjoint.)
In mathematical notation, these conditions can be represented as

\emptyset \notin P

\bigcup_{A\in P} A = X

if A,B \in P and A\neq B then A \cap B = \emptyset,
where \emptyset is the empty set.
The sets in P are called the blocks, parts or cells of the partition.^{[3]}
The rank of P is X − P, if X is finite.
Examples

Every singleton set {x} has exactly one partition, namely { {x} }.

For any nonempty set X, P = {X} is a partition of X, called the trivial partition.

For any nonempty proper subset A of a set U, the set A together with its complement form a partition of U, namely, {A, U−A}.

The set { 1, 2, 3 } has these five partitions:

{ {1}, {2}, {3} }, sometimes written 123.

{ {1, 2}, {3} }, or 123.

{ {1, 3}, {2} }, or 132.

{ {1}, {2, 3} }, or 123.

{ {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 (of any set) because one of its elements is the empty set.

{ {1, 2}, {2, 3} } is not a partition (of any set) because the element 2 is contained in more than one block.

{ {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.^{[4]}
The axiom of choice guarantees for any partition of a set X the existence of a subset of X containing exactly one element from each part of the partition. This implies that given an equivalence relation on a set one can select a canonical representative element from every equivalence class.
Refinement of partitions
A 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 finerthan relation on the set of partitions of X is a partial order (so the notation "≤" is appropriate). Each set of elements has a least upper bound and a greatest lower bound, so that it forms a lattice, and more specifically (for partitions of a finite set) it is a geometric lattice.^{[5]} The partition lattice of a 4element set has 15 elements and is depicted in the Hasse diagram on the left.
Based on the cryptomorphism between geometric lattices and matroids, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of the atoms of the lattice, the partitions with n2 singleton sets and one twoelement set. These atomic partitions correspond oneforone with the edges of a complete graph. The matroid closure of a set of atomic partitions is the finest common coarsening of them all; in graphtheoretic terms, it is the partition of the vertices of the complete graph into the connected components of the subgraph formed by the given set of edges. In this way, the lattice of partitions corresponds to the graphic matroid of the complete graph.
Another example illustrates the refining of partitions from the perspective of equivalence relations. If D is the set of cards in a standard 52card deck, the samecoloras relation on D – which can be denoted ~_{C} – has two equivalence classes: the sets {red cards} and {black cards}. The 2part partition corresponding to ~_{C} has a refinement that yields the samesuitas 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 for any two 'cells' C1 and C2, either all the elements in C1 are < than all the elements in C2 or they are all > than all the elements in C2. In other words: given distinct numbers a, b, c in N, with a < b < c, if a ~ c (they both are in a cell called C), it follows that also a ~ b and b ~ c, that is b is also in C. 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 partitions
The total number of partitions of an nelement set is the Bell number B_{n}. The first several Bell numbers are B_{0} = 1, B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15, B_{5} = 52, and B_{6} = 203 (sequence A000110 in OEIS). 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^z1}.
The Bell numbers may also be computed using the Bell triangle in which the first value in each row is copied from the end of the previous row, and subsequent values are computed by adding the two numbers to the left and above left of each position. The Bell numbers are repeated along both sides of this triangle. The numbers within the triangle count partitions in which a given element is the largest singleton.
The number of partitions of an nelement set into exactly k nonempty parts is the Stirling number of the second kind S(n, k).
The number of noncrossing partitions of an nelement set is the Catalan number C_{n}, given by

C_n={1 \over n+1}{2n \choose n}.
See also
Notes

^ Naive Set Theory (1960). Halmos, Paul R. Springer. p. 28.

^ Lucas, John F. (1990). Introduction to Abstract Mathematics. Rowman & Littlefield. p. 187.

^ Brualdi, pp. 44–45

^ Schechter, p. 54

^ .
References

Brualdi, Richard A. (2004). Introductory Combinatorics (4th ed.). Pearson Prentice Hall.

Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.