I am trying to compute the number(adsbygoogle = window.adsbygoogle || []).push({});

[tex]\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)[/tex]

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 [itex]i\neq j[/itex]. 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 ([itex]k\neq i[/itex]), 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 ([itex]l\neq j[/itex]) 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 ([itex]k\neq i,j[/itex]), g(j)=l, g(l)=g(j) ([itex]l\neq i,j[/itex]), and there are (n-2)(n-3)(n-4)!=(n-2)! of them.

So in total, for (i,j), [itex]i\neq j[/itex] 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 ([itex]k\neq i[/itex]) 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 [itex]i\neq j[/itex] and n ways to choosing i, I conclude that

[tex]\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![/tex]

I have reasons to believe that the correct answer is 8n!. Can anyone see which case I've missed?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Simple combinatorial problem

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**