Movatterモバイル変換

Partition of a set

From Wikipedia, the free encyclopedia

Mathematical ways to group elements of a set

This article is about grouping elements of a set. For partitioning an integer, seeInteger partition. For the partition calculus of sets, seeInfinitary combinatorics. For the problem of partitioning a multiset of integers so that each part has the same sum, seePartition problem.

A set of stamps partitioned into bundles: No stamp is in two bundles, no bundle is empty, and every stamp is in a bundle.

The52 partitions of a set with 5 elements. A colored region indicates a subset of X that forms a member of the enclosing partition. Uncolored dots indicate single-element subsets. The first shown partition contains five single-element subsets; the last partition contains one subset having five elements.

The traditional Japanese symbols for the 54 chapters of theTale of Genji are based on the 52 ways of partitioning five elements (the two red symbols represent the same partition, and the green symbol is added for reaching 54).^[1]

Inmathematics, apartition of a set is a grouping of its elements intonon-empty subsets, in such a way that every element is included in exactly one subset.

Everyequivalence relation on aset defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called asetoid, typically intype theory andproof theory.

Definition and notation

[edit]

A partition of a setX is a set of non-empty subsets ofX such that every elementx inX is in exactly one of these subsets^[2] (i.e., the subsets are nonempty mutuallydisjoint sets).

Equivalently, afamily of setsP is a partition ofX if and only if all of the following conditions hold:^[3]

The familyP does not contain theempty set (that is $\emptyset \notin P$ ).
Theunion of the sets inP is equal toX (that is $\textstyle \bigcup _{A\in P}A=X$ ). The sets inP are said toexhaust orcoverX. See alsocollectively exhaustive events andcover (topology).
Theintersection of any two distinct sets inP is empty (that is $(\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset$ ). The elements ofP are said to bepairwise disjoint or mutually exclusive. See alsomutual exclusivity.

The sets in $P {\displaystyle P}$ are called theblocks,parts, orcells, of the partition.^[4] If $a\in X$ then we represent the cell containing $a {\displaystyle a}$ by $[a]$ . That is to say, $[a]$ is notation for the cell in $P {\displaystyle P}$ which contains $a {\displaystyle a}$ .

Every partition $P {\displaystyle P}$ may be identified with an equivalence relation on $X {\displaystyle X}$ , namely the relation $\sim _{\!P}$ such that for any $a,b\in X$ we have $a\sim _{\!P}b$ if and only if $a\in [b]$ (equivalently, if and only if $b\in [a]$ ). The notation $\sim _{\!P}$ evokes the idea that the equivalence relation may be constructed from the partition. Conversely every equivalence relation may be identified with a partition. This is why it is sometimes said informally that "an equivalence relation is the same as a partition". IfP is the partition identified with a given equivalence relation $\sim$ , then some authors write $P=X/{\sim }$ . This notation is suggestive of the idea that the partition is the setX divided into cells. The notation also evokes the idea that, from the equivalence relation one may construct the partition.

Examples

[edit]

The empty set $\emptyset$ has exactly one partition, namely $\emptyset$ . (Note: this is the partition, not a member of the partition.)
For any non-empty setX,P = {X } is a partition ofX, called thetrivial partition.
- Particularly, everysingleton set {x} has exactly one partition, namely { {x} }.
For any non-emptyproper subsetA of a setU, the setA together with itscomplement form a partition ofU, namely, {A,U ∖A }.
The set {1, 2, 3} has these five partitions (one partition per item):
- { {1}, {2}, {3} }, sometimes written 1 | 2 | 3.
- { {1, 2}, {3} }, or 1 2 | 3.
- { {1, 3}, {2} }, or 1 3 | 2.
- { {1}, {2, 3} }, or 1 | 2 3.
- { {1, 2, 3} }, or 1 2 3.
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 theempty 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

[edit]

For anyequivalence relation on a setX, the set of itsequivalence classes is a partition ofX. Conversely, from any partitionP ofX, we can define an equivalence relation onX by settingx ~y precisely whenx andy are in the same part inP. Thus the notions of equivalence relation and partition are essentially equivalent.^[5]

Theaxiom of choice guarantees for any partition of a setX the existence of a subset ofX containing exactly one element from each part of the partition. This implies that given an equivalence relation on a set one can select acanonical representative element from every equivalence class.

Refinement of partitions

[edit]

Partitions of a 4-element set ordered by refinement

A partitionα of a setX is arefinement of a partitionρ ofX—and we say thatα isfiner thanρ and thatρ iscoarser 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 "finer-than" relation on the set of partitions ofX is apartial order (so the notation "≤" is appropriate). Each set of elements has aleast upper bound (their "join") and agreatest lower bound (their "meet"), so that it forms alattice, and more specifically (for partitions of a finite set) it is ageometric andsupersolvable lattice.^[6]^[7] Thepartition lattice of a 4-element set has 15 elements and is depicted in theHasse diagram on the left.

The meet and join of partitions α and ρ are defined as follows. Themeet $\alpha \wedge \rho$ is the partition whose blocks are the intersections of a block ofα and a block ofρ, except for the empty set. In other words, a block of $\alpha \wedge \rho$ is the intersection of a block ofα and a block ofρ that are not disjoint from each other. To define thejoin $\alpha \vee \rho$ , form a relation on the blocksA ofα and the blocksB ofρ byA ~B ifA andB are not disjoint. Then $\alpha \vee \rho$ is the partition in which each blockC is the union of a family of blocks connected by this relation.

Based on the equivalence between geometric lattices andmatroids, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of theatoms of the lattice, namely, the partitions with $n-2$ singleton sets and one two-element set. These atomic partitions correspond one-for-one with the edges of acomplete graph. Thematroid closure of a set of atomic partitions is the finest common coarsening of them all; in graph-theoretic terms, it is the partition of thevertices of the complete graph into theconnected components of the subgraph formed by the given set of edges. In this way, the lattice of partitions corresponds to the lattice of flats of thegraphic matroid of the complete graph.

Another example illustrates refinement of partitions from the perspective of equivalence relations. IfD is the set of cards in a standard 52-card deck, thesame-color-as relation onD – which can be denoted ~_C – has two equivalence classes: the sets {red cards} and {black cards}. The 2-part partition corresponding to ~_C has a refinement that yields thesame-suit-as relation ~_S, which has the four equivalence classes {spades}, {diamonds}, {hearts}, and {clubs}.

Noncrossing partitions

[edit]

A partition of the setN = {1, 2, ...,n} with corresponding equivalence relation ~ isnoncrossing if it has the following property: If four elementsa,b,c andd ofN havinga <b <c <d satisfya ~c andb ~d, thena ~b ~c ~d. The name comes from the following equivalent definition: Imagine the elements 1, 2, ...,n ofN drawn as then vertices of a regularn-gon (in counterclockwise order). A partition can then be visualized by drawing each block as a polygon (whose vertices are the elements of the block). The partition is then noncrossing if and only if these polygons do not intersect.

The lattice of noncrossing partitions of a finite set forms a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree.

The noncrossing partition lattice has taken on importance because of its role infree probability theory.

Counting partitions

[edit]

The total number of partitions of ann-element set is theBell numberB_n. The first several Bell numbers areB₀ = 1,B₁ = 1,B₂ = 2,B₃ = 5,B₄ = 15,B₅ = 52, andB₆ = 203 (sequenceA000110 in theOEIS). Bell numbers satisfy therecursion

B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}

