MHB Total number of function from A to A

  • Thread starter Thread starter juantheron
  • Start date Start date
  • Tags Tags
    Function
juantheron
Messages
243
Reaction score
1
If $A = \left\{1,2,3,4,5\right\}$. Then total number of function from $A$ to $A$

for which $f(f(x)) = x$
 
Mathematics news on Phys.org
jacks said:
If $A = \left\{1,2,3,4,5\right\}$. Then total number of function from $A$ to $A$

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

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.​
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top