Counting Surjective Functions
What you'll learn: How to use the inclusion-exclusion principle to count the number of surjective (onto) functions from one finite set to another.
The Challenge
You've learned what surjective functions are—functions where every element in the codomain is "hit" by at least one element from the domain. But how many such functions exist from a set of size n to a set of size k?
The total number of functions from an n-element set to a k-element set is k^n (each of n elements has k choices). But counting only the surjective ones requires eliminating those functions that "miss" at least one codomain element.
Using Inclusion-Exclusion
This is a perfect job for the inclusion-exclusion principle! Let Aᵢ be the set of functions that do not map onto the i-th element of the codomain.
We want functions in none of these bad sets—that is, onto functions equal:
Total functions - |A₁ ∪ A₂ ∪ ... ∪ A_k|
By inclusion-exclusion:
- |Aᵢ| counts functions avoiding one specific element: (k-1)^n
- |Aᵢ ∩ A_j| counts functions avoiding two elements: (k-2)^n
- And so on...
The formula becomes:
Number of surjections = Σ (-1)^i · C(k,i) · (k-i)^n for i from 0 to k
This equals: k^n - C(k,1)(k-1)^n + C(k,2)(k-2)^n - ...
Example
Functions from {1,2,3} onto {A,B}: 2³ - C(2,1)·1³ = 8 - 2·1 = 6 surjective functions
Key Takeaway: The number of surjective functions is computed by inclusion-exclusion: start with all functions, then alternately subtract and add terms that count functions missing one or more codomain elements.