Chapter 1 · Relations and Functions

Miscellaneous · Q4: Number of onto functions from $\{1, 2, \dots, n\}$ to itself

Miscellaneous ExerciseCounting functions · Miscellaneous Exercise

The question

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

Exam answer

Let $S = \{1, 2, \dots, n\}$ and $f : S \to S$ ⁠.

If $f$ is onto, the $n$ values $f(1), \dots, f(n)$ cover all $n$ elements of $S$ ⁠, so no two are equal: $f$ is one-one. If $f$ is one-one, the $n$ values are distinct, so they fill $S$ ⁠: $f$ is onto.

So the onto functions are exactly the one-one functions. Choosing $f(1), f(2), \dots, f(n)$ in turn, with no value repeated, there are $n, n - 1, \dots, 1$ choices. So the number of such functions is

n(n - 1)(n - 2)\cdots 2\cdot 1 = n!

The number of onto functions is $n!$ ⁠.

Want the reason behind every step, the basics and the checks?

The one idea this problem is built on

When a function goes from a finite set to itself, "onto" and "one-one" are the same condition. There are $n$ inputs and $n$ targets: to hit all $n$ targets, the $n$ outputs must all be different, and $n$ different outputs automatically hit every target. So counting onto functions is the same as counting one-one functions, that is, arrangements of $1, 2, \dots, n$ ⁠, and the multiplication principle gives $n \times (n-1) \times \dots \times 1 = n!$ ⁠.

Given, to find, and the plan

Given: The set $S = \{1, 2, \dots, n\}$ ⁠, with $n$ elements, used both as domain and as codomain.
To find: How many functions $f : S \to S$ are onto.
Plan: (1) Describe a function by its list of values. (2) Prove onto $\Rightarrow$ one-one, and (3) one-one $\Rightarrow$ onto, so the two sets of functions are identical. (4) Count one-one functions by making the choices $f(1), f(2), \dots, f(n)$ in turn, and show every such function is counted exactly once. (5) Conclude and check with small $n$ ⁠.

Basics you need

1A function is its list of values

A function $f : S \to S$ assigns to each input exactly one output. On $S = \{1,\dots,n\}$ it is completely described by the list $(f(1), f(2), \dots, f(n))$ ⁠, and two functions are equal exactly when their lists agree in every position. Basics: what a function is

2One-one and onto

One-one: different inputs give different outputs. Onto: every element of the codomain is an output, that is, the range equals the codomain. Basics: one-one and onto

3The multiplication principle

If a task is done in stages, with $m_1$ ways for the first stage, then $m_2$ ways for the second whatever the first choice was, and so on, the number of ways to do the whole task is $m_1 \times m_2 \times \cdots$ ⁠. Basics: counting choices

4Factorial

$n! = n \times (n-1) \times \dots \times 2 \times 1$ ⁠. For example $3! = 6$ ⁠, $4! = 24$ ⁠, $5! = 120$ ⁠. It counts the arrangements (permutations) of $n$ different objects.

Solution

Write each function as a list of values

By Basic 1, a function $f : S \to S$ is the same thing as a list $(f(1), f(2), \dots, f(n))$ in which each entry is one of $1, \dots, n$ ⁠. For instance, with $n = 3$ ⁠, the list $(2, 3, 1)$ means $f(1) = 2$ ⁠, $f(2) = 3$ ⁠, $f(3) = 1$ ⁠. In this language:
- the range of $f$ is the set of numbers appearing in the list;
- $f$ is onto when every number $1, \dots, n$ appears in the list;
- $f$ is one-one when no number appears twice.
For $n = 3$ ⁠, the list $(1, 1, 2)$ is a function that is neither: 1 appears twice and 3 never appears.

Lists are much easier to count than "rules". Each function gives exactly one list and each list gives exactly one function, so counting functions with a property is the same as counting lists with the matching property.

Range of $f$ = $\{f(1), \dots, f(n)\}$ ⁠; onto $\iff$ range = codomain (the Remark after Definition 6). Lesson: types of functions
Onto forces one-one