and have theexponential generating function

\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.

The Bell numbers may also be computed using theBell trianglein which the first value in each row is copied from the end of the previous row, and subsequent values are computed by adding two numbers, the number to the left and the number to the above left of the 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 largestsingleton.

The number of partitions of ann-element set into exactlyk (non-empty) parts is theStirling number of the second kindS(n,k).

The number of noncrossing partitions of ann-element set is theCatalan number

C_{n}={1 \over n+1}{2n \choose n}.

Notes

[edit]

^Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.),Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37
^Halmos, Paul (1960).Naive Set Theory R. Springer. p. 28.ISBN 9780387900926.{{cite book}}:ISBN / Date incompatibility (help)
^Lucas, John F. (1990).Introduction to Abstract Mathematics. Rowman & Littlefield. p. 187.ISBN 9780912675732.
^Brualdi 2004, pp. 44–45.
^Schechter 1997, p. 54.
^Birkhoff, Garrett (1995),Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, p. 95,ISBN 9780821810255.
^*Stern, Manfred (1999),Semimodular Lattices. Theory and Applications, Encyclopedia of Mathematics and its Applications, vol. 73, Cambridge University Press,doi:10.1017/CBO9780511665578,ISBN 0-521-46105-7

References

[edit]

Brualdi, Richard A. (2004).Introductory Combinatorics (4th ed.). Pearson Prentice Hall.ISBN 0-13-100119-1.
Schechter, Eric (1997).Handbook of Analysis and Its Foundations. Academic Press.ISBN 0-12-622760-8.