Counting the number of functions on a 4-element set whose composite with itself maps 1 to 2

Question

Let $S = \{1, 2, 3, 4\}$, and let $F$ be the sets of all functions from $S$ to $S$.

How many functions exist such that $(f \circ f)(1) = 2$?

How many functions exist such that $(f \circ f)(1) = 2$, and $f$ is onto?

I'm not sure how to approach this problem really, any hints to help me count how many of these functions exist? Thanks in advance :)

Answer 1

Hint. If $f(f(1))= 2$ then $f(1)\not=1$. Hence $[f(1),f(2),f(3),f(4)]$ could be $$[2,2,?,?],\;[3,?,2,?],\;[4,?,?,2].$$ For the first question we can replace any ? with $1$, $2$, $3$, or $4$.

For the second question note that any onto function from $S$ to $S$ is a bijection!

Answer 2

Count them. It's as simple as that.

For the first problem, count how many function from $S$ to $S$ are there which satisfy one of the following conditions:

• $f(1)=2$ and $f(2)=2$;
• $f(1)=3$ and $f(3)=2$;
• $f(1)=4$ and $f(4)=2$.

After this, try to solve the second problem.