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

[Olivier Gerard]

Dear Hans,

Thanks for posting to seqfan.

We have already in the OEIS for instance the sequence of the maximum number
of permutations of a partition of n

A102462: 1, 1, 1, 2, 3, 4, 6, 12, 20, 30, 60, 105, 168, 280, 504, 840,
1512, 2520, 5040, ...

which is based on the multinomial interpretation of this problem. This
interpretation is
very natural as the multinomial coefficient has an original definition as a
number of
permutations of powers of k variables with total degree n.

You will also find the directly related

A007294: Number of partitions of n into nonzero triangular numbers.
1, 1, 1, 2, 2, 2, 4, 4, 4, 6, 7, 7, 10, 11, 11, 15, 17, 17, 22, 24, ...

and a few others, that you can find by using the crossrefs and comments of
these entries.

Regards,

Olivier

On Fri, Apr 5, 2019 at 1:07 AM Hans L <thehans at gmail.com> wrote:

> Hello,
>
> This is my first post to this list, and my background is dominated moreso
> by programming than formal math, so go easy on me.
>
> I'm interested in finding a sort of "worst case" for how many ways a
> partition can be permuted.
>
> As the subject says: For any partition of n into k parts, what is the
> maximum permutations possible on those parts
>
> Another way of stating this might be to find the partition with the least
> number of repeated parts,
> such that the multinomial coefficient of the multiplicities of parts is
> maximized.
>
> First a trivial case: for n==k, the only partition is 1,1,1,..., the parts
> are all the same so there is only 1 permutation.
>
> Another example might be n=10, k=4
> We can use partition 1,2,3,4 which has all distinct parts, giving the upper
> bound of permutations: k! = 4!
> This partition for 10 is equivalent to the triangular number T(4) =
> 1+2+3+4.  So for n >= T(k), then the answer for most permutations is always
> k!
>
> But what about when n < T(k) and n > k ?
>
> I spent some time thinking about this and I believe I have a solution but
> it doesn't look very pretty to me.
>
> If you find the largest value j that satisfies either equation:
> 1) T(k - floor(n/T(j))*j - 1) + j  < (n mod T(j))       OR
> 2) T(k - floor(n/T(j))*j) <= (n mod T(j))
> Where T( ) is the Triangular numbers A000217.
> Also just for brevity below I'll define variable  m = floor(n/T(j))
>
> Then the most permutations is either:
> a) If equation 1 is satisfied then:   k!/(m!^(j-(k-m*j-1)) *
> (m+1)!^(k-m*j-1) )
> b) Otherwise: k!/(m!^(j-(k-m*j)) * (m+1)!^(k-m*j) )
>      (same except no "-1" in the exponents)
>
> An example I tried testing this on was: partition 512 into 64 parts.
> Again we try to use parts in terms of triangular numbers since we want to
> split into as many (minimal) unique parts as possible.
> The largest j that satisfies the equation is j=15, T(15)=120
> So the parts would be (1,2,3,..14,15), repeated m=4 times, followed by
> (1,2,3,26) to get to 512
> Since the after j*m parts, we need 4 more parts to reach k=64, and T(3)+j <
> (n mod T(j)), then our last part (26) can and will be greater than j and
> that keeps our part multiplicities down.
> So the final result has 4 through 15 (12 parts)repeated m=4 times each, and
> 1,2,3 repeated m+1=5 times, then our result is:
> 64! / (4!^12 * 5!^3)
>
> If we instead did n=501, n=64
> then we would need (1..15)*4+ 1,2,3,15
> Since the last part isn't greater than j, we get one less m! term and one
> more (m+1)! term, giving us:
> 64! / (4!^11 * 5!^4)
>
> Does this reasoning make sense to others and can anyone help confirm my
> thoughts that this would always produce the maximum permutations?
>
> Are there existing sequences that define or relate to this phenomenon in a
> more natural/straightforward way?  Could it be restated more clearly as a
> recurrence relation?
>
> Thanks,
> Hans Loeblich
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>