

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



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
a(n) = ((3  sqrt(5))^n*(5*n  2*sqrt(5)) + (3 + sqrt(5))^n*(5*n + 2*sqrt(5)))/ (25*2^n).  Peter Luschny, Mar 07 2022


EXAMPLE

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



KEYWORD

nonn,nice,easy


AUTHOR



EXTENSIONS

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


STATUS

approved



