cp's OEIS Frontend

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

In other words, there are no "column rises", where a "column rise" means a pair of adjacent columns where each entry in the left column is strictly less than the adjacent entry in the right column.

This is R(n,k,0) in [Abramson-Promislow].

From Petros Hadjicostas, Sep 09 2019: (Start)

As stated above, in the notation of Abramson and Promislow (1978), we have T(n,k) = R(n, k, t=0).

Let P_k be the set of all lists a = (a_1, a_2, ..., a_k) of integers a_i >= 0, i = 1, ..., k, such that 1*a_1 + 2*a_2 + ... + k*a_k = k; i.e., P_k is the set all integer partitions of k. Then |P_k| = A000041(k).

From Eq. (6), p. 248, in Abramson and Promislow (1978), with t=0, we get T(n,k) = Sum_{a in P_k} (-1)^(k - Sum_{j=1..k} a_j) * (a_1 + a_2 + ... + a_k)!/(a_1! * a_2! * ... * a_k!) * (k! / ((1!)^a_1 * (2!)^a_2 * ... * (k!)^a_k))^n.

The integer partitions of k = 1..10 are listed on pp. 831-832 of Abramowitz and Stegun (1964). We see that, for k = 1..6, the corresponding multinomial coefficients k! / ((1!)^a_1 * (2!)^a_2 * ... * (k!)^a_k) are all distinct; that is, A070289(k) = A000041(k) and A309951(k,s) = A325305(k,s) for s = 0..A000041(k). For 7 <= k <= 10, this is not true anymore; i.e., A070289(k) < A000041(k) for 7 <= k <= 10 (and we conjecture that this is the case for all k >= 7).

From the theory of difference equations, we see that Abramson and Promislow's Eq. (6) on p. 248 (with t=0) implies that Sum_{s = 0..A070289(k)} (-1)^s * A325305(k,s) * T(n-s,k) = 0 for n >= A070289(k) + 1. For k = 1..5, these recurrences give R. H. Hardin's empirical recurrences shown in the Formula section below.

We also have Sum_{s = 0..A000041(k)} (-1)^s * A309951(k,s) * T(n-s,k) = 0 for n >= A000041(k) + 1, but for k >= 7, the recurrence we get (for column k) may not necessarily be minimal.

To derive the recurrence for row n, let y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978). We get 1 + Sum_{k >= 1} T(n,k)*x^k/(k!)^n = 1/f_n(-x), where f_n(x) = Sum_{i >= 0} (x^i/(i!)^n). Matching coefficients, we get Sum_{s = 1..k} T(n,s) * (-1)^(s-1) * binomial(k,s)^n = 1, from which the recurrence in the Formula section follows.

(End)

Column 5 of A212855.

From Petros Hadjicostas, Sep 06 2019: (Start)

Let P_5 be the set of all lists b = (b_1, b_2, b_3, b_4, b_5) of integers b_i >= 0, i = 1, ..., 5, such that 1*b_1 + 2*b_2 + 3*b_3 + 4*b_4 + 5*b_5 = 5; i.e., P_5 is the set all integer partitions of 5. Then |P_5| = A000041(5) = 7.

From Eq. (6), p. 248, in Abramson and Promislow (1978), we get a(n) = A212855(n,5) = Sum_{b in P_5} (-1)^(5 - Sum_{j=1..5} b_j) * (b_1 + b_2 + b_3 + b_4 + b_5)!/(b_1! * b_2! * b_3! * b_4! * b_5!) * (5! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5))^n.

The integer partitions of 5 are listed on p. 831 of Abramowitz and Stegun (1964). We see that the corresponding multinomial coefficients 5! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5) are all distinct; that is, A070289(5) = A000041(5) = 7.

Using the integer partitions of 5 and the above formula for a(n), we may derive R. J. Mathar's formula below.

(End)

Column 6 of A212855.

From Petros Hadjicostas, Sep 08 2019: (Start)

Let P_6 be the set of all lists b = (b_1, b_2, b_3, b_4, b_5, b_6) of integers b_i >= 0, i = 1, ..., 6, such that 1*b_1 + 2*b_2 + 3*b_3 + 4*b_4 + 5*b_5 + 6*b_6 = 6; i.e., P_6 is the set all integer partitions of 6. Then |P_6| = A000041(6) = 11.

From Eq. (6), p. 248, in Abramson and Promislow (1978), with t=0, we get a(n) = A212855(n,6) = Sum_{b in P_6} (-1)^(6-Sum_{j=1..6} b_j) * (b_1 + b_2 + b_3 + b_4 + b_5 + b_6)!/(b_1! * b_2! * b_3! * b_4! * b_5! * b_6!) * (6! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5 * (6!)^b_6))^n.

The integer partitions of 6 are listed on p. 831 of Abramowitz and Stegun (1964). We see that the corresponding multinomial coefficients 6! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5 * (6!)^b_6) are all distinct; that is, A070289(6) = A000041(6) = 11 and A309951(6,s) = A325305(6,s) for s = 0..11. (Compare with the comments for A212854.)

Using the information about partitions of 6 in Eq. (6) (with t=0), p. 248, of Abramson and Promislow (1978), we may derive the explicit equation for a(n) shown below.

