Motivation
Putting distinct objects into groups is not determined by the group sizes alone. One must also specify which labels occur together and whether the groups themselves have names. Permutation cycles introduce still another choice: a cyclic order inside each group. These distinctions lead to different counting sequences even when the same integers appear as parameters.
Stirling numbers organize two of these models. Bell numbers total all set partitions, and exponential generating functions express how labeled blocks assemble. The same arrays also appear in polynomial identities, where ordinary powers and falling factorials count functions in two different ways. We will derive those connections from the objects being counted rather than treating the formulas as unrelated tables.
Definitions
Definition 2.7.1
(Partitions and the two Stirling arrays)
A set partition of is an unordered collection of disjoint nonempty blocks whose union is . Let count partitions into blocks. Let count permutations of with exactly disjoint cycles, where cycles have cyclic order but the collection of cycles is unordered. Define .
Use , representing the empty partition or empty permutation. For positive , use . Set either Stirling number to zero for or . These conventions make boundary cases of the recurrences meaningful without inventing an empty block.
Definition 2.7.2
(Falling factorials and formal exponential series)
Set and for . Let for . For labeled counts , their exponential generating function is , interpreted formally over the real numbers here. Write as a formal series.
A formal identity means equality of coefficients, not a numerical convergence claim. Products use finite convolution at each degree. Composing a series with another series having zero constant coefficient is also well-defined coefficient by coefficient; this will justify the Bell generating function.
Theorem/Proposition
Theorem 2.7.3
(The two insertion recurrences)
For and ,
There are surjections from to a labeled -element target. For , inclusion–exclusion consequently gives
with the empty-domain counting convention when needed.
Theorem 2.7.4
(Bell recurrence and exponential generating functions)
For ,
For every , and then summing over all block counts,
These are formal-series identities, including the constant terms.
Theorem 2.7.5
(Two inverse polynomial bases)
For every nonnegative integer , as polynomial identities in ,
Thus the second-kind array and the signed first-kind array are inverse changes of basis. In particular, for ,
Proof sketch or proof idea
Proof
(Inserting the last label, and naming the fibers)
In a partition, label is either a singleton block or belongs to one of the other blocks. Removing a singleton leaves a partition into blocks; otherwise removing the label leaves blocks and records which one receives it again. These cases are disjoint and uniquely reversible, proving the recurrence for .
For permutation cycles, label is either its own cycle or is inserted immediately after one of the other labels in an existing cycle. Removing it reverses that insertion and preserves the number of cycles. The two cases prove the recurrence for . The insertion positions are labeled elements, not the number of cycles: each cycle offers as many positions as its length.
A surjection partitions its domain into nonempty fibers and assigns the distinct target labels to those blocks. Every partition has exactly such assignments, regardless of equal block sizes, because the blocks have different contents. Inclusion–exclusion counts surjections by excluding missed target labels; grouping by the number of available targets gives the displayed alternating formula.
Proof X-ray
Deletion must remember exactly the reconstruction choice
Both recurrences come from one move, deleting the largest label, and each is an equality only because the deletion is paired with exactly the information needed to undo it. In a set partition, a non-singleton label is reattached by naming one of the surviving blocks; blocks are distinguishable by their contents, so these choices give different partitions. In a cycle, the label is reattached by naming its predecessor, one of minus 1 labels, and each choice gives a different permutation with the same number of cycles. That is the whole source of the different factors and minus 1. The singleton case is where the zero conventions enter: it reduces the block or cycle count by one, and at equal to 0 or the corresponding terms vanish or equal one by convention rather than by a separate argument. The surjection formula uses the same fact that blocks are distinguishable, now to make every partition have exactly factorial labelings.
Proof
(The block of a distinguished label, and ordered blocks)
For the Bell recurrence, inspect the block containing a new distinguished label. Choose its companions from the other labels, then partition the remaining labels arbitrarily. The distinguished block and remaining partition reconstruct the original object uniquely. Summing over all companion counts proves the recurrence.
To prove the generating function for fixed , first order the nonempty blocks. If their sizes are , there are ways to distribute the labels into those ordered blocks. The coefficient of in sums precisely the reciprocal factorial weights over positive sizes totaling . Multiplication by therefore counts ordered block partitions; dividing by forgets the block order. For each fixed degree, only contributes, except the empty case. Summing the formal identities over gives , whose inner series has zero constant term.
Proof
(Counting functions by image, then inverting)
For the first polynomial identity, take a positive integer and count functions from to an -element target. Their domain fibers form a partition into some nonempty blocks. Assigning distinct target values to these blocks can be done in ways. Summing gives the identity for every positive integer , hence as polynomials because a nonzero polynomial has only finitely many roots.
For the second, multiplying by gives the coefficient recurrence
The signed cycle counts satisfy exactly this recurrence and the same initial values, so induction proves the coefficients agree. Finally substitute the second polynomial expansion into the first and compare the coefficient of . This gives the inverse-array formula. The falling factorials form a basis because they are monic polynomials of successive degrees: comparing highest degrees gives independence, and successive subtraction gives spanning.
Worked examples
Worked example 2.7.6
(Six labeled objects in three unnamed blocks)
First and . Therefore . Also , so . Naming the three boxes multiplies this by , giving onto assignments. Independently, inclusion–exclusion gives , verifying that the labels and nonemptiness were handled consistently.
Worked example 2.7.7
(Bell total versus block-size patterns)
The Bell recurrence gives , , , and . On four labels, the block-size patterns are , , , , and . Their respective numbers of set partitions are one, four, three, six and one, totaling fifteen. Counting the five size patterns alone would count integer partitions, not set partitions of labeled elements.
Worked example 2.7.8
(The same blocks carry additional cycle orders)
For permutations on four labels with two cycles, type contributes four choices of singleton times two cyclic orders on the remaining labels, giving eight. Type contributes three pairings, giving three. Thus , whereas . A block of size has cyclic orders: fix one label as the starting point and arrange the others. These internal orders explain the difference between the two Stirling kinds.
Concept lensAlgebraic
A whole cycle row as one product
The cycle recurrence says that each row is a product of linear factors:
since multiplying the row polynomial for by reproduces . For the product is , matching . Replacing by and multiplying by gives the falling factorial expansion with the signs .
Why unnamed blocks still have a uniform labeling count
A set partition is unordered, but its blocks are distinct sets. Two blocks of equal size are not identical: disjoint nonempty blocks contain different elements. Assigning box labels therefore gives the full factorial number of assignments even when several sizes coincide. The labeling map has a uniform fiber size, which is the precise reason division by a factorial is valid.
Integer block-size patterns deliberately forget more information. A pattern says how many blocks have each size but not which elements they contain. Different patterns have different numbers of realizations, as the four-label example shows. Dividing a total labeled count by one universal pattern factor cannot recover those different multiplicities without another argument.
The cycle model adds information rather than forgetting it. For a fixed set partition, independently choose a cyclic order inside each block. The product of the cyclic-order counts is the number of permutations with exactly those cycle supports. Summing those products over partitions yields the unsigned first-kind numbers. This explains their relationship without identifying the objects they count.
Reading exponential generating functions correctly
The factorial denominator in an exponential generating function records label distribution. Multiplying two such series combines objects on disjoint selected subsets of the labels, producing binomial coefficients in the resulting count. An ordinary generating function uses a different coefficient rule for the underlying counting interpretation. The same rational or exponential-looking algebra should not be transferred between the two models without checking its coefficients.
The term describes one nonempty labeled block: there is one block structure on each positive-size label set. Its constant term is removed because a partition has no empty blocks. The outer exponential permits an unordered collection of such blocks. This description is shorthand for the explicit ordered-block and factorial argument in the proof, not a replacement for it.
At degree zero there is one empty collection of blocks. Accordingly both the Bell generating function and the fixed-zero-block series have constant coefficient one. Omitting that case would break the recurrence at the first input and the formal exponential identity. No analytic convergence question is needed to determine these coefficients.
Concept lensCombinatorial
One transformation changes labels, another changes polynomial coordinates
Surjections and partitions differ by naming their nonempty fibers. Permutations and partitions differ by cyclic order within blocks. Powers and falling factorials are instead polynomial bases connected by counting image sizes. The same arrays connect these descriptions, but an equality of formulas does not make their objects interchangeable.
Exact tables and their computational cost
Compute one Stirling row from the preceding row, proceeding through all valid block counts. Both recurrences require quadratically many arithmetic operations to produce rows through a given index, and one may keep only two rows if earlier entries are not needed. Bell numbers are obtained by summing each second-kind row or by their own recurrence.
These are counts of arithmetic operations on integers that grow. For positive , every partition can be encoded by the function sending each label to the least label in its block. The encoding is injective because its nonempty fibers recover the blocks. Thus , giving an bound on the binary length of a partition count. Likewise cycle counts are at most . Elementary exact integer arithmetic therefore gives a polynomial bit implementation, although not the same unit-cost bound as the table's operation count.
A numerical evaluation of the formal Bell expression is not required to compute an exact count. The recurrence uses exact additions and integer products and preserves integrality automatically. Floating-point approximations to exponential functions would need a separate error argument before rounding could certify a coefficient.
Common mistakes
Counterexample mode
Stars-and-bars counts a different object
The positive integer solutions of are , so there are three. But . The integer solutions describe sizes in two named positions; they do not specify which four labels occur together, and a set partition's blocks are unnamed. The corrected model must track both label membership and whether block names matter.
The two remaining errors concern signs and conventions rather than the model.
Common mistake
(Dropping the signs of the first-kind numbers)
The expansion of in powers uses , not . Already , whereas the unsigned row would give . The signs alternate with .
Common mistake
(Permitting an empty block)
An empty block would make a partition of into two blocks, so would become instead of , and two empty blocks could not even be told apart. Do not permit an empty block merely to make a recurrence look uniform; use the explicitly stated zero conventions instead.
Summary
Set partitions and permutation cycles lead to different insertion recurrences. Bell numbers total the partition rows, while labeled block assembly explains their exponential generating function. The two Stirling kinds, with signs on the first, also provide inverse changes between ordinary powers and falling factorials.
Exercises
Quick check
(Compute and using their counting interpretations.)
Identify the only possible non-singleton cycle type in the second count.
Solution · Answer
: exclude the two constant assignments to two named boxes, then forget the names. A permutation on five labels with four cycles has one transposition and three fixed points, so . No longer cycle fits that cycle count.
Quick check
(Prove , and determine when this inequality is strict.)
Add the new label as a singleton and identify a partition outside that image.
Solution · Answer
Adding the new label as its own block injects partitions of into those of . For , the partition with block containing one and the new label together, and all other labels singleton, is not in the image. Thus for . At , both values are one, so equality holds exactly there among nonnegative indices.
Quick check
(Expand in falling factorials, and expand in ordinary powers.)
Use the fourth rows and check the two polynomial expressions at .
Solution · Answer
The second-kind row gives . Multiplying gives , consistent with signed cycle counts. At , the first expression gives , while the second gives , the correct fourth falling factorial value.