Exercise 1614Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Surjection formula proof

#surjection#inclusion-exclusion#onto

Statement

Prove the surjection formula $\text{Surj}(m,n)=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m$ .

Hint

Inclusion-exclusion on missed elements.

Show solutionHide solution

Setup. Let $A_i$ = functions missing element $i$ (out of $n$ targets).

Count. $|A_{i_1}\cap\cdots\cap A_{i_k}|=(n-k)^m$ .

Inclusion-exclusion.
$\text{Surj}(m,n)=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m.$

Conclusion. Formula holds.