Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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

share|improve this question

2 Answers 2

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)?

share|improve this answer

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.

share|improve this answer
    
Do you mean $f(y)=x$ at the end of the first paragraph? –  Ross Millikan Mar 16 at 15:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.