Let $f$ be onto. Then the range $\{f(1), \dots, f(n)\}$ is all of $S$ ⁠, so it has exactly $n$ elements. Suppose, for contradiction, that two different inputs had the same output, say $f(i) = f(j)$ with $i \neq j$ ⁠. Then the list of $n$ values contains a repeat, so it has at most $n - 1$ different values, and the range has at most $n-1$ elements. That contradicts "the range has $n$ elements". So no two inputs share an output: $f$ is one-one.

This is the textbook's Example 13 argument (done there for $n=3$ ⁠) written for a general $n$ ⁠. The key is counting: a list of $n$ entries with a repeat cannot show all $n$ numbers. We argue by contradiction because "one-one" is a statement about every pair of inputs, and assuming a single failing pair leads straight to a count that is too small.

A list of $n$ entries has at most $n$ different values, and fewer if any value repeats (the pigeonhole idea). See Example 13 for the case $n = 3$ ⁠.
One-one forces onto

Let $f$ be one-one. Then the $n$ values $f(1), \dots, f(n)$ are all different, so the range is a subset of $S$ with $n$ elements. But $S$ itself has only $n$ elements, and the only subset of $S$ with $n$ elements is $S$ ⁠. So the range is $S$ ⁠: $f$ is onto.

Together with Step 2: for $f : S \to S$ ⁠,
$\text{onto} \iff \text{one-one} \iff \text{bijective}.$
So the onto functions are exactly the one-one functions, and we may count those instead.

Step 3 is not needed to get an upper bound, but it is needed for an exact count: it shows that every one-one function is onto, so when we count one-one functions in Step 4 we are counting onto functions and nothing else. This is the Remark after Examples 13 and 14: for a finite set the two properties coincide. For an infinite set they do not; $f(x) = 2x$ on $\N$ is one-one but not onto (Example 8).

A subset of a finite set with as many elements as the whole set is the whole set. See Example 14 for $n = 3$ ⁠.

Count the one-one functions, one value at a time

Build a one-one function by choosing its values in order, never reusing a value already taken:

Stage	Values already used	Number of choices
choose $f(1)$	none	$n$
choose $f(2)$	$f(1)$	$n - 1$
choose $f(3)$	$f(1), f(2)$	$n - 2$
$\vdots$	$\vdots$	$\vdots$
choose $f(k)$	$k - 1$ values	$n - k + 1$
choose $f(n)$	$n - 1$ values	$1$

By the multiplication principle the number of one-one functions is

n(n-1)(n-2) \cdots 2 \cdot 1 = n!.

The choice tree for

n = 3

⁠. Each level fixes one value; the number of branches drops by one at each level because a value already used may not be used again. The 6 complete paths are the 6 onto functions, written as

(f(1), f(2), f(3))

⁠.

Why every function is counted exactly once. Each complete path through the tree is a list of $n$ different values, which is a one-one function. Conversely, every one-one function appears: at stage $k$ its value $f(k)$ differs from $f(1), \dots, f(k-1)$ ⁠, so it is one of the allowed choices, and following its values picks out one path. Two different paths differ at some stage $k$ ⁠, so they give different values $f(k)$ and therefore different functions. Hence paths and one-one functions match one-to-one, and the count $n!$ has no omissions and no repeats.

The multiplication principle needs the number of choices at each stage to be the same whatever happened earlier. That is true here: at stage

k

⁠, exactly

k-1

values are used up (they are all different), so exactly

n-k+1

remain, no matter which ones were used. The textbook makes the same count for

n = 3

in Example 22, where it calls these functions permutations of the symbols 1, 2, 3.

Multiplication principle (Basic 3). The

n!

arrangements of

1, \dots, n

are the permutations. Basics: counting choices

Conclude

By Steps 2 and 3, the onto functions from $\{1, \dots, n\}$ to itself are exactly the one-one functions, and by Step 4 there are $n!$ of these. So the number of onto functions is $n!$ .

