OFFSET
0,6
COMMENTS
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.
LINKS
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).
FORMULA
Sum_{k=0..A000041(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. 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.
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, Aug 25 2019
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Petros Hadjicostas, Aug 25 2019
STATUS
approved