MHB Total number of function from A to A

[juantheron]

If $A = \left\{1,2,3,4,5\right\}$. Then total number of function from $A$ to $A$

for which $f(f(x)) = x$

 

[Nono713]

If $A = \left\{1,2,3,4,5\right\}$. Then total number of function from $A$ to $A$

for which $f(f(x)) = x$

Spoiler

Firstly, $f$ must be onto. Proof: suppose $f$ is not onto, so $f(x)$ never takes some value $y$. Then $f(f(y))$ cannot equal $y$ and the function fails to meet the requirements. Next, $f$ must be one-to-one. Proof: suppose $f$ is not one-to-one, so $f(x) = f(y)$ for some distinct $x$, $y$. Now assume towards a contradiction that $f(f(x)) = x$ for all $x$. Then $f(f(y)) = x$ for $x \ne y$, and so there can be no such function.

Hence $f$ must necessarily be a bijection, i.e. a permutation. We can now consider the group of permutations of five elements $S_5$ and specifically the elements $a$ such that $a^2 = e$. There are 26 such elements (25 elements of order 2 and the identity) so there are 26 functions. QED.​