Return to Answer

(2,m+2)

(2,m)

(m+2)

(2,m+2)

If m = 1 or 2, the problem is 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.

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.

(2,m)

(m+2)

(2,m+2)

(m+4)

then n-1.

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.

(2,m+2)

(m+4)

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.

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.