Exercise 889Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Counting onto functions

#onto#surjections#inclusion-exclusion

Statement

Count onto functions from an $n$ -element set to a $2$ -element set.

Hint

Either the function is constant (not onto) or not. Total $2^n$ .

Show solutionHide solution

Total. $2^n$ functions.

Not onto. Two constant functions (all to $1$ or all to $2$ ).

Onto. $2^n-2$ .

Conclusion. $2^n-2$ onto functions.

Check for $n=2$ . $2^2-2=2$ : the two non-constant functions. ✓