The answer is a count of one-one functions, but it is the answer to the question about onto functions only because Steps 2 and 3 showed the two collections are identical. Both directions were needed.

On a finite set, $f : X \to X$ is one-one if and only if it is onto (the chapter Summary). Lesson: counting functions and relations

Result

The number of onto functions from $\{1, 2, \dots, n\}$ to itself is $n!$ . On a finite set, onto and one-one coincide, so these are the one-one functions, chosen as $n$ ways for $f(1)$ ⁠, $n-1$ for $f(2)$ ⁠, and so on down to 1 way for $f(n)$ ⁠. (Textbook answer: $n!$ ⁠.)

Check it with numbers

For $n = 3$ there are $3^3 = 27$ functions in all (3 choices for each of 3 values, with repeats allowed). Listing all 27 and keeping those in which 1, 2 and 3 all appear leaves exactly the 6 lists $(1,2,3)$ ⁠, $(1,3,2)$ ⁠, $(2,1,3)$ ⁠, $(2,3,1)$ ⁠, $(3,1,2)$ ⁠, $(3,2,1)$ ⁠, and $3! = 6$ ✓. The other 21, such as $(1,1,2)$ ⁠, each miss at least one value. The site's verification script repeats this brute force for every $n$ from 1 to 6 (up to $6^6 = 46656$ functions) and finds $1, 2, 6, 24, 120, 720$ onto functions, which are $1!, \dots, 6!$ ⁠, and in each case the onto functions are exactly the one-one ones.

Common mistakes

Answering $n^n$ ⁠. That counts all functions from $S$ to $S$ ⁠, including the many that repeat a value and miss another.
Counting with $n$ choices at every stage. After $f(1)$ is chosen, it may not be reused, so the next stage has $n-1$ choices, not $n$ ⁠.
Using the "onto = one-one" shortcut for infinite sets. It holds only because $S$ is finite and the function maps $S$ to itself. On $\N$ ⁠, Examples 8 and 10 show it fails both ways.
Proving only one direction. To replace "onto" by "one-one" in the count, both onto $\Rightarrow$ one-one and one-one $\Rightarrow$ onto are needed.

What to take away

For $f : S \to S$ with $S$ finite: one-one $\iff$ onto $\iff$ bijective.
Count functions by choosing their values one input at a time; the multiplication principle does the rest.
Every count should come with a reason that nothing is missed and nothing is counted twice. Here that reason is the match between paths in the choice tree and one-one functions.

Every fact used, and where it comes from

Fact	Used in	Source
One-one, onto, bijective; onto $\iff$ range = codomain	Steps 1–3	Definitions 5–7 and the Remark after Definition 6, Section 1.3 (Lesson: types of functions)
Onto $\Rightarrow$ one-one and one-one $\Rightarrow$ onto on a finite set	Steps 2, 3	Examples 13, 14 and the Remark after them, Section 1.3; chapter Summary
$f(x)=2x$ on $\N$ is one-one but not onto	Step 3	Example 8, Section 1.3
Multiplication principle; $n!$	Step 4	Class XI, Permutations and Combinations (Basics: counting choices)
One-one maps of $\{1,2,3\}$ are the $3! = 6$ permutations	Step 4, Check	Example 22, Miscellaneous Examples
Counts $1!, \dots, 6!$ by enumerating all $n^n$ functions	Check	Brute force in the site's verification script

Found an error, or want more?

Tell us if something on this page is wrong or unclear, or if you would like a fuller explanation, another method or a new feature. Send feedback on this problem →

Miscellaneous · Q4: Number of onto functions from {1,2,…,n}\{1, 2, \dots, n\}{1,2,…,n} to itself

Basics you need

Solution

Write each function as a list of values

Onto forces one-one

One-one forces onto

Count the one-one functions, one value at a time

Conclude

Every fact used, and where it comes from

Miscellaneous · Q4: Number of onto functions from $\{1, 2, \dots, n\}$ to itself