Really guys, local optimization is the way to go, or at least to start. By analyzing those cycle patterns which are resistant to being optimized, you can get a lot of information, and reduce the search space dramatically. I said this in comments and another post; this post shows it in action using the move c d goes to c-1,d+1, and occasional variations on this move. Here c and d are integers representing cycle lengths with c at most d. Often, but not always, it will be useful to choose d to be the maximal length present in a given cycle structure.

Let's start with r many cycles of length d, where r is greater than one. If d is 1, we can't do the move. If d is greater than one, the denominator is affected by a) replacing d^2 by (d^2-1), b) reducing a factorial term by r(r-1), and c) increasing two other factorial terms representing cycle counts for lengths d+1 and d-1, which we will call an increase by a factor of st.

Before we break it down to cases, we see that this move says something about a cycle structure: if this move doesn't optimize it, then either it has not many cycles of length greater than 1, or it does, but for every cycle length d greater than 1 which has two or more cycles, there is a relationship almost harmonic in nature, represented by the exponents (a_j) given by the relationship $st\geq r(r-1)$. In particular, for cycle lengths j-1,j, and j+1, if the counts for j-1 and j+1 are both at least two less than the count for j, this move optimizes (replaces this configuration with another with smaller denominator). More particularly, any configuration with $ r\gt 1$ cycles of length $j \gt 1$ and at most one cycle having a length from { j+1,j -1} is nonoptimal (0,2,1 and 1,2,0 and similar can't appear as consecutive subsequences can't appear in an optimal cycle structure).

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. 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.

Now suppose we have a cycle structure with k many distinct cycle lengths. We assume the structure has more than 1 cycle.

If k is 1, then the cycle lengths must all be 1, otherwise the structure is non optimal. This is the case m=n in the notation of the problem with cycle structure 1^n.

If k is two, then one of the lengths must be 1, otherwise we have a nontrivial configuration. If the other length is greater than 2, there can be only one cycle of that length, and by reversing the move c-1,d+1 to c,d, we have a nonoptimal structure if there are at least three 1-cycles. So one potentially optimal structure with only two lengths is 11(n-2): this works when n is 4 or 5. For larger n this is beaten by the structure with three lengths 12(n-3).

If k is two and the longest cycle present is length 2, this is optimal unless there are r 2-cycles and s-1 1-cycles and r(r-1) is at least 3s/4, in which case turning two of the 2-cycles into a 1-cycle and a three cycle gives a possibly more optimal structure. So for two cycle lengths, we either have 1(n-1), 113, or 1^(s-1)2^r with 4r(r-1) at most 3s. Indeed, trying to improve upon this configuration for n=2r+s-1 by replacing 2-cycles by a j cycle and j 1-cycles gives a less optimal configuration since s+i is greater than 2(r-i).

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).

If d is 4 and there are 3 or more 2-cycles or 5 or more 1-cycles, we can do a c 4 to c+1 3 optimizing move. Otherwise 1^s2^r4 is a potential optimum for s at most 4 and r at most 2.

Finally assume d is 3, and the structure to study is 1^s2^r3^t. Assume r and t large enough when needed. The moves to investigate are 3 3 to 2 4, 2 3 to 1 4, and 2 2 to 1 3 and the reverse move. These involve comparing 9t(t-1) to 8(r+1), 6rt to 4(s+1), and 4r(r-1) to 3(s+1)(t+1). One needs to run the calculations for a specific triple s,r,t, but if t is roughly bigger than square root of r, then the structure is nonoptimal, and if r is bigger than a fractional power ( compute it, but use 3/5 for an initial guess) of s, the structure is non optimal.

As pointed out before, one expects a decrease in exponents of a harmonic type (to counter moves like j j to j-1 j+1) as cycle length increases and with a largest cycle there can be only one gap in the list of cycle lengths, and if there is a gap then there is one largest cycle. When k gets larger, if there is a gap of length two or greater between second largest and largest cycle lengths, sometimes a move from c d to c+1 to d-1 can optimize, so usually the second largest cycle length has exponent one in an optimal structure, and one can say more about the sequence of exponents for smaller cycle lengths.

Gerhard "One Move At A Time" Paseman, 2019.06.23.