cp's OEIS Frontend

This is the total number of hierarchies of n labeled elements arranged on 1 to n levels. A distribution of elements onto levels is "hierarchical" if a level l+1 contains <= elements than level l. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed. See also A140585. Examples: Let the colon ":" separate two consecutive levels l and l+1. Then n=2 --> 3: {1}{2}, {1}:{2}, {2}:{1}, n=3 --> 10: {1}{2}{3}, {1}{2}:{3}, {3}{1}:{2}, {2}{3}:{1}, {1}:{2}:{3}, {3}:{1}:{2}, {2}:{3}:{1}, {1}:{3}:{2}, {2}:{1}:{3}, {3}:{2}:{1}. - Thomas Wieder, May 17 2008

n identical objects are painted by dipping them into a long row of cans of paint of distinct colors. Begining with the first can and not skipping any cans k, 1<=k<=n, objects are dipped (painted) and not more objects are dipped into any subsequent can than were dipped into the previous can. The painted objects are then linearly ordered. - Geoffrey Critzer, Jun 08 2009

a(n) is the number of partitions of n where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur exactly once in the partition. a(3) = 10: 3abc, 2ab1c, 2ac1b, 2bc1a, 1a1b1c, 1a1c1b, 1b1a1c, 1b1c1a, 1c1a1b, 1c1b1a. - Alois P. Heinz, Aug 30 2015

Also the number of ordered set partitions of {1,...,n} with weakly decreasing block sizes. - Gus Wiseman, Sep 03 2018

The parity of a(n) is that of A000110(A000120(n)), so a(n) is even if and only if A000120(n) == 2 (mod 3). - Álvar Ibeas, Aug 11 2020

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)

From Petros Hadjicostas, Aug 25 2019: (Start)

Both formulas below follow from the theory in the documentation of array A309951. We have Sum_{s = 0..A000041(3)} (-1)^s * A309951(3,s) * a(n-s) = 0, i.e., a(n) - 10*a(n-1) - 27*a(n-2) + 18*a(n-3) = 0 for n >= 4. This is a consequence of Eq. (6) on p. 248 of Abramson and Promislow (1978), where we let t=0 in the equation.

In the explicit formula by Vaclav Kotesovec below, a(n) = 6^n - 2*3^n + 1^n, the numbers 1, 3, 6 (that are raised to the n-th power) are the multinomial coefficients of the A000041(3) = 3 integer partitions of 3: 1 = 3!/3!, 3 = 3!/(1!2!), 6 = 3!/(1!1!1!).

(End)

Column 4 of A212855.

From Petros Hadjicostas, Aug 25 2019: (Start)

All formulas below follow from the theory in the documentation of array A309951.

We have Sum_{s = 0..A000041(4)} (-1)^s * A309951(4,s) * a(n-s) = 0, i.e., a(n) - 47*a(n-1) + 718*a(n-2) - 4416*a(n-3) + 10656*a(n-4) - 6912*a(n-5) = 0 for n >= 6. This is a consequence of Eq. (6) on p. 248 of Abramson and Promislow (1978).

Note that in R. J. Mathar's formula a(n) = 24^n + 6^n - 3*12^n + 2*4^n - 1^n, the numbers 1, 4, 12, 6, and 24 (that are raised to the n-th power) are the multinomial coefficients of the A000041(4) = 5 integer partitions of 4: 4!/4! = 1, 4!/(1!3!) = 4, 12 = 4!/(1!1!2!), 6 = 4!/(2!2!), 24 = 4!/(1!1!1!1!).

Note also that these numbers appear also in the denominator of the Colin Barker's g.f.: (1 - x)*(1 - 4*x)*(1 - 6*x)*(1 - 12*x)*(1 - 24*x) = 1 - 47*x + 718*x^2 - 4416*x^3 + 10656*x^4 - 6912*x^5. (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. 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).

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)