Give an explicit injection from the permutations in Sn with an odd number of fixed points into the permutations with an even number of fixed points.

Question

I'm not sure where to start. I know to prove injectivity I have to show that if $f(x)=f(y)$ then $x=y$. So I would say there are two permutations of the same odd number with k fixed points. Where do I go from there?

Answer 1

Send the nth odd-number-of-fixed-points permutation to the nth even-number-of-fixed-points permutation under the dictionary order on the tuple-representation.