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

[David Wilson]

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!)

For example, let P = {3x1, 2x2, 1x3} = {3 2 2 1 1 1} be a partition of n = 10. Then

	m(P) = 10! / ((3^1 * 1!) * (2^2 * 2!) * (1^3 * 3!)) = 25200.

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).

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.

Perhaps I am confused about the correct order of elements in this sequence, but if I am correct, I would like to edit this sequence, fix the elements, and provide a b-file. Could someone verify or refute my findings?

A = n
B = my computed values of A036039(n)
C = published value of A036039(n)
D = sum of partition used to calculate B
D = partition used to calculate B

A    B    C    D    E
1    1    1    1    {1}

2    1    1    2    {2}
3    1    1    2    {1 1}

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

7    6    6    4    {4}
8    8    8    4    {3 1}
9    3    3    4    {2 2}
10   6    6    4    {2 1 1}
11   1    1    4    {1 1 1 1}

12   24   24   5    {5}
13   30   30   5    {4 1}
14   20   20   5    {3 2}
15   20   20   5    {3 1 1}
16   15   15   5    {2 2 1}
17   10   10   5    {2 1 1 1}
18   1    1    5    {1 1 1 1 1}

19   120  120  6    {6}
20   144  144  6    {5 1}
21   90   90   6    {4 2}
22   90   40   6    {4 1 1}
23   40   90   6    {3 3}
24   120  120  6    {3 2 1}
25   40   15   6    {3 1 1 1}
26   15   40   6    {2 2 2}
27   45   45   6    {2 2 1 1}
28   15   15   6    {2 1 1 1 1}
29   1    1    6    {1 1 1 1 1 1}

30   720  720  7    {7}
31   840  840  7    {6 1}
32   504  504  7    {5 2}
33   504  420  7    {5 1 1}
34   420  504  7    {4 3}
35   630  630  7    {4 2 1}
36   210  280  7    {4 1 1 1}
37   280  210  7    {3 3 1}
38   210  210  7    {3 2 2}
39   420  420  7    {3 2 1 1}
40   70   105  7    {3 1 1 1 1}
41   105  70   7    {2 2 2 1}
42   105  105  7    {2 2 1 1 1}
43   21   21   7    {2 1 1 1 1 1}
44   1    1    7    {1 1 1 1 1 1 1}

45   5040 5040 8    {8}
46   5760 5760 8    {7 1}
47   3360 3360 8    {6 2}
48   3360 2688 8    {6 1 1}
49   2688 1260 8    {5 3}
50   4032 3360 8    {5 2 1}
51   1344 4032 8    {5 1 1 1}
52   1260 3360 8    {4 4}
53   3360 1260 8    {4 3 1}
54   1260 1120 8    {4 2 2}
55   2520 1344 8    {4 2 1 1}
56   420  2520 8    {4 1 1 1 1}
57   1120 1120 8    {3 3 2}
58   1120 1680 8    {3 3 1 1}
59   1680 105  8    {3 2 2 1}
60   1120 420  8    {3 2 1 1 1}
61   112       8    {3 1 1 1 1 1}
62   105       8    {2 2 2 2}
63   420       8    {2 2 2 1 1}
64   210       8    {2 2 1 1 1 1}
65   28        8    {2 1 1 1 1 1 1}
66   1         8    {1 1 1 1 1 1 1 1}