Exercise 1629Combinatorics › Counting principlesL1Added 3 Nov 2026

Counting surjections

#surjections#inclusion-exclusion#Stirling

Statement

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

Hint

Use inclusion-exclusion on which elements are missed.

Show solutionHide solution

Solution

Total. $n^m$ functions.

Inclusion-exclusion. Subtract those missing at least one element:
$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m=n!\cdot S(m,n),$
where $S(m,n)$ is the Stirling number of the second kind.

Conclusion. Number of surjections $=n!\,S(m,n)=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m$ .

Example. $m=n$ : surjections = $n!$ .

Counting surjections

Statement

Solution

More problems in Counting principles