Return to Answer

From these two kinds of moves we see that if there are fewer cycles of length $j$ than of length $j+1$, then either $j+1$ is d , the maximal cycle length, and there is one such cycle of that length, or else we have a move to optimize this configuration. We also have the counts for any three successive lengths present in the structure s-1,r, and t-1 the relation $r(r-1) \leq st$, otherwise we have an optimizing move to make. In particular, s-r cannot be smaller than r-t-1. Also, if there is a gap (a single cycle of maximal length d and none of length d-1), then the move c d to c+1,.d-1 optimizes if the exponents on c and c+1 differ enough (if s/t+1 is greater than (cd +d-c-1)/cd), so one gets a tighter relationship on the exponents with a gap present.

From these two kinds of moves we see that if there are fewer cycles of length $j$ than of length $j+1$, then either $j+1$ is d , the maximal cycle length, and there is one such cycle of that length, or else we have a move to optimize this configuration. We also have the counts for any three successive lengths present in the structure s-1,r, and t-1 the relation $r(r-1) \leq st$, otherwise we have an optimizing move to make. In particular, s-r cannot be smaller than r-t-1. Also, if there is a gap (a single cycle of maximal length d and none of length d-1), then the move c d to c+1,.d-1 optimizes if the exponents on c and c+1 differ enough (if s/t+1 is greater than (cd +d-c-1)/cd), so one gets a tighter relationship on the exponents with a gap present. If the gap is large enough, and s is the smallest cycle not present, then 1^s d can be replaced by 1^(s-1)s(d-s+1), which gives more bounds on the exponents.

For k = 3, we must have the lengths be 1,2, and d, otherwise we have a nonoptimal structure. Suppose d is greater than 4. We can replace 2,d by 3,d-1 and if there are two or more 2-cycles, this is an optimizing move.if there is only one 2-cycle, then we can do 1,d to 2,d-1 , and this is an optimizing move if there are 4 or more 1-cycles. So for d 5 or greater, the only possible optimal cycle structure with three cycle lengths are 1112d and 112d and 12d.

For k = 3, we must have the lengths be 1,2, and d, otherwise we have a nonoptimal structure. Suppose d is greater than 4. We can replace 2,d by 3,d-1 and if there are two or more 2-cycles, this is an optimizing move.if there is only one 2-cycle, then we can do 1,d to 2,d-1 , and this is an optimizing move if there are 4 or more 1-cycles. So for d 5 or greater, the only possible optimal cycle structure with three cycle lengths are 1112d and 112d and 12d. For large d, 1112d is less optimal than 1123(d-2).

For the case of replacing c d by c-1, d+1, where there are $r \gt 0$ many cycles of maximal length $d \lt c \lt 1$, $s$ many cycles of length c, and $t-1$ many cycles of length c-1 before replacement, we get a) cd replaced by cd + c-d-1, b) a reduction by r of one factorial term, and c) a change of t/s in the terms induced by moving the cycle of length $c$. This is a reduction whenever $t \leq rs$.

From these two kinds of moves we see that if there are fewer cycles of length $j$ than of length $j+1$, then either $j+1$ is d , the maximal cycle length, and there is one such cycle of that length, or else we have a move to optimize this configuration. We also have the counts for any three successive lengths present in the structure s-1,r, and t-1 the relation $r(r-1) \leq st$, otherwise we have an optimizing move to make. In particular, s-r cannot be smaller than r-t-1.

For the case of replacing c d by c-1, d+1, where there are $r \gt 0$ many cycles of maximal length $d \gt c \gt 1$, $s$ many cycles of length c, and $t-1$ many cycles of length c-1 before replacement, we get a) cd replaced by cd + c-d-1, b) a reduction by r of one factorial term, and c) a change of t/s in the terms induced by moving the cycle of length $c$. This is a reduction whenever $t \leq rs$.

From these two kinds of moves we see that if there are fewer cycles of length $j$ than of length $j+1$, then either $j+1$ is d , the maximal cycle length, and there is one such cycle of that length, or else we have a move to optimize this configuration. We also have the counts for any three successive lengths present in the structure s-1,r, and t-1 the relation $r(r-1) \leq st$, otherwise we have an optimizing move to make. In particular, s-r cannot be smaller than r-t-1. Also, if there is a gap (a single cycle of maximal length d and none of length d-1), then the move c d to c+1,.d-1 optimizes if the exponents on c and c+1 differ enough (if s/t+1 is greater than (cd +d-c-1)/cd), so one gets a tighter relationship on the exponents with a gap present.