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

[Hans L]

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