Counting Surjections

Combinatorics · Axiom Academy

Using inclusion-exclusion to count surjective functions and derive the Stirling number formula A function f: A → B is surjective if every element in the codomain B is hit by at least one element from the domain A. Let's visualize this with sets of size n = 4 and k = 3. How many surjective functions are there from an n-element set to a k-element set? We'll use inclusion-exclusion : start with all k n functions, then subtract those that miss at least one element in the codomain. 3. Inclusion-Exclusion Formula Let A i be the set of functions that miss element i in the codomain. By inclusion-exclusion, the number of surjections is the total minus functions missing at least one element. 4. Simplifying to the Final Formula The inclusion-exclusion sum simplifies beautifully. Functions missing a specific subset S of size j can map to only (k - j) elements, giving us (k - j) n choices. There are C(k, j) such subsets. 5. Stirling Numbers of the Second Kind The number of surjections is intimately connected to Stirling numbers S(n, k) , which count the ways to partition an n-element set into k non-empty subsets. Each partition corresponds to k! surjections (one for each labeling of the subsets).

This is the written version of the interactive lesson above. See the full Combinatorics course.