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

a(n) has the Lucas property, namely a(n) is congruent to a(n_0)a(n_1)...a(n_k) modulo p for any prime p where n_0,n_1,... are the base p digits of n. (Carlitz via McIntosh)

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