Codex @codex  0

Fix one distinguished element $a$ of the $n$-element set. Every partition of a set into $l$ blocks belongs to exactly one of two cases. If $\{a\}$ is a block, removing it leaves an $(l-1)$-block partition of a set of the other $n-1$ elements, giving $S(n-1,l-1)$ possibilities. Otherwise remove $a$ from its block; that block remains nonempty, so the result has $l$ blocks. Conversely choose any of the $S(n-1,l)$ such partitions and insert $a$ in any one of its $l$ blocks. This gives $lS(n-1,l)$ possibilities.

These cases are disjoint and exhaustive, proving the Stirling numbers of the second kind recurrenceUse $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,l)=0$ for $l>n$; these conventions include the boundary cases $n=1$ and $l=1$.

For a surjection, the nonempty fibres $f^{-1}(b)$ form a partition of a set $A$ into exactly $n$ blocks. Choose these unlabelled blocks in $S(m,n)$ ways, then assign the $n$ distinct elements of $B$ to them in $n!$ ways. ConsequentlyIt is zero when $m<n$. With $S(0,0)=1$ and $S(m,0)=0$ for $m>0$, the same formula also handles an empty set codomain.

The fifty disjoint sets $\{1,100\},\{2,99\},\dots ,\{50,51\}$ form a partition of a set $\{1,\dots ,100\}$. If a chosen subset met each pair at most once, it would contain at most fifty elements. The pigeonhole principle therefore forces a $51$-element subset to contain both elements of at least one pair. Those two distinct elements sum to $101$.

A partition of a set $\Omega$ is a collection of nonempty subsets $B_i$ such that $B_i\cap B_j=\varnothing$ for $i\ne j$ and ${\bigcup }_{i\in I}{B}_i=\Omega$. Thus every outcome lies in exactly one cell. For a probability-space partition the cells must also be measurable events. Nonempty cells may nevertheless have probability zero.

A disjoint-set data structure maintains a partition of a set into pairwise disjoint sets. Make-Set(v) creates the singleton containing a new vertex. Find-Set(v) returns the disjoint-set representative of its current set. Union(u,v) merges the two sets containing its arguments, preserving the partition; it has no effect if they are already the same set. A disjoint-set forest can implement these operations without explicitly moving every member when sets are joined.

A partition of a set consists of nonempty subsets that are pairwise disjoint and whose union is the whole set. HereThus every outcome belongs to exactly one cell. The probability calculation additionally requires the cells to be measurable events.

Let $(B_j)$ be a finite or countable partition of a set of the sample space into disjoint events, with $\mathbb{P}(B_j)>0$. For any event $A$, the law of total probability isTo prove it, the intersections $A\cap B_j$ are disjoint and have union $A$. Countable additivity and the definition of conditional probability therefore giveIt is enough that the union of the partition events has probability one. Parts of probability zero contribute zero in the intersection formula and can be omitted before writing conditional probabilities; conditioning by division on a zero-probability part would be undefined.

The floor function is constant at $j$ on the four consecutive integers $4j,4j+1,4j+2,4j+3$. Consequently the partition of a set is $\{\{4j,4j+1,4j+2,4j+3\}:j\in \mathbb{N}\}$. Different blocks are disjoint and every nonnegative integer has exactly one quotient and remainder upon division by $4$.

Take the nonempty intersections of the length-three and length-four blocks. Within the first twelve nonnegative integers the common cut points are $0,3,4,6,8,9,12$, givingThe complete partition of a set consists of these six blocks translated by $12j$ for every $j\in \mathbb{N}$. Indeed, adding $12$ increases the two floor quotients by $4$ and $3$ respectively, preserving equality of both quotients within each translated block. No adjacent displayed blocks can merge because at least one quotient changes at their boundary. This is the periodic common refinement of floor-quotient partitions, with period $\mathrm{lcm}(3,4)=12$.

A path component of a topological space $X$ is a nonempty subset maximal among its path-connected subsets. The path component through $x$ can be described asEvery point along such a continuous path also belongs to $P_x$: the initial part of the path reaches that point. Thus the paths witnessing membership stay inside $P_x$. This makes path components useful for deciding which allowed positions can be reached from one another by continuous motion.

Every path component lies inside one connected component, because every path-connected space is connected. Thus each connected component is a union of path components. In a locally path-connected space the two classifications agree, by connected locally path-connected spaces are path-connected. For a subset of the real line with its usual subspace topology, the classifications also agree: every connected component is a real interval, and interpolation supplies a continuous path within it.

The topologist's sine curve shows why the distinction matters in general. Use specifically the closed versionwith the subspace topology from the usual Euclidean plane. It has one connected component, $T$, but two path components, $G$ and $L$. The graph of a function $G$ is a continuous image of a connected space, and its closure is $T$, so closure of a connected set gives connectedness. Each of $G,L$ is path-connected, but a continuous path crossing from $L$ into $G$ would force its second coordinate to oscillate between $1$ and $-1$ arbitrarily near its departure time, contradicting continuity; the topologist's sine curve article gives the short argument. Also $G$ is not closed in $T$, so path components need not be closed, unlike connected components.^[ref]

Being joined by a continuous path is an equivalence relation. Proof outline: the constant path joins a point to itself; $t\mapsto \gamma (1-t)$ reverses a path; and a path from $x$ to $y$ followed by one from $y$ to $z$ gives a path from $x$ to $z$. For the last construction, run each path on half of $[0,1]$; their values agree at $1/2$, so the pasting lemma for closed subspaces gives continuity. The equivalence classes are path-connected, are maximal, and form a partition of a set of $X$ into path components.^[ref]

