# number of function satisfy $f(x) = f^{-1}(x)$ in $f:\{1,2,3,4,5\}\rightarrow \{1,2,3,4,5\}$

(1) How many of function $f:\{1,2,3,4,5\}\rightarrow \{1,2,3,4,5\}$ satisfy $f(f(x)) = x\forall x\in \{1,2,3,4,5\}$

(2) How many of function $f:\{1,2,3,4,5\}\rightarrow \{1,2,3,4,5\}$ satisfy $f(f(x)) = f(x)\forall x\in \{1,2,3,4,5\}$

My try:: (1) If $f(f(x)) = x$ , then $f(x)=f^{-1}(x)$ means we have to calculate the function whose inverse is same as function $f(x)$ now after that how can i calculate it

Thanks

-

Hint: Are you familiar with cycle notation for permutations? For a single cycle, how long can it be to satisfy $f(x)=f^{-1}(x)$? How many ways are there to break your set of $5$ elements into cycles of th(is)(ese) length(s)?

-

The problem with your approach is that some of the functions that you want don’t have inverses; an example is the function $f(x)=1$ for all $x\in\{1,2,3,4,5\}$. Here’s a better idea: if $y$ is in the range of $f$, meaning that $y=f(x)$ for some $x\in\{1,2,3,4,5\}$, then we must have $f(y)=y$. In other words, $f$ must be the identity function on its range.

Suppose that the range of $f$ is $R\subseteq\{1,2,3,4,5\}$. We know what $f$ has to do on $R$: $f(x)=x$ for each $x\in R$. And $f$ can do anything at all to any $x\in\{1,2,3,4,5\}\setminus R$, so long as $f(x)\in R$. For example, if I choose $\{1,3,5\}$ for $R$, I know that $f(1)=1$, $f(3)=3$, and $f(5)=5$, while $f(2)$ and $f(4)$ can be any of $1,3$, and $5$. There are therefore $3^2=9$ ways to choose the values of $f(2)$ and $f(4)$, so there are $9$ functions of the desired kind that have range $\{1,3,5\}$.

More generally, if $R$ has $k$ elements, there are $k^{5-k}$ such functions with range $R$.

• What are the possible values of $k$?
• How many subsets of $\{1,2,3,4,5\}$ are there of each of those sizes?

If you can answer those questions, some simple (if slightly tedious) arithmetic will get you your answer. If you know about binomial coefficients and the binomial theorem, you can avoid the arithmetic.

-
Do you mean $f(y)=x$ at the end of the first paragraph? – Ross Millikan Mar 16 '14 at 15:10