login
A325305
Irregular triangular array, read by rows: T(n,k) is the sum of the products of distinct multinomial coefficients (n_1 + n_2 + n_3 + ...)!/(n_1! * n_2! * n_3! * ...) taken k at a time, where (n_1, n_2, n_3, ...) runs over all integer partitions of n (n >= 0, 0 <= k <= A070289(n)).
8
1, 1, 1, 1, 1, 3, 2, 1, 10, 27, 18, 1, 47, 718, 4416, 10656, 6912, 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000, 1, 1602, 929171, 260888070, 39883405500, 3492052425000, 177328940580000, 5153150631600000, 82577533320000000, 669410956800000000, 2224399449600000000, 1632586752000000000, 1, 11271
OFFSET
0,6
COMMENTS
This array was inspired by R. H. Hardin's recurrences for the columns of array A212855. Row n has length A070289(n) + 1.
This array differs from array A309951 starting at row n = 7. Array A309951 calculates a similar sum of products of multinomial coefficients, but the multinomial coefficients do not have to be distinct. Row n of array A309951 has length A000041(n) + 1, i.e., one more than the number of partitions of n.
Let P_n be the set of all lists a = (a_1, a_2,..., a_n) of integers a_i >= 0, i = 1,..., n such that 1*a_1 + 2*a_2 + ... + n*a_n = n; i.e., P_n is the set all integer partitions of n. (We use a different notation for partitions than the one in the name of T(n,k).) Then |P_n| = A000041(n) for n >= 0.
For n = 1..6, all the multinomial coefficients n!/((1!)^a_1 * (2!)^a_2 * ... * (n!)^a^n) corresponding to lists (a_1,...,a_n) in P_n are distinct; that is, A000041(n) = A070289(n) for n = 1..6.
For n = 7, the partitions (a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (0, 2, 1, 0, 0, 0, 0) (i.e., 2 + 2 + 3) and (a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (3, 0, 0, 1, 0, 0, 0) (i.e., 1 + 1 + 1 + 4) give the same multinomial coefficient: 210 = 7!/(2!2!3!) = 7!/(1!1!1!4!). Hence, A000041(7) > A070289(7).
Looking at the multinomial coefficients of the integer partitions of n = 8, 9, 10 on pp. 831-832 of Abramowitz and Stegun (1964), we see that, even in these cases, we have A000041(n) > A070289(n).
LINKS
Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (6), p. 248.
FORMULA
Sum_{k=0..A070289(n)} (-1)^k * T(n,k) = 0.
EXAMPLE
Triangle begins as follows:
[n=0]: 1, 1;
[n=1]: 1, 1;
[n=2]: 1, 3, 2;
[n=3]: 1, 10, 27, 18;
[n=4]: 1, 47, 718, 4416, 10656, 6912;
[n=5]: 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000;
...
For example, when n = 3, the integer partitions of 3 are 3, 1+2, 1+1+1, and the corresponding multinomial coefficients are 3!/3! = 1, 3!/(1!2!) = 3, and 3!/(1!1!1!) = 6. They are all distinct. Then T(n=3, k=0) = 1, T(n=3, k=1) = 1 + 3 + 6 = 10, T(n=3, k=2) = 1*3 + 1*6 + 3*6 = 27, and T(n=3, k=3) = 1*3*6 = 18.
Consider the list [1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040] of the A070289(7) = 15 - 1 = 14 distinct multinomial coefficients corresponding to the 15 integer partitions of 7. Then T(7,0) = 1, T(7,1) = 11271 (sum of the coefficients), T(7,2) = 46169368 (sum of products of every two different coefficients), T(7,3) = 92088653622 (sum of products of every three different coefficients), and so on. Finally, T(7,14) = 2372695722072874920960000000000 = product of these coefficients.
MAPLE
g:= proc(n, i) option remember; `if`(n=0 or i=1, [n!], [{map(x->
binomial(n, i)*x, g(n-i, min(n-i, i)))[], g(n, i-1)[]}[]])
end:
b:= proc(n, m) option remember; `if`(n=0, 1,
expand(b(n-1, m)*(g(m$2)[n]*x+1)))
end:
T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(nops(g(n$2)), n)):
seq(T(n), n=0..7); # Alois P. Heinz, Sep 05 2019
MATHEMATICA
g[n_, i_] := g[n, i] = If[n == 0 || i == 1, {n!}, Union[Map[Function[x, Binomial[n, i] x], g[n - i, Min[n - i, i]]], g[n, i - 1]]];
b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m] (g[m, m][[n]] x + 1)];
T[n_] := CoefficientList[b[Length[g[n, n]], n], x];
T /@ Range[0, 7] // Flatten (* Jean-François Alcover, May 06 2020, after Maple *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Petros Hadjicostas, Sep 05 2019
STATUS
approved