I am to find the number of permutations of a set which contains $55$ elements and the permutations meet following requirements:
$$\forall_{i\in \{1, 2, ..., 55\}} f(i)\neq i \wedge f \circ f = id$$
Asked
Active
Viewed 80 times
2
Hendrra
- 2,868
- 1
- 18
- 35
-
You are counting the fixed-point free involutions in $S_{55}$? I don't think there are very many of them. – Angina Seng Apr 26 '17 at 19:04
-
2Try with 3 instead of 55. – Catalin Zara Apr 26 '17 at 19:05
-
Me neither but I really would like to see if there is a method of finding the solution – Hendrra Apr 26 '17 at 19:06
-
I tried but I think I don't know how to use the second requirement @CatalinZara – Hendrra Apr 26 '17 at 19:07
-
If, say, $f(1) = 2$, then what is $f(2)$? – Catalin Zara Apr 26 '17 at 19:08
-
$f(2) = 1$ according to the first requirement? @CatalinZara – Hendrra Apr 26 '17 at 19:23
-
Yes, $f(2)$ must be 1, but that's because of the second requirement $f(2) = f(f(1))=1$; with only the first requirement, you could have had $f(2) = 3$. – Catalin Zara Apr 26 '17 at 19:25
1 Answers
2
Any permutation is a (unique) product of cycles that commute with each other. Since you want $f^2=id$, the only cycles allowed are transpositions. Since you want $f(i)\ne i$, all elements should appear in one transposition.
This requires taking the elements in pairs. As the number of elements, 55, is odd, there will always be an element missing; any $f$ with $f^2=\text{id}$ has a fixed point. Thus, no such $f$ exists.
When the number of elements is even, say $2n$ the pairing is obviously possible. The number of such pairings is given by $$ \frac{(2n)!}{2^n\,n!}. $$ For $f^3=\text{id}$, one would have to work with triples instead of pairs: the only cycles that are allowable are triples. So the problem becomes in how many way you can divide your elements in groups of $3$. Of course if you still what $f$ with no fixed elements (which is good, because otherwise the combinatorics become more complicated), then you need the number to be a multiple of $3$, say $3n$, and the number of possible $f$ will be $$ \frac{2^n(3n)!}{3^n\,n!}. $$ The "new" $2^n$ in the numerator accounts for the fact that for every group of 3 elements there are two possible 3-cycles.
Martin Argerami
- 205,756
-
Thank you! That's quite an interesting solution and it's very helpful. – Hendrra Apr 26 '17 at 19:23
-
That means that we need an even numbers of elements? What if the second requirement would be a bit different: $f\circ f \circ f = id$? – Hendrra Apr 26 '17 at 19:25
-
-
@MartinArgerami: you may want to emphasize that for any group of three elements, there are two cycles that meet the condition $f^{3} = id$. – Catalin Zara Apr 26 '17 at 20:13
-
@CatalinZara: absolutely. So, do you agree that we need a further $2^n$ factor in the numerator, to account for the possible choices of $3$-cycles for each triple? – Martin Argerami Apr 26 '17 at 21:25