Using standard results from the theory of difference equations (since the solution is known explicitly), we may derive R. H. Hardin's empirical recurrence. The recurrence is equivalent to Sum_{s = 0..11} (-1)^s * A325305(6,s) * a(n-s) = 0 for n >= 12.

(End)

From Petros Hadjicostas, Aug 25 2019: (Start)

We have a(m) = R(m,n=7,t=0) = A212855(m,7) for m >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).

Let P_7 be the set of all lists b = (b_1, b_2,..., b_7) of integers b_i >= 0, i = 1, ..., 7 such that 1*b_1 + 2*b_2 + ... + 7*b_7 = 7; i.e., P_7 is the set all integer partitions of 7. Then |P_7| = A000041(7) = 15.

We have a(m) = A212855(m,7) = Sum_{b in P_7} (-1)^(7 - Sum_{j=1..7} b_j) * (b_1 + b_2 + ... + b_7)!/(b_1! * b_2! * ... * b_7!) * (7! / ((1!)^b_1 * (2!)^b_2 * ... * (7!)^b_7))^m.

The integer partitions of 7 are listed on p. 831 of Abramowitz and Stegun (1964). We see that, when (b_1, b_2, ..., b_7) = (0, 2, 1, 0, 0, 0, 0) or (3, 0, 0, 1, 0, 0, 0) (i.e., we have the partitions 2+2+3 and 1+1+1+4), the corresponding multinomial coefficients are 210 = 7!/(2!2!3!) = 7!/(1!1!1!4!), so the number of terms in the expression for a(m) is |P_7| - 1 = 15 - 1 = 14 (see below in the Formula section).

Let M_7 := [1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040] be the A070289(7) = 15 - 1 = 14 distinct multinomial coefficients corresponding to the 15 integer partitions of 7 in P_7. The characteristic equation of the recurrence for a(m) is f(x) := Product_{r in M_7} (x-r) = Sum_{i = 0..14} (-1)^{14-i} * c_i * x^i. It turns out that c_{14} = 1, c_{13} = 11271, c_{12} = 46169368, c_{11} = 92088653622, and so on (see R. H. Hardin's recurrence below), and c_0 = 2372695722072874920960000000000 = product of elements in M_7.

It follows that a(m) satisfies the recurrence Sum_{i = 0..14} (-1)^{14-i} * c_i * a(m-i) = 0, which is equivalent to R. H. Hardin's empirical recurrence below.

If we count the multinomial coefficient 210 twice in the characteristic equation (since it corresponds to two different integer partitions of 7) then we get (x-210)*f(x) = Sum_{i = 0..15} (-1)^{15-i} * d_i * x^i, where (d_0, d_1, ..., d_15) is row k = 7 in irregular triangular array A309951. We have d_{15} = 1, d_{14} = 11481, ..., d_0 = 498266101635303733401600000000000 (see Alois P. Heinz's b-file for A309951 with entries 37 to 52). Note that d_0 = 210 * c_0.

We then have Sum_{s = 0..15} (-1)^s * A309951(7, s) * a(m-s) = 0 for m >= 16. The latter recurrence is of order 15, and it is not minimal (as opposed to the one below by R. H. Hardin, which is of order 14 and minimal).

(End)

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.

A column rise in a matrix M = (m_{i,j}) is a value of j such that m_{i,j} < m_{i,j+1} for all i = 1..n.

From Petros Hadjicostas, Aug 26 2019: (Start)

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 b = (b_1, b_2,..., b_n) of integers b_i >= 0, i = 1,..., n, such that 1*b_1 + 2*b_2 + ... + n*b_n = n; i.e., P_n is the set all integer partitions of n. Then |P_n| = A000041(n) for n >= 0.

We have a(n) = R(n,n) = A212855(n,n) = Sum_{b in P_n} (-1)^(n - Sum_{j=1..n} b_j) * (b_1 + b_2 + ... + b_n)!/(b_1! * b_2! * ... * b_n!) * (n! / ((1!)^b_1 * (2!)^b_2 * ... * (n!)^b_n)^n.

(End)

Frequency of the most common number in row n of A036038 (for n >= 1) or A078760.

The sequence is nondecreasing, because a set of partitions of n-1 with a common multinomial coefficient can be extended to a set of partitions of n with a common multinomial coefficient by adding a unit part to each partition. It appears that a(n) > a(n-1) for n >= 28.

The sequence is unbounded. To see this, note that the sets of parts (1,1,1,4) and (2,2,3) of a partition can be exchanged without affecting the value of the multinomial coefficient, because 1+1+1+4 = 2+2+3 and 1!*1!*1!*4! = 2!*2!*3!. In particular, a((7*k)!/24^k) >= k+1 from the partitions 7*k = (3*j)*1 + j*4 + (2*(k-j))*2 + (k-j)*3 for 0 <= j <= k.

Differs from A036038 after a(37). To illustrate where the difference comes from, consider 4,1,1,1 and 3,2,2 are two different partitions of 7 having the same value of multinomial coefficient M(n)=n!/(m1!*m2!*...*mk!)=210.

There is no known formula for M(n) sequence, however the asymptotic behavior has been studied, see the paper by Andrews, Knopfmacher, and Zimmermann.

The number of terms per row (for each value of n starting with n=1) forms sequence A070289.

Differs from A026820 first at T(7,4).

Differs from A213008 first at T(8,3).