- #1
- 4,796
- 32
I am trying to compute the number
\sum_{g\in S_n}|\mathrm{fix}(g^2)|^2=\sharp\left(\bigsqcup_{g\in S_n}\mathrm{fix}(g^2)\times \mathrm{fix}(g^2)\right)
where S_n is the permutation group on the n elements {1,...n} and where fix(g) = {i in {1,...,n} : g(i)=i}.
So the plan is to fix a pair (i,j) in {1,...n} x {1,...n} and ask how many g's are such that (i,j) belongs to fix(g²) x fix(g²). Then summing over all the possible values of (i,j) gives the desired answer.
I start with (i,j) in {1,...n} x {1,...n} such that i\neq j. How many g's are such that (i,j) belongs to fix(g²) x fix(g²)?
- There are those g's such that g(i)=i, g(j)=j and there are (n-2)! of them.
- There are those g's such that g(i)=k, g(k)=i (k\neq i), g(j)=j and there are (n-2)(n-3)!=(n-2)! of them.
- There are those g's such that g(i)=i, g(j)=l, g(l)=j (l\neq j) and there are (n-2)(n-3)!=(n-2)! of them.
- There are those g's such that g(i)=j, g(j)=i, and there are (n-2)! of them.
- There are those g's such that g(i)=k, g(k)=i (k\neq i,j), g(j)=l, g(l)=g(j) (l\neq i,j), and there are (n-2)(n-3)(n-4)!=(n-2)! of them.
So in total, for (i,j), i\neq j there are 5(n-2)! g's in S_n such that (i,j) is in fix(g²) x fix(g²).
Next, if i in {1,...n} is fixed, how many g's are such that (i,i) is in fix(g²) x fix(g²)?
- There are those g's such that g(i)=i and there are (n-1)! of them.
- There are those g's such that g(i)=k, g(k)=i (k\neq i) and there are (n-1)(n-2)!=(n-2)! of them.
So in total, for each i in {1,...,n}, there are 2(n-1)! g's in S_n such that (i,i) is in fix(g²) x fix(g²).
Since there are n(n-1) ways of choosing (i,j) such that i\neq j and n ways to choosing i, I conclude that
\sum_{g\in S_n}|\mathrm{fix}(g^2)|^2=\sharp\left(\bigsqcup_{g\in S_n}\mathrm{fix}(g^2)\times \mathrm{fix}(g^2)\right) = n(n-1)(5(n-2)!)+n(2(n-1)!)=5n!+2n!=7n!
I have reasons to believe that the correct answer is 8n!. Can anyone see which case I've missed?
\sum_{g\in S_n}|\mathrm{fix}(g^2)|^2=\sharp\left(\bigsqcup_{g\in S_n}\mathrm{fix}(g^2)\times \mathrm{fix}(g^2)\right)
where S_n is the permutation group on the n elements {1,...n} and where fix(g) = {i in {1,...,n} : g(i)=i}.
So the plan is to fix a pair (i,j) in {1,...n} x {1,...n} and ask how many g's are such that (i,j) belongs to fix(g²) x fix(g²). Then summing over all the possible values of (i,j) gives the desired answer.
I start with (i,j) in {1,...n} x {1,...n} such that i\neq j. How many g's are such that (i,j) belongs to fix(g²) x fix(g²)?
- There are those g's such that g(i)=i, g(j)=j and there are (n-2)! of them.
- There are those g's such that g(i)=k, g(k)=i (k\neq i), g(j)=j and there are (n-2)(n-3)!=(n-2)! of them.
- There are those g's such that g(i)=i, g(j)=l, g(l)=j (l\neq j) and there are (n-2)(n-3)!=(n-2)! of them.
- There are those g's such that g(i)=j, g(j)=i, and there are (n-2)! of them.
- There are those g's such that g(i)=k, g(k)=i (k\neq i,j), g(j)=l, g(l)=g(j) (l\neq i,j), and there are (n-2)(n-3)(n-4)!=(n-2)! of them.
So in total, for (i,j), i\neq j there are 5(n-2)! g's in S_n such that (i,j) is in fix(g²) x fix(g²).
Next, if i in {1,...n} is fixed, how many g's are such that (i,i) is in fix(g²) x fix(g²)?
- There are those g's such that g(i)=i and there are (n-1)! of them.
- There are those g's such that g(i)=k, g(k)=i (k\neq i) and there are (n-1)(n-2)!=(n-2)! of them.
So in total, for each i in {1,...,n}, there are 2(n-1)! g's in S_n such that (i,i) is in fix(g²) x fix(g²).
Since there are n(n-1) ways of choosing (i,j) such that i\neq j and n ways to choosing i, I conclude that
\sum_{g\in S_n}|\mathrm{fix}(g^2)|^2=\sharp\left(\bigsqcup_{g\in S_n}\mathrm{fix}(g^2)\times \mathrm{fix}(g^2)\right) = n(n-1)(5(n-2)!)+n(2(n-1)!)=5n!+2n!=7n!
I have reasons to believe that the correct answer is 8n!. Can anyone see which case I've missed?
Last edited:
