cp's OEIS Frontend

Sum of pyramid weights of all nondecreasing Dyck paths of semilength n. (A pyramid in a Dyck word (path) is a factor of the form U^h D^h, where U=(1,1), D=(1,-1) and h is the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d. The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids.) Example: a(4) = 46. Indeed, there are 14 Dyck paths of semilength 4. One of them, namely UUDUDDUD is not nondecreasing because the valleys are at heights 1 and 0. The other 13, with the maximal pyramids shown between parentheses, are: (UD)(UD)(UD)(UD), (UD)(UD)(UUDD), (UD)(UUDD)(UD), (UD)U(UD)(UD)D, (UD)(UUUDDD), (UUDD)(UD)(UD), (UUDD)(UUDD), (UUUDDD)(UD), U(UD)(UD)(UD)D, U(UD)(UUDD)D, U(UUDD)(UD)D, UU(UD)(UD)DD and (UUUUDDDD). The pyramid weights of these paths are 4, 4, 4, 3, 4, 4, 4, 4, 3, 3, 3, 2, and 4, respectively. Their sum is 46. a(n) = Sum_{k = 1..n} k*A121462(n, k). - Emeric Deutsch, Jul 31 2006

Number of 1s in all compositions of n, where compositions are understood with two different kinds of 1s, say 1 and 1' (n >= 1). Example: a(2) = 4 because the compositions of 2 are 11, 11', 1'1, 1'1', 2, having a total of 2 + 1 + 1 + 0 + 0 = 4 1s. Also number of k's in all compositions of n + k (k = 2, 3, ...). - Emeric Deutsch, Jul 21 2008

From Petros Hadjicostas, Jun 24 2019: (Start)

If c = (c(m): m >= 1) is the input sequence and b_k = (b_k(n): n >= 1) is the output sequence under the AIK[k] = INVERT[k] transform (see Bower's web link below), then the bivariate g.f. of the list of sequences (b_k: k >= 1) = ((b_k(n): n >= 1): k >= 1) is Sum_{n, k >= 1} b_k(n)*x^n*y^k = y*C(x)/(1 - y*C(x)), where C(x) = Sum_{m >= 1} c(m)*x^m is the g.f. of the input sequence.

Here, b_k(n) is the number of all (linear) compositions of n with k parts where a part of size m is colored with one of c(m) colors. Thus, Sum_{k = 1..n} k*b_k(n) is the total number of parts in all compositions of n.

If we differentiate the bivariate g.f. function above, i.e., Sum_{n, k >= 1} b_k(n)*x^n*y^k, with respect to y and set y = 1, we get the g.f. of the sequence (Sum_{k = 1..n} k*b_k(n): n >= 1). It is C(x)/(1 - C(x))^2.

When c(m) = m for all m >= 1, we have m-color compositions of n that were first studied by Agarwal (2000). The cyclic version of these m-color compositions were studied by Gibson (2017) and Gibson et al. (2018).

When c(m) = m for each m >= 1, we have C(x) = x/(1 - x)^2, and so C(x)/(1 - C(x))^2 = x * (1 - x)^2/(1 - 3*x + x^2)^2, which is the g.f. of the current sequence.

Hence, a(n) is the total number of parts in all m-color compositions of n (in the sense of Agarwal (2000)).

(End)

Series reversal gives A153294 starting from index 1, with alternating signs: 1, -4, 18, -86, 427, -2180, ... - Vladimir Reshetnikov, Aug 03 2019

Cyclic compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation. These were first studied by Sommerville (1909).

Symmetric cyclic compositions or circular palindromes or achiral cyclic compositions are those cyclic compositions that have at least one axis of symmetry. They were also studied by Sommerville (1909, pp. 301-304).

Dihedral compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation or reflection. See, for example, Knopfmacher and Robbins (2013).

The number of dihedral compositions of n (of any kind) is the average of the corresponding numbers of cyclic and symmetric cyclic compositions of n.

Let c = (c(m): m >= 1) be the input sequence and let b_k = (b_k(n): n >= 1) be the output sequence under Bower's DIK[k] ("bracelet, indistinct, unlabeled" with k boxes) transform of c; that is, b_k(n) = (DIK[k] c)n for n >= 1. Hence, b_k(n) is the number of dihedral compositions of n with k parts, where a part of size m can be colored with one of c(m) colors. If C(x) = Sum{m >= 1} c(m)*x^m is the g.f. of the input sequence c, then the bivariate g.f. of the list of sequences (b_k: k >= 1) = ((DIK[k] c): k >= 1) = ((b_k(n): n >= 1): k >= 1) is Sum_{n,k >= 1} b_k(n)*x^n*y^k = (1 + y * C(x))^2/(4 * (1 - y^2 * C(x^2))) - (1/4) - (1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - y^d * C(x^d)).

Here, Sum_{k=1..n} k*b_k(n) is the total number of parts in all colored dihedral compositions of n (where the coloring of parts is done according to the input sequence c). To find the g.f. of the sequence (Sum_{k=1..n} k*b_k(n): n >= 1), we differentiate the above bivariate g.f. (i.e., Sum_{n,k >= 1} b_k(n)*x^n*y^k) w.r.t. y and set y = 1. We get (1 + C(x)) * (C(x) + C(x^2))/(2 * (1 - C(x^2))^2) + (1/2) * Sum_{d >= 1} phi(d) * C(x^d)/(1 - C(x^d)).

For the current sequence, the input sequence is c(m) = m for m >= 1, and we are dealing with the so-called "m-color" compositions. m-color linear compositions were studied by Agarwal (2000), whereas m-color cyclic compositions were studied by Gibson (2017) and Gibson et al. (2018).

Thus, for the current sequence, a(n) is the total number of parts in all m-color dihedral compositions of n (where a part of size m may be colored with one of m colors). Since C(x) = x/(1 - x)^2, we get that (1 + C(x)) * (C(x) + C(x^2))/(2 * (1 - C(x^2))^2) + (1/2) * Sum_{d >= 1} phi(d) * C(x^d)/(1 - C(x^d)) = (1/2) * (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2) + (1/2) * Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)).