A309972 -id:A309972 - cp's OEIS frontend

A309951 Irregular triangular array, read by rows: T(n,k) is the sum of the products of 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 <= A000041(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, 11481

Offset: 0

Petros Hadjicostas, Aug 25 2019

This array was inspired by R. H. Hardin's recurrences for the columns of array A212855. Rows k=1 to k=5 are due to him, while the remaining rows were computed by Alois P. Heinz.
Row n has length A000041(n) + 1, i.e., one more than the number of partitions of n.
Let R(m,n) := R(m,n,t=0) = A212855(m,n) for m,n >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).
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.
We have R(m,n) = A212855(m,n) = Sum_{a in P_n} (-1)^(n - Sum_{j=1..n} a_j) * (a_1 + a_2 + ... + a_n)!/(a_1! * a_2! * ... * a_n!) * (n! / ((1!)^a_1 * (2!)^a_2 * ... * (n!)^a_n))^m.
The recurrence of R. H. Hardin for column n of array A212855 is Sum_{s = 0..|P_n|} (-1)^s * T(n,s) * R(m-s,n) = 0 for n >= 1 and m >= |P_n| + 1.
The above recurrence is correct for all n >= 1, but it is not always a minimal one. For example, it seems to be the minimal one for n = 1,...,6, but not for n = 7 (see A212854). It seems to be minimal whenever every two different partitions of n give different multinomial coefficients.
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, to find the minimal recurrence for n = 7, we count 210 only once in the set of multinomial coefficients: 1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040. Then the absolute value of the coefficient of a(n-1) in the minimal recurrence is the sum of these multinomial coefficients (i.e., 11271); the absolute value of the coefficient of a(n-2) in the minimal recurrence is the sum of products of every two of them (i.e., 46169368), and so on.
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, the above recurrence is not the minimal one. The number of distinct multinomial coefficients among the integer partitions of n is given by A070289.

			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. 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.
Since |P_3| = A000041(3) = 3, the recurrence of _R. H. Hardin_ for column n = 3 of array A212855 is T(3,0)*R(m,3) - T(3,1)*R(m-1,3) + T(3,2)*R(m-2,3) - T(3,3)*R(m-3,3) = 0; i.e., R(m,3) - 10*R(m-1,3) + 27*R(m-2,3) - 18*R(m-3,3) = 0 for m >= 4. We have the initial conditions R(m=1,3) = 1, R(m=2,3) = 19, and R(m=3,3) = 163. Thus, R(m,3) = 6^m - 2*3^m + 1 = A212850(m) for m >= 1. See the documentation of array A212855.

Alois P. Heinz, Rows n = 0..14, 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, and the comments above.
Wikipedia, Partition (number theory).

Cf. A000012 (column k=0), A000041, A005651 (column k=1), A070289, A212850, A212851, A212852, A212853, A212854, A212855, A212856, A212857, A212858, A212859, A212860.

Rightmost terms in rows give A309972.

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, Aug 25 2019

g[n_, i_] := g[n, i] = If[n==0 || i==1, {n!}, Join[Binomial[n, i]*#& /@ g[n - i, Min[n - i, i]], g[n, i - 1]]];
b[n_, m_] := b[n, m] = If[n==0, 1, Expand[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, Feb 18 2021, after Alois P. Heinz *)

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

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

Original entry on oeis.org

Offset: 0

Petros Hadjicostas, Sep 05 2019

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

			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.

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

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

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

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

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

cp's OEIS Frontend

A309951 Irregular triangular array, read by rows: T(n,k) is the sum of the products of 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 <= A000041(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula