Which function, partition, or relation count do I need?
The decision path from "how many maps/splits/relations" to the right count in Chapter 5.
Reach for this whenever a problem asks how many functions, set partitions, or equivalence relations exist between or on finite sets. Start with whether every input needs a distinct or covered output, then decide whether the target blocks are labeled or not.
Step 1 — does every output need to be distinct, covered, or neither?
Example
No two inputs may share an output -- a falling factorial count.
Example
Every target must be hit at least once -- inclusion-exclusion.
Step 2 — are the target blocks labeled or unlabeled?
Example
Unlabeled, nonempty blocks, exactly k of them.
Term
Bell number
Example
Unlabeled blocks, any number of them at all.
Formulas this decision path leads to
The number of surjective (onto) functions from an n-element set to an m-element set is \sum_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n
Show proof
There are m^n total functions from the n-set to the m-set. Let A_j be the set of functions that miss target element j (never map anything to j). A function is surjective exactly when it lies in none of A_1,\ldots,A_m, so the count is m^n - \left|\bigcup_{j=1}^m A_j\right|. Fixing any i target elements to be missed leaves m-i allowed targets for every one of the n inputs, so a i-fold intersection has (m-i)^n functions, and there are \binom{m}{i} ways to choose which i targets to miss. The general inclusion-exclusion formula gives \left|\bigcup_{j=1}^m A_j\right| = \sum_{i=1}^m (-1)^{i+1}\binom{m}{i}(m-i)^n, so the surjection count is m^n - \sum_{i=1}^m (-1)^{i+1}\binom{m}{i}(m-i)^n = \sum_{i=0}^m (-1)^i\binom{m}{i}(m-i)^n, since the i=0 term of the final sum is exactly m^n.
The number of surjective functions from an n-element set onto an m-element set is \operatorname{Surj}(n,m) = m!\,S(n,m) where S(n,m) is the Stirling number of the second kind counting partitions of the n-set into m nonempty blocks.
Show proof
Let f be a surjection from an n-set A onto an m-set B. The fibers f^{-1}(b) for b\in B are pairwise disjoint, cover A, and are all nonempty precisely because f is onto — so they form a partition of A into exactly m nonempty blocks. Conversely, start from any partition of A into m nonempty blocks and any bijection from its blocks to B; sending each element to the label of its block defines a surjection onto B. These two constructions invert each other: a surjection recovers its own fiber partition together with the labeling "block f^{-1}(b) maps to b," and distinct (partition, labeling) pairs give distinct surjections. There are S(n,m) choices of partition and, independently, m! bijections from its m blocks to B, so the product rule gives \operatorname{Surj}(n,m) = m!\,S(n,m).