[seqfan] Re: Given any partition of n into k parts, what's the maximum permutations of parts

[William Keith]

Hans:

     It seems that my last letter went to you personally instead of the
list, so I am reposting it here for the benefit of any list members
interested.  I also have an additional comment, for which please see the
bottom.

     Unfortunately CDF Player is strictly a reader, and will not allow you
to manipulate the notebook.

     Looking back at your first post, I see that you did indeed have a
similar idea.  I think it gets you pretty close to a global maximum.  This
is hopefully very good news, even though there is a negative answer to your
later question.   Before I get in to that, I have a counterexample to your
suggestion of a minimal denominator for 512 into 64 parts: take 1-16 three
times, then add 1-13, 10, 1, and 2.  You get a denominator of 5!^3 4!^10
3!^3, and with some cancellation you can see that this is smaller than your
proposed 5!^3 4!^12 1!.

     A somewhat more complex alteration to "1-15 four times, plus
(1,2,3,26)" would be to reduce 26 by 6 to 20, and put the six points thus
removed on the 15s, increasing (...14,14,14,14,15,15,15,15,26) to
(...,14,14,14,14,15,16,17,18,20) and cutting another 4! from the
denominator.  Finally, reduce 20 to 19 and increase a 14 to 15, getting
(...,14,14,14,15,15,16,17,18,19).  This drops a 4! to a 3! and increases a
1! to a 2!, for a net change of 2/4.

     To guarantee the true maximum without computing all possible
partitions would probably require rigorous proof that some particular form
of partition was the best possible among all partitions.  One usual means
of proving this would be to take a proposed formula and show that one could
get from it to any other possible partition of n with the required number
of parts by a series of "moves" that always decreased the number of
permutations or kept it the same.  A tweaked variant of your formula might
work for this.  The good news is that for many applications, it suffices to
find a lower bound on the maximum, and I think your proposed form, possibly
with a bit of tweaking as described above, provides a pretty good estimate.

     I note that you can make one restriction on the search space
immediately. I can guarantee that any two consecutive parts in the maximal
partition differ by no more than 2 at any step, and in fact differ by no
more than 1 at any step *unless* both are unique.  Suppose parts occur
(...,x,y,...) with y>x+1.  Then alter this to the partition
(...,x+1,y-1,...).  This is still a valid partition.  If x and y differed
by at least 3, then these are two new, unique parts, and so the new
partition has more permutations (if there were any other x and y) or the
same number (if x and y were already unique).  If y = x+2, you have created
2 of a new part, and as long as there were at least two of x or two of y,
then this does not decrease the number of permutations.

     By examination of the set of such possible "moves," you might be able
to establish that some proposed form of partition is optimal according to
the desired criterion.

Best,
William Keith