login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A030267 Compose the natural numbers with themselves, A(x) = B(B(x)) where B(x) = x/(1-x)^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 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

REFERENCES

R. P. Grimaldi, Compositions and the alternate Fibonacci numbers, Congressus Numerantium, 186, 2007, 81-96.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..200

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.

E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170 (1997), 211-217.

C. G. Bower, Transforms (2).

R. X. F. Chen and L. W. Shapiro, On sequences G(n) satisfying G(n)=(d+2)G(n-1)-G(n-2), J. Integer Seq. 10 (2007), Article #07.8.1; see Proposition 17.

É. Czabarka, R. Flórez, and L. Junes, Some Enumerations on Non-Decreasing 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 non-decreasing Dyck paths, Discrete Math. 341 (10) (2018), 2789-2807.

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137 (1995), 155-176.

Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.

Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.

M. Janjic, Hessenberg Matrices and Integer Sequences, J. Integer Seq. 13 (2010), Article #10.7.8

N. J. A. Sloane, Transforms.

Index entries for two-way 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(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - Harvey P. Dale, Aug 01 2011

EXAMPLE

From Petros Hadjicostas, Jun 24 2019: (Start)

Recall that with m-color 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[n-1] +L[n-2] 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+k-1, 2k-1], {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)+(2-n)*fibonacci(2*n))/5

CROSSREFS

Partial sums of A038731. First differences of A001870.

Cf. A001629 (right-shifted inverse Binomial Transform), A023610 (inverse Binomial Transform of left-shifted 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 03:02 EST 2021. Contains 340384 sequences. (Running on oeis4.)