Editing Partition of a set

{{Short description|Mathematical ways to group elements of a set}}
{{about|grouping elements of a set|partitioning an integer|Integer partition|the partition calculus of sets|Infinitary combinatorics|the problem of partitioning a multiset of integers so that each part has the same sum|Partition problem}}
[[File:Indiabundleware.jpg|thumb|A set of stamps partitioned into bundles: No stamp is in two bundles, no bundle is empty, and every stamp is in a bundle.]]{{Use American English|date = March 2019}}
[[File:Set partitions 5; circles.svg|thumb|The [[Bell number|52]] 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.]]
[[File:Genji chapter symbols groupings of 5 elements.svg|thumb|The traditional Japanese symbols for the 54 chapters of the ''[[Tale 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).<ref>{{citation|contribution=Two thousand years of combinatorics|first=Donald E.|last=Knuth|author-link=Donald Knuth|pages=7–37|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins}}</ref>]]
In [[mathematics]], a '''partition of a set''' is a grouping of its elements into [[Empty set|non-empty]] [[subset]]s, in such a way that every element is included in exactly one subset.

Every [[equivalence relation]] on a [[Set (mathematics)|set]] 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 a [[setoid]], typically in [[type theory]] and [[proof theory]].

== Definition and notation ==
A partition of a set ''X'' is a set of non-empty subsets of ''X'' such that every element ''x'' in ''X'' is in exactly one of these subsets<ref>{{Cite book|last=Halmos|first=Paul|title=Naive Set Theory R.|publisher=Springer|year=1960|isbn=9780387900926|page=28|url=https://books.google.com/books?id=x6cZBQ9qtgoC&pg=PA28}}</ref> (i.e., the subsets are nonempty mutually [[disjoint sets]]).

Equivalently, a [[family of sets]] ''P'' is a partition of ''X'' if and only if all of the following conditions hold:<ref>{{cite book|last=Lucas|first=John F.|title=Introduction to Abstract Mathematics|publisher=Rowman & Littlefield|year=1990|isbn=9780912675732|page=187|url=https://books.google.com/books?id=jklsb5JUgoQC&pg=PA187}}</ref>
*The family ''P'' does not contain the [[empty set]] (that is <math>\emptyset \notin P</math>).
*The [[union (set theory)|union]] of the sets in ''P'' is equal to ''X'' (that is <math>\textstyle\bigcup_{A\in P} A = X</math>). The sets in ''P'' are said to '''exhaust''' or '''cover''' ''X''.  See also [[collectively exhaustive events]] and [[cover (topology)]].
* The [[intersection (set theory)|intersection]] of any two distinct sets in ''P'' is empty (that is <math>(\forall A,B \in P)\; A\neq B \implies A \cap B = \emptyset</math>). The elements of ''P'' are said to be [[pairwise disjoint]] or mutually exclusive. See also [[mutual exclusivity]].

The sets in <math>P</math> are called the ''blocks'', ''parts'', or ''cells'', of the partition.{{sfn|Brualdi|2004|pp=44–45}}  If <math>a\in X</math> then we represent the cell containing <math>a</math> by <math>[a]</math>.  That is to say, <math>[a]</math> is notation for the cell in <math>P</math> which contains <math>a</math>.  

Every partition <math>P</math> may be identified with an equivalence relation on <math>X</math>, namely the relation <math>\sim_{\!P}</math> such that for any <math>a,b\in X</math> we have <math>a\sim_{\!P} b</math> if and only if <math>a\in [b]</math> (equivalently, if and only if <math>b\in [a]</math>).  The notation <math>\sim_{\!P}</math> 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".  If ''P'' is the partition identified with a given equivalence relation <math>\sim</math>, then some authors write <math>P = X/{\sim}</math>.  This notation is suggestive of the idea that the partition is the set ''X'' divided into cells.  The notation also evokes the idea that, from the equivalence relation one may construct the partition.

The '''rank''' of <math>P</math> is <math>|X|-|P|</math>, if <math>X</math> is [[Finite set|finite]].

== Examples ==
*The empty set <math>\emptyset</math> has exactly one partition, namely <math>\emptyset</math>. (Note: this is the partition, not a member of the partition.)
*For any non-empty set ''X'', ''P'' = {{mset| ''X'' }} is a partition of ''X'', called the '''trivial partition'''.
**Particularly, every [[singleton set]] {''x''} has exactly one partition, namely {{mset| {{mset|''x''}} }}.
*For any non-empty [[proper subset]] ''A'' of a set ''U'', the set ''A'' together with its [[complement (set theory)|complement]] form a partition of ''U'', namely, {{mset| ''A'', ''U'' &setminus; ''A'' }}.
*The set {{mset|1, 2, 3}} has these five partitions (one partition per item):
** {{mset| {1}, {2}, {3} }}, sometimes written 1 | 2 | 3.
** {{mset| {1, 2}, {3} }}, or 1 2 | 3.
** {{mset| {1, 3}, {2} }}, or 1 3 | 2.
** {{mset| {1}, {2, 3} }}, or 1 | 2 3.
** {{mset| {1, 2, 3} }}, or 123 (in contexts where there will be no confusion with the number).
*The following are not partitions of {{mset|1, 2, 3}}:
** {{mset| {}, {1, 3}, {2} }} is not a partition (of any set) because one of its elements is the [[empty set]].
** {{mset| {1, 2}, {2, 3} }} is not a partition (of any set) because the element 2 is contained in more than one block.
** {{mset| {1}, {2} }} is not a partition of {{mset|1, 2, 3}} because none of its blocks contains 3; however, it is a partition of {{mset|1, 2}}.

== Partitions and equivalence relations ==
For any [[equivalence relation]] on a set ''X'', the set of its [[equivalence class]]es is a partition of ''X''. Conversely, from any partition ''P'' of ''X'', we can define an equivalence relation on ''X'' by setting {{nowrap|''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.{{sfn|Schechter|1997|p=54}}

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 [[representative (mathematics)|canonical representative element]] from every equivalence class.

== Refinement of partitions ==
[[File:Set partitions 4; Hasse; circles.svg|thumb|left|300px|Partitions of a 4-element set ordered by refinement]]
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 "finer-than" relation on the set of partitions of ''X'' is a [[partially ordered set|partial order]] (so the notation "≤" is appropriate). Each set of elements has a [[least upper bound]] (their "join") and a [[greatest lower bound]] (their "meet"), so that it forms a [[lattice (order)|lattice]], and more specifically (for partitions of a finite set) it is a [[geometric lattice|geometric]] and [[supersolvable lattice|supersolvable]] lattice.<ref>{{citation|title=Lattice Theory|volume=25|series=Colloquium Publications|publisher=American Mathematical Society|first=Garrett|last=Birkhoff|author-link=Garrett Birkhoff|edition=3rd|year=1995|isbn=9780821810255|page=95|url=https://books.google.com/books?id=0Y8d-MdtVwkC&pg=PA95}}.</ref><ref>*{{citation | last=Stern | first=Manfred | title=Semimodular Lattices. Theory and Applications | publisher=Cambridge University Press | year=1999 | volume=73 | series=Encyclopedia of Mathematics and its Applications | doi=10.1017/CBO9780511665578 | isbn=0-521-46105-7}}</ref> The ''partition lattice'' of a 4-element set has 15 elements and is depicted in the [[Hasse diagram]] on the left.

The meet and join of partitions α and ρ are defined as follows.  The '''meet''' <math>\alpha \wedge \rho</math> 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 <math>\alpha \wedge \rho</math> is the intersection of a block of ''α'' and a block of ''ρ'' that are not disjoint from each other.  To define the '''join''' <math>\alpha \vee \rho</math>, form a relation on the blocks ''A'' of ''α'' and the blocks ''B'' of ''ρ'' by ''A'' ~ ''B'' if ''A'' and ''B'' are not disjoint. Then <math>\alpha \vee \rho</math> is the partition in which each block ''C'' is the union of a family of blocks connected by this relation.

Based on the equivalence between geometric lattices and [[matroid]]s, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of the [[Atom (order theory)|atoms]] of the lattice, namely, the partitions with <math>n-2</math> singleton sets and one two-element set. These atomic partitions correspond one-for-one with the edges of a [[complete graph]]. The [[Matroid#Closure operators|matroid closure]] of a set of atomic partitions is the finest common coarsening of them all; in graph-theoretic terms, it is the partition of the [[Vertex (graph theory)|vertices]] of the complete graph into the [[Connected component (graph theory)|connected 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 the [[graphic matroid]] of the complete graph.

Another example illustrates refinement of partitions from the perspective of equivalence relations. If ''D'' is the set of cards in a standard 52-card deck, the ''same-color-as'' relation on ''D'' – which can be denoted ~<sub>C</sub> – has two equivalence classes: the sets {red cards} and {black cards}.  The 2-part partition corresponding to ~<sub>C</sub> has a refinement that yields the ''same-suit-as'' relation ~<sub>S</sub>, 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 partition|noncrossing]]''' if it has the following property: If four elements ''a'', ''b'', ''c'' and ''d'' of ''N'' having ''a'' < ''b'' < ''c'' < ''d'' satisfy ''a'' ~ ''c'' and ''b'' ~ ''d'', then ''a'' ~ ''b'' ~ ''c'' ~ ''d''. The name comes from the following equivalent definition: Imagine the elements 1, 2, ..., ''n'' of ''N'' drawn as the ''n'' vertices of a regular ''n''-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 in [[free probability]] theory.

== Counting partitions ==
The total number of partitions of an ''n''-element set is the [[Bell numbers|Bell number]] ''B<sub>n</sub>''. The first several Bell numbers are ''B''<sub>0</sub> = 1,
''B''<sub>1</sub> = 1, ''B''<sub>2</sub> = 2, ''B''<sub>3</sub> = 5, ''B''<sub>4</sub> = 15, ''B''<sub>5</sub> = 52, and ''B''<sub>6</sub> = 203 {{OEIS|A000110}}. Bell numbers satisfy the [[recursion]]

: <math>B_{n+1}=\sum_{k=0}^n {n\choose k} B_k</math>

and have the [[generating function|exponential generating function]]

:<math>\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}.</math>

[[Image:BellNumberAnimated.gif|right|thumb|Construction of the [[Bell triangle]]]]
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 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 largest [[singleton (mathematics)|singleton]].

The number of partitions of an ''n''-element set into exactly ''k'' (non-empty) parts is the [[Stirling number of the second kind]] ''S''(''n'', ''k'').

The number of noncrossing partitions of an ''n''-element set is the [[Catalan number]] 
:<math>C_n={1 \over n+1}{2n \choose n}.</math>

==See also==
* [[Exact cover]]
* [[Block design]]
* [[Cluster analysis]]
* [[List of partition topics]]
* [[Lamination (topology)]]
* [[MECE principle]]
* [[Partial equivalence relation]]
* [[Partition algebra]]
* [[Partition refinement]]
* [[Point-finite collection]]
* [[v:Rhyme schemes by set partition|Rhyme schemes by set partition]]
* [[Weak ordering]] (ordered set partition)

==Notes==
{{Reflist}}

==References==
*{{cite book |last= Brualdi |first= Richard A. |title= Introductory Combinatorics |edition= 4th |year= 2004 |publisher= Pearson Prentice Hall |isbn= 0-13-100119-1}}
*{{cite book |last= Schechter |first= Eric |title= Handbook of Analysis and Its Foundations |year= 1997 |publisher= Academic Press |isbn= 0-12-622760-8}}

{{Authority control}}

[[Category:Basic concepts in set theory]]
[[Category:Combinatorics]]
[[Category:Families of sets]]