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