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

[Rob Pratt]

If I understand the problem correctly, an optimal partition for n = 512, k = 64 is as follows (in frequency representation form):
1^7 2^6 3^6 4^5 5^4 6^4 7^4 8^3 9^3 10^3 11^2 12^2 13^2 14^2 15^2 16^2 17^1 18^1 19^1 20^1 21^1 22^1 23^1

> On Apr 11, 2019, at 11:10 AM, William Keith <william.keith at gmail.com> wrote:
> 
> 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
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/