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

[Rob Pratt]

Indeed, dynamic programming works here even without imposing any staircase structure. Let a(n,k,m) denote the minimum product {i = 1 to m} x(i)! subject to sum {i = 1 to m} i * x(i) = n and sum {i = 1 to m} x(i) = k, with x(i) >= 0 for all i. Here, x(i) corresponds to the number of times part i appears in the partition of n into k parts of size at most m.  By conditioning on the value of x(m), we derive the recursion a(n,k,m) = min {xm >= 0} xm! * a(n-m*xm,k-xm,m-1). The desired quantity is a(n,k,n).

> On Apr 12, 2019, at 1:01 PM, Rob Pratt <robert.william.pratt at gmail.com> wrote:
> 
> I have no mathematical proof of optimality, but I used an integer linear programming solver, which implicitly enumerates all possibilities.  If this staircase structure is necessary for optimality, it seems like dynamic programming can be applied.
> 
> But the way, I was able to solve all n and k up to 30 in about 17 seconds.
> 
>> On Apr 12, 2019, at 12:04 PM, William Keith <william.keith at gmail.com> wrote:
>> 
>> On Fri, Apr 12, 2019 at 8:11 AM Rob Pratt <robert.william.pratt at gmail.com>
>> wrote:
>> 
>>> 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
>>> 
>> 
>> Mr. Pratt:
>> 
>>    I agree that this looks like a pretty good candidate.  I do not see
>> any local moves that would increase the number of permutations.  Do you
>> have a proof that this is optimal?  I would be persuadable that it is
>> always the case the frequencies must increase, by at most 1 at a time, as
>> part sizes decrease by 1 at a time, which heavily restricts the set of
>> possible optimal partitions, but I would like to see the argument for that,
>> and what hits optimality?
>> 
>> Cordially,
>> William Keith
>> 
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/