A325305 - OEIS

%I #47 May 06 2020 05:00:30

%S 1,1,1,1,1,3,2,1,10,27,18,1,47,718,4416,10656,6912,1,246,20545,751800,

%T 12911500,100380000,304200000,216000000,1,1602,929171,260888070,

%U 39883405500,3492052425000,177328940580000,5153150631600000,82577533320000000,669410956800000000,2224399449600000000,1632586752000000000,1,11271

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

%C This array was inspired by _R. H. Hardin_'s recurrences for the columns of array A212855. Row n has length A070289(n) + 1.

%C 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.

%C 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.

%C 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.

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

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

%H Alois P. Heinz, <a href="/A325305/b325305.txt">Rows n = 0..15, flattened</a>

%H Milton Abramowitz and Irene A. Stegun, <a href="http://www.cs.bham.ac.uk/~aps/research/projects/as/book.php">Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables</a>, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.

%H Morton Abramson and David Promislow, <a href="https://doi.org/10.1016/0097-3165(78)90012-2">Enumeration of arrays by column rises</a>, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (6), p. 248.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>.

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

%e Triangle begins as follows:

%e   [n=0]: 1,   1;

%e   [n=1]: 1,   1;

%e   [n=2]: 1,   3,     2;

%e   [n=3]: 1,  10,    27,     18;

%e   [n=4]: 1,  47,   718,   4416,    10656,      6912;

%e   [n=5]: 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000;

%e   ...

%e 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.

%e 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.

%p g:= proc(n, i) option remember; `if`(n=0 or i=1, [n!], [{map(x->

%p       binomial(n, i)*x, g(n-i, min(n-i, i)))[], g(n, i-1)[]}[]])

%p     end:

%p b:= proc(n, m) option remember; `if`(n=0, 1,

%p       expand(b(n-1, m)*(g(m$2)[n]*x+1)))

%p     end:

%p T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(nops(g(n$2)), n)):

%p seq(T(n), n=0..7);  # _Alois P. Heinz_, Sep 05 2019

%t 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]]];

%t b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m] (g[m, m][[n]] x + 1)];

%t T[n_] := CoefficientList[b[Length[g[n, n]], n], x];

%t T /@ Range[0, 7] // Flatten (* _Jean-François Alcover_, May 06 2020, after Maple *)

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

%K nonn,tabf

%O 0,6

%A _Petros Hadjicostas_, Sep 05 2019