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

[Hans L]

Thanks Olivier,

A102462 seems very similar to what I'm asking, but it only tells the
maximum for *any* k.  I am still wanting a triangular table for specific n,k

My interest in this is because it relates directly to some theoretical
bounds for a general data compression algorithm I'm experimenting with.

Jamie,
I took a peek at it and I must admit I'm a bit lost about what that
sequence is representing, but the PARI script works fine for me.  It
calculated up to row(7) without issue.
For higher rows, I had to set parisize (the stack size) progressively
higher but after giving it an absurd amount of stack space it was able to
calculate up to row(10) in a few minutes.


On Thu, Apr 4, 2019 at 5:32 PM Olivier Gerard <olivier.gerard at gmail.com>
wrote:

> 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>