Partition of a set
In mathematics, a partition of a set S is a collection of non-empty subsets of S that are pairwise disjoint and whose union equals S.[1] This means every element of S belongs to exactly one subset in the collection, ensuring a complete and non-overlapping division of the set.[2] Partitions are intimately connected to equivalence relations: every equivalence relation on a set induces a unique partition where the subsets are the equivalence classes, and conversely, every partition defines an equivalence relation by declaring elements equivalent if they lie in the same subset.[3] This correspondence underpins much of their utility in abstract algebra and set theory.[4] The enumeration of set partitions is a central topic in combinatorics. The total number of partitions of a finite set with n elements is given by the n-th Bell number B_n, which counts all possible ways to divide the set into non-empty subsets regardless of the number of parts.[5] More specifically, the number of partitions into exactly k non-empty subsets is the Stirling number of the second kind S(n, k), and the Bell numbers satisfy B_n = \sum_{k=0}^n S(n, k).[6] These numbers arise in diverse counting problems, such as distributing distinct objects into indistinguishable bins.[7] Set partitions find applications across mathematics and related fields, including probabilistic models and in combinatorial optimization.[8] They also play a role in the study of symmetric groups and representation theory, where partitions label irreducible representations.[9]Basic Concepts
Definition
A partition of a set S is a collection of non-empty subsets of S that are pairwise disjoint and whose union equals S. This means the subsets divide S into distinct, non-overlapping parts that together cover every element exactly once. Formally, if P = \{ A_i \mid i \in I \} is a partition of S, where I is an indexing set, then A_i \cap A_j = \emptyset for all distinct i, j \in I, \bigcup_{i \in I} A_i = S, and each A_i \neq \emptyset. The non-emptiness condition ensures that no subset is trivial or redundant in covering S, while the disjointness prevents any element from belonging to multiple subsets, and the union requirement guarantees exhaustiveness, so no element of S is omitted. The requirement for non-empty subsets arises because including the empty set would not affect the union but would violate the principle of a proper division into meaningful parts; similarly, exhaustiveness ensures the partition fully accounts for S without gaps.[10] This structure underpins the correspondence between partitions and equivalence relations, where each part corresponds to an equivalence class.Notation and Terminology
In standard mathematical notation, the collection of all partitions of a finite set S is often denoted by \Pi(S) or P(S).[11] For a partition P of S, the cardinality |P| represents the number of blocks in P, while the type of P is defined as the multiset of the sizes of its blocks, providing a way to classify partitions up to the specific elements involved.[11] The fundamental components of a partition are its blocks, which are the non-empty, pairwise disjoint subsets whose union is exactly S. A block containing a single element is termed a singleton. Partitions are partially ordered by the refinement relation: a partition P is finer than another partition Q (or equivalently, Q is coarser than P) if every block of P is a subset of some block of Q; this ordering forms the partition lattice.[11] Given a partition P of S and a subset A \subseteq S, the restriction of P to A, denoted P \upharpoonright A or P \restriction A, is the partition of A induced by taking the non-empty intersections of the blocks of P with A.[11] It is important to distinguish set partitions from integer partitions in combinatorics: while integer partitions represent ways of writing a positive integer n as a sum of positive integers (disregarding order), set partitions divide a set into unlabeled, unordered blocks without regard to the elements' labels or the blocks' arrangement, focusing instead on the grouping structure.[12]Examples
Simple Examples
To illustrate the concept of a set partition, consider the smallest non-trivial case: a set with two elements, such as S = \{a, b\}. There are exactly two possible partitions of this set. The first is the trivial partition consisting of a single block containing all elements: \{\{a, b\}\}. The second is the discrete partition into singletons: \{\{a\}, \{b\}\}.[12] For a three-element set, such as S = \{1, 2, 3\}, there are five distinct partitions, reflecting the Bell number B_3 = 5, which counts the total number of partitions of a set with three elements. These are:- The single-block partition: \{\{1, 2, 3\}\}
- The partitions into one doubleton and one singleton: \{\{1, 2\}, \{3\}\}, \{\{1, 3\}, \{2\}\}, and \{\{2, 3\}, \{1\}\}
- The discrete partition into three singletons: \{\{1\}, \{2\}, \{3\}\}
Similarly, the full discrete partition appears as three separate singleton blocks:Block 1: {1, 2} Block 2: {3}Block 1: {1, 2} Block 2: {3}
Such representations emphasize the disjointness and coverage of the original set without overlap.[12] It is important to note that partitions are unordered collections of subsets; thus, the order of blocks or elements within blocks does not affect equality. For example, \{\{1, 2\}, \{3\}\} is identical to \{\{3\}, \{1, 2\}\}, and \{1, 2\} is the same block as \{2, 1\}. This unordered nature distinguishes partitions from ordered tuples or sequences.[13]Block 1: {1} Block 2: {2} Block 3: {3}Block 1: {1} Block 2: {2} Block 3: {3}
Partitions of Larger Sets
To illustrate the diversity of partitions for larger sets, consider the set S = \{a, b, c, d\}. One partition consists of all singletons: \{\{a\}, \{b\}, \{c\}, \{d\}\}, where each element forms its own block. Another type features one doubleton and two singletons, such as \{\{a, b\}, \{c\}, \{d\}\}, emphasizing how elements can be paired while leaving others isolated. A further variation includes two doubletons, like \{\{a, b\}, \{c, d\}\}, pairing all elements into equal-sized blocks.[14] Partitions of such sets exhibit patterns based on block sizes, distinguishing balanced structures—where blocks are as equal in size as possible, such as the two doubletons example above—from unbalanced ones, like a tripleton with a singleton \{\{a, b, c\}, \{d\}\}, which creates disparity in block cardinalities. These patterns highlight the flexibility in grouping elements while maintaining disjointness and coverage.[15] For intuition, partitions resemble dividing a class of four students into study groups by skill levels: all individuals working alone (singletons), two pairing up while others remain solo (one doubleton and singletons), or two pairs forming balanced teams (two doubletons), ensuring every student is assigned without overlap. The following table enumerates all partitions of \{a, b, c, d\}, grouped by block size compositions (in nonincreasing order), using set notation for clarity:| Block Sizes | Partitions |
|---|---|
| 4 | \{\{a, b, c, d\}\} |
| 3+1 | \{\{a, b, c\}, \{d\}\} \{\{a, b, d\}, \{c\}\} \{\{a, c, d\}, \{b\}\} \{\{b, c, d\}, \{a\}\} |
| 2+2 | \{\{a, b\}, \{c, d\}\} \{\{a, c\}, \{b, d\}\} \{\{a, d\}, \{b, c\}\} |
| 2+1+1 | \{\{a, b\}, \{c\}, \{d\}\} \{\{a, c\}, \{b\}, \{d\}\} \{\{a, d\}, \{b\}, \{c\}\} \{\{b, c\}, \{a\}, \{d\}\} \{\{b, d\}, \{a\}, \{c\}\} \{\{c, d\}, \{a\}, \{b\}\} |
| 1+1+1+1 | \{\{a\}, \{b\}, \{c\}, \{d\}\} |
Equivalence Relations and Partitions
The Correspondence
A fundamental connection exists between equivalence relations and partitions of a set. Given a nonempty set S and an equivalence relation \sim on S, the equivalence classes = \{ y \in S \mid y \sim x \} for each x \in S form the blocks of a partition of S. These classes are nonempty by reflexivity, disjoint by the properties of equivalence (if two classes overlapped, transitivity would merge them), and their union covers S by totality of the relation.[16] Conversely, for any partition P of S, consisting of nonempty disjoint subsets whose union is S, one can define an equivalence relation \sim_P on S by declaring x \sim_P y if and only if x and y belong to the same block in P. This relation is reflexive (each element is in its own block), symmetric (blocks are undirected), and transitive (elements in the same block stay within it).[16] These constructions establish a bijection between the set of all equivalence relations on S and the set of all partitions of S. The map sending an equivalence relation to its partition of equivalence classes is injective, as distinct relations yield distinct class collections (different groupings imply different relations), and surjective, as every partition arises from its induced relation. Similarly, the reverse map is bijective by construction, confirming the one-to-one correspondence. This duality underscores that equivalence relations and partitions are theoretically interchangeable representations of the same clustering structure on S.[16] The recognition of this bijection as a core principle in set theory developed in the early 20th century, building on Georg Cantor's foundational work on set equivalence in the 1890s, with explicit terminology and formalization appearing in modern texts from the 1930s onward, such as those standardizing "equivalence relation" around that period.[17]Constructing Partitions from Relations
Given an equivalence relation \sim on a set S, the partition induced by \sim consists of the equivalence classes = \{ y \in S \mid y \sim x \} for each x \in S. To construct this partition explicitly, begin with the set S and select an arbitrary element x \in S; form the equivalence class by identifying all elements in $S$ that are related to $x$ via $\sim$ (accounting for reflexivity, symmetry, and transitivity to ensure completeness). Remove and all its elements from consideration, then repeat the process with a remaining element until S is exhausted; the resulting collection of disjoint equivalence classes forms the partition. For instance, consider S = \{1, 2, 3\} with the relation specified by $1 \sim 2 and $2 \sim 3; applying the transitive closure yields $1 \sim 3, so the single equivalence class {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} = {{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} = {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} = \{1, 2, 3\}, producing the partition \{\{1, 2, 3\}\}. In the reverse direction, starting from the partition P = \{\{1, 2\}, \{3\}\} on S, define the relation \sim_P by x \sim_P y if and only if x and y belong to the same block of P. This relation is reflexive (each x is in its own block), symmetric (blocks are unordered), and transitive (elements in the same block remain so under chaining), confirming \sim_P is an equivalence relation whose classes recover P.[18] This construction establishes a bijection between equivalence relations on S and partitions of S, as detailed in the correspondence between the two structures. Furthermore, the lattice of all partitions of S (ordered by refinement, where finer partitions are below coarser ones) is isomorphic to the lattice of all equivalence relations on S (or congruences), with the meet and join operations corresponding via the blocks and transitive closures, respectively.[19]Operations on Partitions
Refinement
In the theory of set partitions, a partition Q of a set S is a refinement of another partition P of S, written Q \preceq P, if every block of Q is contained as a subset in some block of P. This means that Q can be obtained from P by further subdividing the blocks of P, resulting in a finer grouping of the elements of S. The refinement relation defines a partial order on the set of all partitions of S, turning it into a partially ordered set (poset), often called the partition lattice \Pi_{|S|}.[11] The partial order induced by refinement is reflexive, as every partition refines itself, since each of its blocks is contained in itself. It is also transitive: if Q \preceq P and P \preceq R, then every block of Q is contained in a block of P, which in turn is contained in a block of R, so every block of Q is contained in a block of R. Additionally, the order is antisymmetric, ensuring that if Q \preceq P and P \preceq Q, then Q = P. These properties make the refinement poset a lattice structure with well-defined meets and joins corresponding to common coarsenings and refinements, respectively.[11] In the refinement poset, the minimal element is the discrete partition, which consists of |S| singleton blocks \{\{x\} \mid x \in S\}, as no finer partition exists. The maximal element is the indiscrete partition \{\{S\}\}, the coarsest possible grouping with a single block containing all elements. For a concrete illustration, consider S = \{1,2,3,4\}, with P = \{\{1,2\}, \{3,4\}\} and Q = \{\{1\}, \{2\}, \{3,4\}\}. Here, Q \preceq P holds because \{1\} \subseteq \{1,2\}, \{2\} \subseteq \{1,2\}, and \{3,4\} = \{3,4\}, but the reverse does not, since \{1,2\} is not contained in any single block of Q. This example demonstrates how refinement captures the idea of splitting blocks to achieve greater detail in partitioning.[11]Coarsening
In the theory of set partitions, a partition P of a set S is a coarsening of another partition Q of S (denoted P \geq Q) if every block of P is a union of one or more blocks of Q.[20] This operation merges blocks of Q to form larger blocks in P, reducing the number of blocks while preserving the underlying set S.[20] Coarsening is the dual operation to refinement in the partially ordered set (poset) of all partitions of S, ordered by refinement where Q \leq P if Q refines P (every block of Q is contained in some block of P). This poset is a lattice, with the meet of two partitions being their coarsest common refinement (the partition formed by taking all nonempty intersections of blocks from the two partitions) and the join being their finest common coarsening (the partition generated by the transitive closure of the union of the corresponding equivalence relations). For example, the partition \{\{1,2,3,4\}\} is a coarsening of \{\{1,2\}, \{3,4\}\} because the single block \{1,2,3,4\} is the union of the two blocks in the finer partition.[20] To obtain a coarsening of a partition Q, select compatible groups of blocks from Q (subsets of blocks whose elements can be merged without violating the partition structure) and replace each group with their union, ensuring the resulting collection remains a partition of S.[20]Special Partitions
Noncrossing Partitions
A noncrossing partition of a linearly ordered set S = \{1 < 2 < \dots < n\} is a partition where no two blocks cross, meaning there do not exist elements a < b < c < d such that either a and c are in one block and b and d are in another block, or a and d are in one block and b and c are in another block.[21] This condition ensures that the blocks respect the linear order without interleaving.[22] Geometrically, noncrossing partitions can be visualized by placing the elements $1 to n consecutively around a circle and connecting elements within the same block by chords; the partition is noncrossing if these chords do not intersect except possibly at the vertices.[21] This representation highlights their combinatorial significance, as the non-intersecting chords correspond to planar embeddings, linking noncrossing partitions to other Catalan structures like polygon triangulations.[22] For n=4, the partition \{\{1,2\}, \{3,4\}\} is noncrossing, as the blocks are contiguous and non-interleaving in the order.[21] In contrast, \{\{1,3\}, \{2,4\}\} is crossing, since $1 < 2 < 3 < 4 with $1 \sim 3 and $2 \sim 4, violating the noncrossing condition.[21] The number of noncrossing partitions of an n-element set is given by the n-th Catalan number C_n = \frac{1}{n+1} \binom{2n}{n}.[22] This enumeration satisfies the recurrence relation C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, with C_0 = 1.[22]Interval Partitions
In the context of set partitions, an interval partition of the linearly ordered set S = \{1 < 2 < \dots < n\} is a partition whose blocks are nonempty intervals of consecutive elements, meaning each block takes the form \{k, k+1, \dots, m\} for integers $1 \leq k \leq m \leq n.[23] This restricts the blocks to contiguous segments, preserving the natural order of the elements.[24] For example, with n=5, the collection \{\{1,2,3\}, \{4\}, \{5\}\} forms an interval partition, as each block consists of consecutive integers.[24] Interval partitions correspond bijectively to the integer compositions of n, where the sizes of the blocks match the parts of the composition; for instance, the above example corresponds to the composition (3,1,1).[23] Consequently, the total number of interval partitions of is $2^{n-1}, obtained by choosing whether to place a separator in each of the n-1 gaps between the elements.[24] All interval partitions are noncrossing, since their disjoint consecutive blocks cannot interleave in a way that violates the noncrossing condition (no four elements i < j < k < l with i \sim l and j \sim k in different blocks).[25] However, the reverse does not hold, as noncrossing partitions may include blocks that are non-consecutive yet non-interleaving.[24] The collection of all interval partitions forms a sublattice of the full partition lattice under the refinement order, where one partition refines another if every block of the former is contained in some block of the latter.[23] Interval partitions find applications in areas requiring segmentation of ordered data, such as time series analysis, where partitioning a sequence into consecutive segments identifies regimes or changes in behavior.[26] For instance, optimal algorithms for dividing data points on an interval into subintervals often rely on dynamic programming tailored to interval structures, enabling efficient computation for tasks like signal processing or forecasting.[26]Enumeration
Stirling Numbers of the Second Kind
The Stirling numbers of the second kind, denoted S(n,k), count the number of ways to partition a set of n elements into exactly k nonempty unlabeled subsets.[27][28] These numbers satisfy the recurrence relation S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1) for $1 \leq k \leq n, with boundary conditions S(n,0) = 0 for n > 0, S(0,k) = \delta_{0k} (where \delta is the Kronecker delta), S(n,1) = 1, and S(n,n) = 1.[27][28] The values of S(n,k) for small n and k are given in the following table:| n \setminus k | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 1 | 1 | |||
| 3 | 1 | 3 | 1 | ||
| 4 | 1 | 7 | 6 | 1 | |
| 5 | 1 | 15 | 25 | 10 | 1 |
Bell Numbers
The Bell number B_n denotes the total number of partitions of a set with n elements and is defined as B_n = \sum_{k=0}^n S(n,k), where S(n,k) counts the partitions into exactly k nonempty subsets (Stirling numbers of the second kind).[30] This summation aggregates all possible block sizes, providing the overall enumeration of set partitions.[31] The sequence of Bell numbers begins 1, 1, 2, 5, 15, 52, ... and grows rapidly. The values up to n=10 are presented in the following table:| n | B_n |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 15 |
| 5 | 52 |
| 6 | 203 |
| 7 | 877 |
| 8 | 4140 |
| 9 | 21147 |
| 10 | 115975 |