Functions and Combinatorics

Question

If a function $f$ is defined as $f : \{1, 2, 3, 4\}\to \{1, 2, 3, 4\}$ such that $$f(f(x)) = f(x), \ \ \ \ \forall x\in \{1, 2, 3, 4\}.$$ and $S$ is the number of such functions then find $S$.

We can easily figure out that one way of doing this is $f(x) =x$. Then $$f(f(x)) = f(x) = x.$$ Or we can have some cases like $f(i) = i$ only for some elements and others are mapped carefully according to the conditions.

How should I proceed? Also can you suggest some alternate methods.

Answer 1

$\newcommand{\ran}{\operatorname{ran}}$I’ll get you started. The requirement that $f\big(f(x)\big)=f(x)$ means that every element of the range of $f$ must be a fixed point of $f$, i.e., a point such that $f(x)=x$.

• If $\ran(f)=\{1,2,3,4\}$, then $f$ must be the identity function: $f(x)=x$ for all $x\in\{1,2,3,4\}$.
• If $\ran(f)=\{1,2,3\}$, then we must have $f(1)=1$, $f(2)=2$, and $f(3)=3$, but $f(4)$ can be any of $1,2$, and $3$; how many different functions does that allow? And much the same thing happens when the range of $f$ is any $3$-element subset of $\{1,2,3,4\}$.
• If $\ran(f)=\{1,2\}$, then $f(1)=1$ and $f(2)=2$, but each of $f(3)$ and $f(4)$ can be either $1$ or $2$; how many different functions does that allow? And again, much the same thing happens when the range of $f$ is any $2$-element subset of $\{1,2,3,4\}$.
• Now what happens when $f$ is constant, i.e., has a $1$-element range?