It's not hard to count the number of permutations in a given conjugacy class of Sn. In particular, the number of permutations in Sn whose cycle decomposition has ci i-cycles is n!/(Πi=1n ci!ici). It's also not too hard to see that this is maximized for the conjugacy class that leaves one element fixed and permutes the others in an (n-1)-cycle, and that this is *strictly* the maximum when n ≥ 3.


What I'm looking for is an "injective proof" of this fact. Namely, a set of injections from the other conjugacy classes into the set of (n-1)-cycles. Ideally you should be able to define a single nice function from Sn into these cycles, which is injective but not surjective (for n ≥ 3) when restricted to every other conjugacy class.



Injective proof about sizes of conjugacy classes in S_n
For any cycle decomposition, we can uniquely order the cycles from smallest length to largest length, breaking ties between cycles of the same length in some fixed arbitrary way (say by maximal elements). Let us do this for concreteness.


Suppose there was an (injective) way to "join" and A-cycle and a B-cycle together to form an A+B cycle whenever |A| and |B| are > 1. Then, given any cycle decomposition as above, one can start bubbling the two largest cycles together to eventually form a single cycle of some length m.


If m = n - 1, we are done.


If m = n, write S = (1............) and then omit the last term.


If m = 1 the problem is very easy.


If n - 1 > m > 2, there is an injective map from m-cycles to elements whose cycle decomposition is a product of an m-cycle with a 2-cycle. For concreteness, one can add the 2-cycle with the two lowest missing entries. Now bubble again to form an m+2 cycle.


If m = 2, and n is at least 5, bubble with a 3-cycle.


If m = 2 and n = 4 (the last case), form whatever bijection you like between the two sets of 6 elements.


The key point is therefore to find a way to bubble an A-cycle and a B-cycle when |A|,|B| > 1.
We do this as follows.


Amongst the entries of A and B, there is a unique smallest integer, call it X.


Case 1. If X lies in A, Let Z denote the *largest* element of B.
Then one can (uniquely) write A = (X.....) and B = (.....Y,Z), where Y < Z. Then consider the A+B cycle obtained by concatenating A and B in this form, i.e. (X,......,Y,
Z).


Case 2. If X lies in B, let Z denote the *smallest* element of A.
Then one can (uniquely) write B = (X....) and A = (.....,Y,Z), where now Y > Z. 
Then consider the A+B cycle (X,.....,Y,Z).


Given an A+B cycle, one can uniquely write it in the form (X,....,Y,Z), where X is the smallest entry. Then one can break it up into an A-cycle and B-cycle depending on whether Y < Z or Y > Z.




---


Since this was apparently a little confusing, suppose that the cycle lengths of S are
a`_`1 <= a`_`2 <= a`_`3 <= ..... <= a`_`r.
Here I omit the 1-cycle lengths, so a`_`1 > 1, and sum a`_`r = m for some m possibly less than n. Then the cycle lengths of the steps in the algorithm will have lengths:


(a`_`1, ...., a`_`(r-1),a`_`r),


(a`_`1, ...., a`_`(r-2),a`_`(r-1) + a`_`r),


(a`_`1, ...., a`_`(r-3),a`_`(r-2) + a`_`(r-1) + a`_`r),


....


(a`_`1 + a`_`\_2 + ... + a`_`r) = (m)


(2,m)


(m+2)


(2,m+2)


(m+4)


...


(n-1 or n, depending on m mod 2),


then n-1.


(if m = 2 and n is at least 5, then instead it should go


(2) --> (2,3) --> (5) --> (2,5) --> (7) --> (2,7) --> (9) ...,etc.