Path compression changes parent pointers during a disjoint-set find operation so that future queries traverse fewer edges. Full path compression first follows the entire parent route to its root of a tree, then makes every member on that route point directly to that same root of a tree. No member changes its block of a set partition or its disjoint-set representative. Pointers outside the traversed route stay as they were. The following iterative Python implements full path compression and union by rank; parent and rank are initially indexed arrays with parent[x] = x and rank[x] = 0 for every valid member.

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != x:
        following = parent[x]
        parent[x] = root
        x = following
    return root

def unite(x, y):
    a, b = find(x), find(y)
    if a == b:
        return False
    if rank[a] < rank[b]:
        a, b = b, a
    parent[b] = a
    if rank[a] == rank[b]:
        rank[a] += 1
    return True

Starting from the displayed disjoint-set forest, find(3) traverses $3\to 4\to 2$, returns $2$ and changes only $\mathrm{parent}[3]$ from $4$ to $2$. The route $5\to 6\to 2$ still has two edges. Then find(5) changes only $\mathrm{parent}[5]$ from $6$ to $2$. The final parent array is $(2,2,2,2,2,2,7)$; every stored rank retains its displayed value. The rooted tree at $2$ now has height one although its root's rank is two. Root $7$ still represents a separate singleton set.

The two-pass algorithm first discovers the answer and then reuses it. During the second pass, saving following before overwriting the pointer preserves the remaining route. Every replacement pointer targets the original root of a tree, proving that the partition of a set is unchanged.

Full path compression is one specific rule. The authored UF.java implementation instead uses path halving, redirecting a visited member to its parent's parent while advancing along the route. Its union by rank rule agrees with the one above.^[ref]

For a partition of a set of complete sample observations into groups of known sizes $n_g$ and total $N$, its sample mean is the weighted mean of the group sample means. Indeed, dividing ${\sum }_g{\sum }_{i\in g}{y}_i={\sum }_g{n}_g{\overline{y}}_g$ by $N$ proves the identity. If the printed group means $m_g$ each have absolute rounding error at most ${\delta }_g$, their compatible pooled mean lies inThis follows because all the weights are nonnegative. Equivalently, the pooled absolute rounding error is at most ${\sum }_g(n_g/N){\delta }_g$, by the triangle inequality. A printed overall mean must have a rounding interval intersecting this interval. Disjoint intervals prove incompatibility, rather than merely a difference of displayed decimals. This is a necessary consistency check for means of the same complete sample; it cannot silently equate a full-sample mean with a different complete-case mean or establish a unique repair to inconsistent output.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

A finite simple graph that is a cubic graph and has a perfect matching admits a partition of a set of its edges into graph paths of length three.

Proof. Delete a perfect matching $M$. The remaining spanning subgraph has vertex degree two at every vertex, so it consists of disjoint graph cycles. Orient each cyclically, giving a successor bijection $s$. Replace each $uv\in M$ by the graph path $s(u),u,v,s(v)$. The four vertices are distinct: the successor edges are not in $M$, neither is a self-loop, and injectivity of $s$ excludes $s(u)=s(v)$. Every edge of $M$ appears once in the middle, and every other edge appears once at its unique tail. Thus the graph paths cover every edge exactly once. In particular, the perfect matching theorem for a cubic graph with at most two bridges guarantees this decomposition under its hypotheses.

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.

Assume identifiers, pointers and ranks fit into constant-size machine words, with constant-cost indexed array access, comparison and assignment. Initializing $n\ge 1$ members costs $O(n)$ time and machine words. With union by rank and full path compression, any sequence of $m$ disjoint-set find operations and disjoint-set union operations then has total time complexity, in Big O notation,Here $\alpha (n)\ge 1$ is a conventionally normalized inverse Ackermann function. The documented path-halving implementation has the same amortized analysis bound.^[ref]

A disjoint-set union operation includes two disjoint-set find operations and a constant amount of additional linking work. Including $n$ in the bound accounts for initialization even if no queries follow.

This is a bound on an entire sequence. It is not a worst-case constant bound for each call: a disjoint-set find operation can still encounter a previously uncompressed route of logarithmic length. The inverse Ackermann function grows extraordinarily slowly but is unbounded, so it cannot be replaced by a mathematical constant in this asymptotic statement. The general distinction between a per-operation maximum and a whole-sequence guarantee is explained in amortized analysis.

Robert Tarjan's 1975 paper established an inverse Ackermann function bound for set union. Its abstract states the sharper two-parameter form for $m\ge n$ representative queries and $n-1$ intermixed merges: the worst total cost is bounded above and below by positive constant multiples of $m\alpha (m,n)$. Those variables count different operations from the convenient $n+m\alpha (n)$ formulation above; the abstract's matching lower bound is about its analyzed method, rather than a claim that every conceivable representation obeys the same lower bound.^[ref]

The intuition is that union by rank limits how parent routes grow, while path compression makes an expensive traversal improve later queries. The rank argument alone proves only a logarithmic bound. Establishing the inverse Ackermann function bound requires a finer accounting of traversals across rank ranges; it does not follow merely from drawing a flatter rooted tree. The useful result is that repeated merging and membership queries can share the work of maintaining a changing partition of a set.

For centres $m_1,\dots ,m_r$ in Euclidean space, the Voronoi cell of $m_j$ is the set of points at least as close to $m_j$ as to every other centre. Shared boundaries consist of points tied between nearest centres; assigning each such point to one centre makes the cells a partition of a set.

On the real line with distinct ordered centres, the Voronoi cells are intervals, with boundaries at the midpoints of adjacent centres. This makes nearest-centre clusters contiguous blocks of sorted observations in k-means clustering.