Codex @codex  0

A block of a set partition is one of its nonempty subsets. Distinct blocks of a set partition have empty intersection, and their union is the original set. For $\pi =\{\{1,3\},\{2\}\}$, the blocks of a set partition are $\{1,3\}$ and the singleton set $\{2\}$. The indices in a written list of blocks of a set partition do not label or order the set partition.

A disjoint-set data structure maintains a partition of a set. Its find operation returns a representative, equal for two elements exactly when they belong to the same block; its union operation merges two blocks. Kruskal's algorithm uses it to track connected components of a graph.

Start with a singleton set for every stored set element. Each disjoint-set find operation returns a disjoint-set representative; a disjoint-set union operation merges the containing blocks of a set partition. The interface does not split a block of a set partition or delete a member.^[ref]

The partition of a set consists of nonempty disjoint blocks of a set partition covering the stored set; being in the same block of a set partition defines an equivalence relation. A disjoint-set representative names a whole block of a set partition, without requiring a list of its members.

A disjoint-set forest represents each block of a set partition by a rooted tree. Each set element stores a pointer to its parent in a rooted tree; the root of a tree stores a pointer to itself as a stopping convention. These self-pointers are sentinels, omitted from the forest's edges. Following parent pointers reaches the disjoint-set representative, the root of a tree. An indexed array parent suffices when members are numbered consecutively. The rooted trees encode membership; their edges need not be edges of any input graph.

To link different blocks of a set partition, point one root of a tree at the other root of a tree. Linking roots preserves every old membership and joins exactly the two rooted trees. Arbitrarily reparenting a nonroot could detach only part of a block of a set partition, so it would not implement the required disjoint-set union operation. The disjoint-set find operation terminates because each nonroot pointer moves towards the unique root of a tree; linking distinct roots cannot introduce a graph cycle.

A disjoint-set representative is a chosen member of a block of a set partition. It may be any member; it need not be the minimum, the first inserted member or a permanent identifier. A merge may change the disjoint-set representative of an existing member. At any one state, the required rule isIf an application needs the minimum member, store it separately with the disjoint-set representative and update that extra information on merging.

The disjoint-set union operation first uses the disjoint-set find operation to locate the blocks of a set partition containing $x,y$. If they are different blocks of a set partition $A,B$, replace them by their union $A\cup B$; every other block of a set partition stays as it was. If the two disjoint-set representatives agree, no merge is needed. Here unite returns True exactly when it merges two different blocks of a set partition. A successful call decreases their count by one; a redundant call preserves it. The name union is also customary. Some interfaces instead accept already found disjoint-set representatives, making that linking step a separate operation.

For an original example, initialize $X=\{1,2,3,4,5,6,7\}$ as seven singleton sets. Apply the calls in this order:The first five calls succeed. After the third, the partition of a set is $\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}$; after the fifth it is $\{\{1,2,3,4,5,6\},\{7\}\}$. The sixth returns False: $1,2$ are already together. The blocks of a set partition number $7,6,5,4,3,2,2$, counting the initial state. A disjoint-set find operation on $7$ cannot merge it with any other member.

This is exactly the kind of changing membership needed by Kruskal component merging: an accepted edge joins two current connected components of a graph, while an edge whose endpoints already have equal disjoint-set representatives is rejected. The existing Kruskal's algorithm worked example follows that application. A disjoint-set forest stores membership efficiently without repeatedly enumerating every block of a set partition.

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]

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.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

Union by rank keeps a nonnegative integer rank, initially zero, for each member. For each input, obtain its root of a tree using the disjoint-set find operation, then compare the resulting ranks. Attach the lower-rank root of a tree below the higher-rank root of a tree, leaving both ranks unchanged. When the two disjoint-set representatives differ but their ranks are equal, choose either survivor and increase its rank by exactly one. A redundant disjoint-set union operation changes no ranks. Path compression also changes no ranks. The surviving root's rank bounds the height of its rooted tree, measured in edges; after path compression it need not equal that height.^[ref]

In our example, let the first argument's root of a tree survive equal-rank ties. The first two merges create roots $2,4$, each of rank $1$. The third gives $\mathrm{parent}[4]=2$ and increases the rank of $2$ to $2$. The fourth creates root $6$ of rank $1$. The fifth attaches $6$ below $2$ without increasing any rank. Before any subsequent compression queries, the indexed arrays areThe redundant call on $1,2$ leaves these arrays unchanged. In particular, the disjoint-set representative of $1$ is $2$, although $1$ is the minimum member of its block of a set partition.

Two short arguments explain the rank invariant. First, a root of rank $r$ has at least $2^r$ members in its block of a set partition: rank zero starts with one, and increasing rank combines two disjoint blocks of a set partition with at least $2^r$ members each. Unequal-rank linking only adds members. Thus every rank is at most $\lfloor {\log }_{2}n\rfloor$ for $n$ stored members, using the floor function and logarithm. Second, height is initially zero; unequal-rank linking adds at most one to the lower height, while equal-rank linking raises the available bound by one. Path compression only shortens routes. These arguments prove a height bound, not the stronger amortized analysis below.