Surjection Examples

Combinatorics · Axiom Academy

Master counting surjections with step-by-step worked examples Excellent work! You've mastered surjection counting. Here's what we learned: Surjection Recognition: When distributing distinguishable objects into distinguishable boxes with no empty boxes, we're counting surjective functions. Two-Step Formula: The count equals S(n,k) × k! where S(n,k) is the Stirling number of the second kind, counting partitions of n objects into k non-empty groups. Stirling Numbers: S(n,k) can be computed using the recurrence relation S(n,k) = k·S(n-1,k) + S(n-1,k-1), or using the inclusion-exclusion formula. Why Multiply by k!: The Stirling number counts unordered partitions (which boxes get which groups doesn't matter). Since our boxes are distinguishable, we multiply by k! to account for all possible assignments. Alternative Method: Use inclusion-exclusion directly: k n - C(k,1)(k-1) n + C(k,2)(k-2) n - ... which gives the same result. This approach works for any surjection problem. Remember: S(n,k) × k! is your formula for distributing n distinguishable objects into k distinguishable boxes with no empty boxes!

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