Stirling numbers and set partitions

Write $S(n,k)$ for the number of ways to partition a specified n-element set into k nonempty unordered blocks. The empty set has one partition into zero blocks, while a nonempty set has none into zero blocks. More blocks than elements are impossible. To insert the largest label into a partition, distinguish whether it forms a singleton. If it does, delete that block and count a partition of the remaining labels into k minus one blocks.

If the largest label is not a singleton, remove it from its block. A partition into k nonempty blocks remains, and there are exactly k choices of the block to which the label can be restored. The blocks are not ordered, but they are distinct subsets of labels, so choosing one is meaningful. The two insertion cases are disjoint and reversible. This reasoning supplies a recurrence and its boundary conditions together, avoiding an unjustified division by a block-ordering factor at every stage.

A surjection from an n-element label set to k named boxes produces a set partition by its nonempty fibers. Conversely, a partition into k blocks produces k factorial surjections by assigning the k box names bijectively to its blocks. Every fiber of this forgetting map has the same size because the blocks are nonempty, disjoint, and distinguishable as subsets. The constant-fiber argument explains exactly why dividing the number of surjections by k factorial works here.

Inclusion-exclusion counts surjections by removing functions that miss one or more named boxes. Start from all k-to-the-n functions and alternate over the sets of forbidden boxes. With positive n, the resulting expression also handles cases where too many boxes are requested. The formula is useful for a fixed small block count, but alternating large terms may be a poor floating-point computation. The positive-term recurrence is usually safer for building a complete table with exact integer arithmetic.

A single nonempty block on a prescribed label set has EGF $e^x-1$. Exactly k unordered blocks therefore have EGF $(e^x-1)^k/k!$. This is a formal coefficient identity over the rationals: the zero constant term makes every coefficient calculation finite. Summing over k gives the Bell-number EGF, since the block count of a partition of n cannot exceed n. Ordinary integer partitions do not obey this formula because they record sizes without distributing distinct labels.

One can also use set partitions to sort all functions into cases according to the number of distinct image values. First partition the domain into nonempty fibers, then assign distinct codomain values to those blocks. The number of injective assignments is a falling factorial. This gives an identity expressing ordinary powers in the falling-factorial basis. It is another counting proof, not merely a change of polynomial notation, and it makes the distinction between unlabeled blocks and labeled image values visible.