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

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

Author

Petros Hadjicostas, Sep 05 2019

Keywords

• nonn
• tabf

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

Examples

			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.
		

Links

• Alois P. Heinz, Rows n = 0..15, flattened
• 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.
• Wikipedia, Partition (number theory).

Crossrefs

Cf. A000012 (column k=0), A000041, A005651, A070289, A212850, A212851, A212852, A212853, A212854, A212855, A212856, A309951, A309972, A325308 (column k=1).

Programs

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

Formula

Sum_{k=0..A070289(n)} (-1)^k * T(n,k) = 0.