Exercise 1616Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Surjections via inclusion-exclusion

#surjections#inclusion-exclusion#function counting

Statement

Count surjections from a $4$ -element set to a $3$ -element set.

Hint

Use the inclusion-exclusion formula for surjections.

Show solutionHide solution

Formula. $\text{Surj}(4,3)=3^4-\binom{3}{1}2^4+\binom{3}{2}1^4-\binom{3}{3}0^4$ .

Compute. $81-3\cdot16+3\cdot1-0=81-48+3=36$ .

Alternative. $3!\,S(4,3)=6\cdot6=36$ .

Conclusion. There are $36$ surjections.