# Number of functions

Let $F$ denote the set of all functions from $\{1,2,3\}$ to $\{1,2,3,4,5\}$

a) Find and simplify the number of functions $f$ in $F$ so that $f(1)=4$.

b) Find and simplify the number of one-to-one functions $f$ in $F$ so that $f(1)$ is greater than or equal to $4$.

c) Find and simplify the number of functions $f$ in $F$ so that $f(1)$ does not equal $f(2)$.

For (a) I have no idea how to write it out, and for (c) can't I make $f(1)=1$ and $f(2)=2,3,4,5$ that way they don't equal each other?

-
For c) you have to work out, for each choice of $f(1)$, how many allowable choices there are for $f(2)$, and then you still have to think about the number of possibilities for $f(3)$. – Gerry Myerson May 24 '13 at 9:32

This whole problem is basically just an exercise in using the multiplication principle, also sometimes called the Chinese menu principle:

Suppose that you are making a sequence of $k$ choices. There are $n_1$ different ways to make the first choice, $n_2$ different ways to make the second choice, and so on, through $n_k$ different ways to make the $k$-th choice. Then there are altogether $n_1n_2\dots n_k$ different ways to make the whole sequence of choices.

(a) Once you set $f(1)=4$, you must assign values to $f(2)$ and $f(3)$. In each case this means picking one of the $5$ numbers $1,2,3,4$, and $5$, so there are $5\cdot5=25$ ways to make the two choices. Once you’ve done that, you’ve completely defined the function $f$, so there are $25$ functions $f:\{1,2,3\}\to\{1,2,3,4,5\}$ such that $f(1)=4$.

(b) The same basic approach to solving the problem and to explaining the solution can be used here as well.

(c) No, you can’t simply make $f(1)=1$ and choose $f(2)\in\{2,3,4,5\}$: if you count only those functions, you’re missing all of the functions that have $f(1)=3$ and $f(2)=5$, for instance. Once again look at it in terms of building $f$ one value at a time. You can let $f(1)$ be any of the five numbers $1,2,3,4$, and $5$. No matter which value you choose, you can let $f(2)$ be any of the four remaining numbers. Finally, you can let $f(3)$ be any of the five numbers. This sequence of three choices can be made in $5\cdot4\cdot5=100$ ways.

-

a) We introduce some notation: Let $A,B$ be abitrary, non-empty (finite) sets and let $A^B := \{f \subseteq A \times B \ | \ f: A \mapsto B \}$. Let (for a given set $A$) $|A|$ be the number of elements of $A$. Now, a nice way to solve your problem is the following:

1. Show that $|A^B| = |A|^{|B|}$

2. Show that $F_a := \{ f \in F \ | \ f(1) = 4 \} \overset{\text{bijective}}\cong \{2,3\}^{\{1,2,3,4,5\}}$

b) Assuming "one-to-one functions" refers to injective functions: Let $F_b := \{ f \in F \ | \ f \text{ is injective }, f(1) \ge 4 \}$. Then $F_b$ is the disjoint union $F_b = \{ f \in F \ | \ f \text{ is injective }, f(1) = 4\} \cup \{ f \in F \ | \ f \text{ is injective }, f(1) = 5\}$. Hence, it is sufficient to prove that

1. $X := \{ f \in F \ | \ f \text{ is injective }, f(1) = 4\} \overset{\text{bijective}}\cong \{ f \in F \ | \ f \text{ is injective }, f(1) = 5\} \overset{\text{bijective}}\cong \{ (x,y) \in \{1,2,3,4\} \times \{1,2,3,4\} \ | \ x \neq y \}$
2. $|\{ (x,y) \in \{1,2,3,4\} \times \{1,2,3,4\} \ | \ x \neq y \}| = |\{1,2,3,4\}\times\{1,2,3,4\}| - |\{(1,1),(2,2),(3,3),(4,4)\}| = 4^2-4$

c) Let $F_c := \{ f \in F \ | \ f(1) \neq f(2)\}$. Then $F_c = F \setminus F_{1,2}$, where $F_{1,2} := \{ f \in F \ | \ f(1) = f(2) \}$ and show that $F_{1,2} \overset{\text{bijective}}\cong \{2,3\}^{\{1,2,3,4,5\}}$. Finally use the technique developed in a) to calculate $|F|$ and $|F_{1,2}|$ which allows you to get $|F_c| \overset{!}= |F| - |F_{1,2}|$.

-
It’s not necessary to assume that one-to-one function means injective function, since it’s a standard term that never means anything else. – Brian M. Scott May 24 '13 at 16:29