Example 22: Number of one-one functions on {1, 2, 3}

Basics you need

Solution

1. Describe every function by a list of three values

   A function $f : \{1,2,3\} \to \{1,2,3\}$ is completely known once we know $f(1)$⁠, $f(2)$ and $f(3)$⁠. So we can record it as the ordered list

   $$\big(f(1),\, f(2),\, f(3)\big).$$

   Each entry is chosen from $\{1,2,3\}$⁠. For example, the list $(2,2,1)$ means $f(1)=2,\ f(2)=2,\ f(3)=1$⁠. Different lists give different functions, and every list gives a function. Since each of the three entries can be any of 3 values, there are $3 \times 3 \times 3 = 27$ functions from $A$ to itself altogether.

   Turning a function into a list of values changes a question about "functions" into a question about "lists", and lists are easy to count. Nothing is lost: two functions on the same domain are equal exactly when they agree at every point, which is exactly when their lists are equal.
   A function must give one output for each input (Basic 1). That is why the list has exactly one entry per input, and why every entry must be filled in.

2. Translate "one-one" into a condition on the list

   One-one means no two different inputs share an output. With inputs 1, 2, 3 this says

   $$f(1) \ne f(2), \qquad f(1) \ne f(3), \qquad f(2) \ne f(3).$$

   So the three entries of the list must all be different. Three different numbers taken from the three-element set $\{1,2,3\}$ must use up every element, so the list is just $1, 2, 3$ written in some order: a permutation of the three symbols. For instance $(2,2,1)$ is not one-one ($f(1)=f(2)$⁠), while $(2,3,1)$ is.

   The definition of one-one is about pairs of inputs. A set of three inputs has exactly three pairs, $\{1,2\}, \{1,3\}, \{2,3\}$⁠, so checking those three inequalities is a complete check. This is the textbook's observation that a one-one function from $\{1,2,3\}$ to itself "is simply a permutation on three symbols".
   One-one: $x_1 \ne x_2 \Rightarrow f(x_1) \ne f(x_2)$ (Definition 5, Basic 2). On a finite set, "all outputs different" and "one-one" are the same statement.

3. Count the lists one entry at a time

   Build a one-one function by choosing its values in order.

   • Choose $f(1)$⁠: any of 1, 2, 3. That is 3 ways.
   • Choose $f(2)$⁠: it must differ from $f(1)$⁠, so one value is ruled out. Whatever $f(1)$ was, 2 values remain.
   • Choose $f(3)$⁠: it must differ from both $f(1)$ and $f(2)$⁠, which are two different values. Exactly 1 value remains, so $f(3)$ is forced.

   By the multiplication principle,

   $$\text{number of one-one functions} = 3 \times 2 \times 1 = 3! = 6.$$
   The multiplication principle needs the number of choices at each stage to be the same no matter what was chosen before. It is: after any choice of $f(1)$ there are always exactly 2 values left for $f(2)$⁠, and after any two different values there is always exactly 1 left for $f(3)$⁠. The tree shows this: every blue node has two children, every gold node has one.
   Multiplication principle (Basic 3) and $n! = n(n-1)\cdots1$ (Basic 4). Counting arrangements of $n$ different objects gives $n!$ because the first place has $n$ options, the next $n-1$⁠, and so on down to 1.

4. List all six to confirm

   Function	$f(1)$	$f(2)$	$f(3)$	Description
   $f_1$	1	2	3	the identity $I_A$
   $f_2$	1	3	2	swaps 2 and 3
   $f_3$	2	1	3	swaps 1 and 2
   $f_4$	2	3	1	cycles $1\to2\to3\to1$
   $f_5$	3	1	2	cycles $1\to3\to2\to1$
   $f_6$	3	2	1	swaps 1 and 3

   Each row uses 1, 2 and 3 exactly once, so each is one-one, and no permutation of 1, 2, 3 is missing (there are only 6). Hence there are exactly 6 one-one functions from $A$ to itself.

   The count from Step 3 is an argument; the list is an independent confirmation. Writing them in "dictionary order" (by $f(1)$⁠, then $f(2)$⁠) makes it easy to see that none is repeated and none is left out. It also shows each one is onto: every element of $A$ appears as an output, which matches Example 14 (one-one on $\{1,2,3\}$ forces onto).
   On a finite set, a one-one function from the set to itself is automatically onto, hence bijective. So these 6 functions are exactly the bijections of $A$⁠. Lesson: types of functions

5. Compare with all 27 functions

   Of the 27 functions in Step 1, the other $27 - 6 = 21$ are not one-one. They split into two kinds:

   • Constant functions (all three outputs equal): $(1,1,1), (2,2,2), (3,3,3)$⁠. That is 3 functions.
   • Exactly two different outputs, such as $(2,2,1)$⁠: the remaining $21 - 3 = 18$ functions.
   $$\underbrace{6}_{\text{3 different values}} + \underbrace{18}_{\text{exactly 2 values}} + \underbrace{3}_{\text{1 value}} = 27 = 3^3.$$
   Sorting all 27 functions by how many different outputs they use accounts for every function exactly once, and the three groups add up to the total. That is a strong check that 6 is right. It also shows how restrictive "one-one" is: only 6 of the 27 functions qualify.
   Every function uses 1, 2 or 3 different output values, never anything else, so these three groups cover all cases without overlap.

Every fact used, and where it comes from