Exercise 1006Combinatorics › Inclusion-exclusionL1Added 3 Nov 2026

Counting surjections via inclusion-exclusion

#surjections#onto#IE

Statement

Count surjective functions from an $m$ -element set to an $n$ -element set (with $m\ge n$ ).

Hint

IE on "function misses element $i$ ".

Show solutionHide solution

Sets. $A_i=\{$ functions missing target $i\}$ .

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

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

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

Example. $m=4$ , $n=3$ : $3^4-3\cdot2^4+3\cdot1^4=81-48+3=36$ .