[seqfan] Re: gf's for partitions into finite number of elements

[Olivier Gerard]

On Sun, 4 Dec 2016 at 07:34 David Wilson <davidwwilson at comcast.net> wrote:

Following Olivier Gerard's lead, I looked into A036039.

The comments are rather abstruse, or perhaps I am rather obtuse, but I was
able to find nothing to help me understand and compute values. The example
for the sequence just gives a layout of the table, it does not show how to
compute sample terms.

I was able to analyze the Sage program, and simplify the logic, and from
that obtain a definition of multinomial coefficient as a function of a
partition.

Let P = {a1xc1 a2xc2 ... akxck} be a partition of n into positive integers
(that is P is a multiset of positive integers with sum n). Then the
multinomial coefficient of P is

        m(P) = n! / PROD(1 <= i <= k; ai^ci * ci!)


That's a good way to put it for partitions of integers.


I don't know a combinatoric interpretation of m(P), but for small n, the
sum of m(P) over all partitions P of n is n!, which makes me think my
calculations are correct, and that m(P) may have application to counting
permutations (perhaps the permutations of {1..n} for which P gives the
lengths of increasing runs).


It counts permutations according to cycle length structure


If I compute the multinomial coefficients of permutations in reverse
lexicographic order per sum, the results agree with the published elements
of A036039 for many initial elements, but eventually disagree. The table
below (better viewed in fixed width font) compares my values to the
published A036039 values. The disagreements seem to be in the order of
elements.


You guessed right.  You computed the coefficient ordered by decreasing
value of the greatest part, etc., the default ordering in software such as
Mathematica. Example for n=6.

{{6},{5,1},{4,2},{4,1,1},{3,3},{3,2,1},{3,1,1,1},{2,2,2},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1}}

the triangle was computed by ordering the partitions by length then by
decreasing value of the greatest part, as in Abramowitz and Stegun, the
original reference for this sequence. Example for n=6.

{{6},{5,1},{4,2},{3,3},{4,1,1},{3,2,1},{2,2,2},{3,1,1,1},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1}}

I think we need both versions in the OEIS. I will add the necessary
details in A036039 and create a new sequence (A279038) with the other
ordering.


Olivier