Q.Find the number of all onto functions from the set $\{1, 2, 3, ..., n\}$ to itself.

Key idea: a function from a finite set to itself is onto exactly when it is one-one. Since $S=\{1,2,\dots,n\}$ is finite, an onto map $f:S\to S$ hits all $n$ values, so no two inputs can share an output — it is a bijection, i.e. a permutation of $S$. …

The key observation

Let $S=\{1,2,\dots,n\}$ and let $f:S\to S$ be onto. "Onto" means every one of the $n$ elements of $S$ is an output of $f$. But $f$ has only $n$ inputs to produce those $n$ distinct outputs. If two different inputs mapped to the same value, then $f$ would produce at most $n-1$ distinct outputs and could not cover all $n$ targets. So the outputs must all be distinct — $f$ is also one-one.

A map that is both one-one and onto is a bijection, and a bijection from a set to itself is exactly a rearrangement (permutation) of its elements.

Counting the permutations

Building a permutation, assign images one element at a time:

• $f(1)$ can be any of the $n$ elements — $n$ choices.
• $f(2)$ must differ from $f(1)$ — $n-1$ choices.
• $f(3)$ must differ from both — $n-2$ choices. …

Method: Counting onto functions from a finite set to itself

For a map from a finite set to itself, use the key equivalence: on a finite set, onto $\iff$ one-one $\iff$ bijection.

Steps

Step 1: Convert "onto" to "bijection"

An onto map $f:S\to S$ on an $n$-element set must hit all $n$ values with only $n$ inputs, so no two inputs can collide — it is automatically one-one, hence a permutation of $S$.

Step 2: Count the permutations

Assign images one input at a time: $n$ choices for the first, $n-1$ for the next, and so on down to $1$: …

Common Mistakes

Mistake 1: Counting all functions ($n^n$) instead of only the onto ones.

Why it's wrong: $n^n$ counts every map from the set to itself, most of which are not onto. Correct approach: use that on a finite set onto $\iff$ bijection, so the count is the number of permutations, $n!$.

Mistake 2: Reaching for the full inclusion–exclusion formula and mis-simplifying it. …