Motivation
Suppose five distinct records must be divided into three nonempty groups. If the groups are named training, validation and test, changing their names changes the assignment. If they are simply three clusters, only their memberships matter. A third problem distributes five identical tokens among three named boxes. The same words “five objects, three groups” hide three different collections to count.
The distinction is especially useful when a program stores a cluster label for every record. Relabeling all the clusters changes that representation while preserving the underlying grouping. We will count the groupings directly, then determine exactly how many representations each has. The resulting recurrence is also a small example of dynamic programming in which a mathematical decomposition determines the update order.
Definitions and boundary cases
Definition 1.4.1
(Set partitions and blocks)
For an integer , let , with . A set partition of is a collection of nonempty, pairwise disjoint subsets whose union is . These subsets are its blocks. Blocks have no names or prescribed order. For instance, and are the same partition.
Definition 1.4.2
(Stirling numbers of the second kind)
Write for the number of partitions of into exactly blocks. These are called Stirling numbers of the second kind. The elements are distinct even when the blocks have equal sizes. We use
The empty collection is the unique partition of the empty set. There is no partition of a nonempty set into no blocks. For convenience set also for negative ; no set with a negative size is being introduced.
Definition 1.4.3
(Surjections)
A surjection uses every one of its output labels. Let count such functions. When , there is one surjection for and none for . For , the nonempty fibers are the groups carrying labels . Forgetting those labels gives a set partition.
Removing the last element gives a recurrence
Theorem 1.4.4
(The Stirling recurrence)
For and ,
Together with the boundary values, this determines every uniquely.
Proof
(Classifying partitions by the block of the last element)
Look at the block containing the distinguished element . If it is the singleton , deleting it leaves a partition of into blocks. Conversely, adjoining that singleton reconstructs exactly one original partition. This case contributes .
Otherwise, remove from its block but retain the other elements. The remaining partition has nonempty blocks, together with the choice of the block from which was removed. Conversely, choose a partition of into blocks, choose one of those blocks, and insert . There are exactly choices for each partition, even though the blocks are unlabeled: its different member subsets are distinguishable choices. This contributes .
The cases are disjoint because the block of cannot be both a singleton and nonsingleton. They exhaust all partitions, so addition proves the recurrence. Each right-hand entry has a smaller first index, and the boundary row is fixed; induction therefore proves uniqueness.
Proof X-ray
Why a recurrence needs reversible cases
“Insert the next element somewhere” is not yet a counting proof. We identified two types of insertion and showed how to recover both the smaller partition and the insertion choice from the result. Recoverability rules out duplicate descriptions inside either case; the singleton distinction rules out overlap between cases.
The first rows, with entries outside the displayed range understood to be zero, are
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 3 | 1 | 0 | 0 |
| 4 | 0 | 1 | 7 | 6 | 1 | 0 |
| 5 | 0 | 1 | 15 | 25 | 10 | 1 |
For example, . This equality tells us more than the number: seven partitions have as a block, and eighteen put into a larger block.
Labels connect partitions to functions
Theorem 1.4.5
(Surjections are partitions with labeled blocks)
For nonnegative integers ,
More generally, for ,
Here denotes the number of functions from the empty set to itself, not a limit of real powers.
Proof
(Labeled blocks and image sizes)
Given a partition with blocks, choose a bijection from its set of blocks to . There are such bijections. Send each element to the label of its block. The resulting function is surjective, and its fibers recover both the partition and the chosen labels. This is a bijection between labeled partitions and surjections, proving the first identity. For , both constructions are empty and still unique.
For the second identity, classify every function by its image size . Choose the image in ways, and then choose a surjection onto those labels in ways. Distinct image sets or partitions describe different functions. The cases are exhaustive because every function has one image. The formula includes empty domains and codomains using the preceding conventions.
Thus counts all assignments to named boxes, including unused boxes. The Stirling number counts unlabeled blocks that must all be nonempty. Converting between the two requires keeping track of which labels are used, rather than merely dividing by .
Concept lensAlgebraic
Stirling numbers as a change of basis
The identity holds for every integer , and vanishes automatically when . Two polynomials of degree at most that agree at infinitely many points are equal, so
For this reads . The numbers are the coordinates of in the basis of falling factorials.
Counting surjections by inclusion–exclusion
Theorem 1.4.6
(Exclude missing output labels)
For all nonnegative ,
The same empty-function convention applies. Dividing this integer by gives .
Proof
(Each function contributes one or zero)
For a subset , the functions avoiding every label in number . Sum this count with sign over all . To prove what the signed sum counts, fix one particular function and let be the set of labels it misses. Its total contribution is
The last cancellation follows by pairing subsets omitting one fixed element of with subsets containing it; their signs are opposite. Hence precisely the surjective functions contribute one. Grouping subsets by size gives the stated formula. When the domain is empty, the same contribution proof applies to its unique function, which misses every codomain label.
Worked example 1.4.7
(Five distinct records, three groups)
The recurrence gives unlabeled groupings. Giving the groups three specified names produces assignments. Inclusion–exclusion confirms
In contrast, five identical tokens in three named nonempty boxes give positive occupancy vectors. That number records only three sizes. It does not record which of five distinct records belongs in each group.
Counterexample mode
Dividing all assignments by a factorial can fail
For four elements and two labels, , but . The two constant functions use only one label and represent a one-block partition. Removing them gives . Division by is valid on the surjections because every two-block partition has exactly two labelings. It does not make assignments with empty boxes become two-block partitions.
More generally, for , a fixed -block partition represented with labels from has representations. This depends on , so forgetting labels on all functions does not have one common fiber size across different block counts.
Prescribed block sizes require two symmetry factors
Sometimes the group sizes are specified but the groups remain unlabeled. Let be the required number of blocks of size , with nonnegative integers satisfying
Theorem 1.4.8
(Partitions with a fixed size profile)
For such a profile the number of partitions is
For , the empty profile has count one, using empty products equal to one.
Proof
(Slots and symmetry factors)
Arrange the distinct elements in a line, and cut that line into slots: first slots of length one, then slots of length two, and so on. There are input lines. Forget both the order inside each slot and the order among slots of the same size. This leaves a partition of the required profile.
For a fixed resulting partition, its blocks of size can be assigned to the corresponding slots in ways. Their elements can be ordered within those slots in ways. These choices are independent over sizes, and recover exactly every line producing that partition. All fibers therefore have the common denominator size, proving the formula. Blocks of different sizes have already been assigned different kinds of slots, so dividing by another would remove legitimate distinctions a second time.
Worked example 1.4.9
(Seven partitions into two blocks)
For four distinct elements, a two-block partition has sizes or . The first profile contributes : choose the singleton. The second contributes : the two pairs have no order. Thus .
Using the same calculation, six distinct elements split into three unlabeled pairs in ways. Assigning three specified names to the pairs multiplies by , giving .
Worked example 1.4.10
(Classifying assignments by image size)
Assign four distinct records to three available labels, allowing unused labels. Image sizes one, two and three contribute respectively
Their sum is . The image-size-two term chooses which two labels are used as well as a grouping and its labels. Omitting the factor would count only assignments using one specified pair of labels.
An exact dynamic program
To compute a single , first return zero if . The boundary cases or can be answered directly. For and , the recurrence uses only the preceding row, so store integer cells.
def stirling(n, k):
if n < 0 or k < 0:
raise ValueError("n and k must be nonnegative integers")
if k > n:
return 0
if n == 0:
return 1 # Here k is necessarily zero.
if k == 0:
return 0
d = [0] * (k + 1)
d[0] = 1
for i in range(1, n + 1):
for j in range(min(i, k), 0, -1):
d[j] = j * d[j] + d[j - 1]
d[0] = 0
return d[k]
The function assumes its arguments are integers. At the start of row , the cells contain for . Processing in decreasing order means that both and still have their old values when read. The update writes the Stirling recurrence for . Entries with remain zero, and resetting establishes the nonempty-row boundary. Induction on proves correctness, including the first row, whose singleton comes from the initial .
There are integer additions and multiplications by an integer at most , and stored integer cells. These are arithmetic counts. To state a bit bound, observe that for : label a partition's blocks in increasing order of their least members to inject it into functions . Thus the stored counts and nonnegative update terms fit within
bits. Elementary addition and multiplication by give the sufficient upper bound bit operations and bits for the integer array. Loop indices and the given input have their separate storage costs. This deliberately simple bound does not assume unit-cost operations on arbitrarily large integers.
The running time depends on the numeric value of , not just its binary length. Indeed, for the exact answer already has binary digits. An exact-output algorithm cannot generally take time polynomial in alone.
Common mistakes and scope
Common mistake
(Treating blocks as labeled, or allowing empty blocks)
The elements are labeled; the blocks are not. Equal-size blocks are still different subsets, while changing their order creates no new partition. Empty blocks are excluded by definition. Allowing an unlimited number of empty blocks would not even give a well-defined block count without further conventions.
An equivalence relation on is uniquely determined by its classes, and every partition defines one by declaring elements related when they share a block. Therefore the total number of equivalence relations is , the Bell number. For four elements it is . This counts all equivalence relations, with no claim that a uniform random assignment of labels samples them uniformly.
Common mistake
(Reading exact counts as numerical or sampling results)
The signed formula, fixed-profile formula and dynamic program count the same objects by different decompositions. The proofs establish exact integers. They do not establish a numerically stable floating-point evaluation of a large alternating sum, or a uniform random partition sampler.
Practice
Quick check
(For , prove . Explain why the case must be handled separately.)
Solution · Answer
For , there are functions to two labels. Exactly two are constant, and every other function is surjective. Each two-block partition has labelings, so . For this correctly gives zero. At , there is only one empty function, rather than two distinct constant functions; there are no two-block partitions, so must be stated separately.
Quick check
(For , prove by describing the possible block sizes.)
Solution · Answer
Starting with one element in each of blocks accounts for elements. The one remaining element must enlarge exactly one block to size two. Thus a partition has one pair and all remaining blocks singletons. Choosing the pair gives partitions, and the pair is uniquely recoverable. For this gives the single one-block partition, as required.
Quick check
(How many partitions of six distinct elements have exactly two blocks of size two and two blocks of size one? How many assignments give those four blocks four specified distinct labels?)
Solution · Answer
The profile is , so the count is . Each partition has four different member subsets, even though sizes repeat; assigning the four specified labels bijectively to them has choices. The assignment count is therefore . Labels are not restricted to particular sizes in this second question.
Quick check
(Replace the inner loop by increasing from one through . Trace the row for and identify the first incorrect value. Explain which recurrence input has been overwritten.)
Solution · Answer
Before the third row the cells are . Increasing order writes , then , then . The last entry should be . Its term has been replaced by the new . Decreasing order reads the old before changing it, so the recurrence uses one consistent preceding row.
Quick check
(Evaluate , and directly. Check each against the signed formula, and explain why must represent one in that formula.)
Solution · Answer
There is one function from the empty set to itself, and its empty image equals its empty codomain, so . The empty function cannot cover three labels, so . A function from three elements into the empty set does not exist, so .
The signed sums are respectively , , and . In the middle sum, even the term with no allowed labels counts an empty function: every input condition is vacuous because there are no inputs. Setting would destroy that count and give an incorrect answer.