4
$\begingroup$

Let $f : \{1, 2, 3, 4, 5, 6, 7\} \to \{1, 2, 3, 4, 5, 6, 7\}$, then number of functions with $f(f(f(x))) =x$.

The right answer comes to be $317$. I am unable to solve it. This question comes from jee advanced preparation test and its solution is not given.

$\endgroup$
2
  • 3
    $\begingroup$ Welcome to MathSE. Please edit your question to show what you have attempted and explain where you are stuck. This MathJax tutorial explains how to typeset mathematics on this site. $\endgroup$ Commented Jul 27, 2023 at 8:49
  • $\begingroup$ Are you sure the answer is 317? i think 351 is the answer. (did they say "conceptual" in the answer key?) $\endgroup$ Commented Jul 27, 2023 at 10:15

2 Answers 2

6
$\begingroup$

Let set $A=\{1,2,3,4,5,6,7\}$

Case (1) - Every element of $A$ satisfies $f(x)=x$, only $1$ function can exist as such (Identity function).

Case (2) - function $f(x)$ is Identity function for 4 elements in set $A$, which can be made as $\binom{7}{4}\times2$, or $70$ functions.

Case (3) - function $f(x)$ is Identity function for any 1 element in set $A$, making the total number of functions as $\binom{7}{1}\frac{6!\times4}{3!\times3!\times2!}$, or $280$ functions.

$$Total=1+70+280=351$$

Extras - This problem can be generalized;

Let $f$ be defined as follows; $f:A\rightarrow A$

Where, $A$ has $k$ distinct elements $f(f(f(x)))=x$, to find the number of functions $f$ satisfying this for all $x\in A$ can be done easily as I recall, exactly for such kinds of questions which could be solved by a generating a sequence and establishing a recurrence relation for the number of functions, particularly, it is $a_n=a_{n-1}+(n-1)(n-2)a_{n-3} \, for \,1,1,3,9,21,81,\boxed{351},\cdots$

$\endgroup$
6
$\begingroup$

First let's notice that the condition $f(f(f(x))) = x$ implies that $f$ is a bijection with inverse $f\circ f$. This means that we are looking for permutations of $7$ elements. Furthermore, $f(f(f(x))) = x$ means that the order of permutation must divide $3$, so the order is $1$ or $3$.

We can break any permutation into its cycles and order of permutation is equal to the least common multiple of the lengths of cycles. That means that all cycles' lengths must divide $3$, so we are looking at permutations that only have cycles of length $1$ or $3$.

The sum of lengths of cycles is $7$, so we want partitions of $7$ such that all summands are $1$ or $3$ and all the cases (up to commutativity) are: $$7=1+1+1+1+1+1+1 = 1+1+1+1+3 = 1+3+3,$$ i.e. we want to find all permutations with precisely $0$, $1$ or $2$ cycles of length $3$ and all other points fixed.

There is only $1$ such permutation with $0$ cycles of length $3$, the identity $f(x) = x$.

To find such permutations with $1$ cycle of length $3$, choose $3$ elements in $\binom 73$ different ways to be in the cycle and fix the rest. There are $2$ permutations of three elements of order $3$ (they are $(123)$ and $(132)$), for total of $2\cdot\binom 73 = 70$ permutations.

To find such permutations with $2$ cycles of length $3$, choose the elements of cycles in $\frac 12\binom 73\binom43$ ways (we need to divide by $2$ since we overcounted because each pair of cycles can be chosen in two different orders). Like above, for each cycle we have $2$ permutations of order $3$, for the total of $2\cdot 2\cdot \frac 12\binom 73\binom43 = 280$ permutations.

The total is $1+70+280 = 351$ permutations.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .