

A030267


Compose the natural numbers with themselves, A(x) = B(B(x)) where B(x) = x/(1x)^2 is the generating function for natural numbers.


17



1, 4, 14, 46, 145, 444, 1331, 3926, 11434, 32960, 94211, 267384, 754309, 2116936, 5914310, 16458034, 45638101, 126159156, 347769719, 956238170, 2623278946, 7181512964, 19622668679, 53522804976, 145753273225, 396323283724, 1076167858046, 2918447861686
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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 mcolor compositions of n that were first studied by Agarwal (2000). The cyclic version of these mcolor 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 mcolor 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


REFERENCES

R. P. Grimaldi, Compositions and the alternate Fibonacci numbers, Congressus Numerantium, 186, 2007, 8196.


LINKS

T. D. Noe, Table of n, a(n) for n = 1..200
A. K. Agarwal, ncolour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 14211427.
E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck paths and qFibonacci numbers, Discrete Math., 170 (1997), 211217.
C. G. Bower, Transforms (2).
R. X. F. Chen and L. W. Shapiro, On sequences G(n) satisfying G(n)=(d+2)G(n1)G(n2), J. Integer Seq. 10 (2007), Article #07.8.1; see Proposition 17.
É. Czabarka, R. Flórez, and L. Junes, Some Enumerations on NonDecreasing Dyck Paths, Electron. J. Combin., 22(1) (2015), #P1.3.
É. Czabarka, R. Flórez, and L. Junes, A Discrete Convolution on the Generalized Hosoya Triangle, J. Integer Seq., 18 (2015), Article #15.1.6.
Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerations of peaks and valleys on nondecreasing Dyck paths, Discrete Math. 341 (10) (2018), 27892807.
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137 (1995), 155176.
Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of ncolor compositions, Discrete Mathematics 341 (2018), 32093226.
M. Janjic, Hessenberg Matrices and Integer Sequences, J. Integer Seq. 13 (2010), Article #10.7.8
N. J. A. Sloane, Transforms.
Index entries for twoway infinite sequences
Index entries for linear recurrences with constant coefficients, signature (6,11,6,1).


FORMULA

a(n) = a(n) = (2n * F(2n+1) + (2  n) * F(2n))/5 with F(n) = A000045(n) (Fibonacci numbers).
G.f.: x * (1  x)^2/(1  3*x + x^2)^2.
a(n) = Sum_{k = 1..n} k*C(n + k  1, 2*k  1).
a(n) = (2/5)*F(2*n) + (1/5)*n*L(2*n), where F(k) are the Fibonacci numbers (F(0)=0, F(1)=1) and L(k) are the Lucas numbers (L(0) = 2, L(1) = 1).  Emeric Deutsch, Jul 21 2008
a(0) = 1, a(1) = 4, a(2) = 14, a(3) = 46, a(n) = 6*a(n1)  11*a(n2) + 6*a(n3)  a(n4).  Harvey P. Dale, Aug 01 2011


EXAMPLE

From Petros Hadjicostas, Jun 24 2019: (Start)
Recall that with mcolor compositions, a part of size m may be colored with one of m colors.
We have a(1) = 1 because we only have one colored composition, namely 1_1, that has only 1 part.
We have a(2) = 4 because we have the following colored compositions of n = 2: 2_1, 2_2, 1_1 + 1_1; hence, a(2) = 1 + 1 + 2 = 4.
We have a(3) = 14 because we have the following colored compositions of n = 3: 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 2_1 + 1_1, 2_2 + 1_1, 1_1 + 1_1 + 1_1; hence, a(3) = 1 + 1 + 1 + 2 + 2 + 2 + 2 + 3 = 14.
We have a(14) = 46 because we have the following colored compositions of n = 4:
(i) 4_1, 4_2, 4_3, 4_4; with a total of 4 parts.
(ii) 1_1 + 3_1, 1_1 + 3_2, 1_1 + 3_3, 3_1 + 1_1, 3_2 + 1_1, 3_3 + 1_1, 2_1 + 2_1, 2_1 + 2_2, 2_2 + 2_1, 2_2 + 2_2; with a total of 2 x 10 = 20 parts.
(iii) 1_1 + 1_1 + 2_1, 1_1 + 1_1 + 2_2, 1_1 + 2_1 + 1_1, 1_1 + 2_2 + 1_1, 2_1 + 1_1 + 1_1, 2_2 + 1_1 + 1_1; with a total of 3 x 6 = 18 parts.
(iv) 1_1 + 1_1 + 1_1 + 1_1; with a total of 4 parts.
Hence, a(4) = 4 + 20 + 18 + 4 = 46.
(End)


MAPLE

with(combinat): L[0]:=2: L[1]:=1: for n from 2 to 60 do L[n]:=L[n1] +L[n2] end do: seq(2*fibonacci(2*n)*1/5+(1/5)*n*L[2*n], n=1..30); # Emeric Deutsch, Jul 21 2008


MATHEMATICA

Table[Sum[k Binomial[n+k1, 2k1], {k, n}], {n, 30}] (* or *) LinearRecurrence[ {6, 11, 6, 1}, {1, 4, 14, 46}, 30] (* Harvey P. Dale, Aug 01 2011 *)


PROG

(PARI) a(n)=(2*n*fibonacci(2*n+1)+(2n)*fibonacci(2*n))/5


CROSSREFS

Partial sums of A038731. First differences of A001870.
Cf. A001629 (rightshifted inverse Binomial Transform), A023610 (inverse Binomial Transform of leftshifted sequence), A030279, A045623, A088305, A121462, A153294, A279282, A307415, A308723.
Sequence in context: A117916 A054449 A029868 * A026290 A027649 A330796
Adjacent sequences: A030264 A030265 A030266 * A030268 A030269 A030270


KEYWORD

nonn,nice,easy


AUTHOR

Christian G. Bower


EXTENSIONS

Name clarified using a comment of the author by Peter Luschny, Aug 03 2019


STATUS

approved



