Number of functions $f$ on $\{1,\cdots,7\}$ s.t. $f(f(x))$ is constant

Question

Let $A = \{1,2,3,4,5,6,7\}$. Find the number of functions $f$ from set $A$ to set $A$ such that $f(f(x))$ is a constant function.

Please help me out. I tried all sort of combinations but not reaching to any concrete method to get the final answer.

Answer 1

Clear that $f$ cannot be onto! Otherwise the range of $f$. Condition $f(f(x)$ is constant means when $f$ is restricted to its image it has to be a constant function. Let $B\subset A$ be a proper subset.

Easy to see that there is a $b\in B$ such that $f(B)=\{b\}$. (STEP 1)

Now $f$ can send anything outside $B$ to any element of $B$. (STEP 2)

First calculate how many functions are there satisfying STEP 2, for every proper subset of $B$.

Step 1 is as many as there are elements of $B$.

You should be able to complete as I have now split your problem into easier smaller problems.

Answer 2

Let $f^{\circ2}(x)=c$ for all $x\in A$. If $f(c)=d$ then $f(d)=f^{\circ2}(c)=c$ and $f^{\circ2}(d)=f(c)=d$, hence $d=c$, i.e., $f(c)=c$. Let $A':=A\setminus\{c\}$. We cannot have $f(A')\subset A'$. Therefore there is a nonempty subset $A_c\subset A'$ with $f(x)=c$ for $x\in A_c$ and $f(x)\in A_c$ for $x\in A'\setminus A_c$.

The point $c\in A$ can be chosen in $7$ ways. If $|A_c|=r\in[1 .. 6]$ the set $A_c\subset A'$ can be chosen in ${6\choose r}$ ways. The partial function $f:\>A'\!\setminus\! A_c\>\to A_c$ can be chosen in $r^{6-r}$ ways.