cp's OEIS Frontend

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.

%I A030267 #95 Mar 04 2025 17:21:29
%S A030267 1,4,14,46,145,444,1331,3926,11434,32960,94211,267384,754309,2116936,
%T A030267 5914310,16458034,45638101,126159156,347769719,956238170,2623278946,
%U A030267 7181512964,19622668679,53522804976,145753273225,396323283724,1076167858046,2918447861686
%N 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.
%C A030267 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
%C A030267 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
%C A030267 From _Petros Hadjicostas_, Jun 24 2019: (Start)
%C A030267 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.
%C A030267 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.
%C A030267 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.
%C A030267 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).
%C A030267 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.
%C A030267 Hence, a(n) is the total number of parts in all m-color compositions of n (in the sense of Agarwal (2000)).
%C A030267 (End)
%C A030267 Series reversal gives A153294 starting from index 1, with alternating signs: 1, -4, 18, -86, 427, -2180, ... - _Vladimir Reshetnikov_, Aug 03 2019
%D A030267 R. P. Grimaldi, Compositions and the alternate Fibonacci numbers, Congressus Numerantium, 186, 2007, 81-96.
%H A030267 T. D. Noe, <a href="/A030267/b030267.txt">Table of n, a(n) for n = 1..200</a>
%H A030267 A. K. Agarwal, <a href="https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005b15_1421.pdf">n-colour compositions</a>, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
%H A030267 E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170 (1997), 211-217.
%H A030267 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H A030267 R. X. F. Chen and L. W. Shapiro, <a href="http://cs.uwaterloo.ca/journals/JIS/VOL10/Chen/chen509.html">On sequences G(n) satisfying G(n)=(d+2)G(n-1)-G(n-2)</a>, J. Integer Seq. 10 (2007), Article #07.8.1; see Proposition 17.
%H A030267 Éva Czabarka, Rigoberto Flórez, and Leandro Junes, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p3">Some Enumerations on Non-Decreasing Dyck Paths</a>, Electron. J. Combin., 22(1) (2015), #P1.3.
%H A030267 Éva Czabarka, Rigoberto Flórez, and Leandro Junes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Florez/florez12.html">A Discrete Convolution on the Generalized Hosoya Triangle</a>, J. Integer Seq., 18 (2015), Article #15.1.6.
%H A030267 Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez, <a href="https://doi.org/10.1016/j.disc.2018.06.032">Enumerations of peaks and valleys on non-decreasing Dyck paths</a>, Discrete Math. 341 (10) (2018), 2789-2807.
%H A030267 A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137 (1995), 155-176.
%H A030267 Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Florez/florez51.html">Counting Subwords in Non-Decreasing Dyck Paths</a>, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 6, 14-15, 17, 19.
%H A030267 Meghann Moriah Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of compositions</a>, Master of Science, Georgia Southern University, 2017.
%H A030267 Meghann Moriah Gibson, Daniel Gray, and Hua Wang, <a href="https://doi.org/10.1016/j.disc.2018.08.001">Combinatorics of n-color compositions</a>, Discrete Mathematics 341 (2018), 3209-3226.
%H A030267 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Janjic/janjic33.html">Hessenberg Matrices and Integer Sequences</a>, J. Integer Seq. 13 (2010), Article #10.7.8.
%H A030267 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H A030267 <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>
%H A030267 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,6,-1).
%F A030267 a(n) = -a(-n) = (2n * F(2n+1) + (2 - n) * F(2n))/5 with F(n) = A000045(n) (Fibonacci numbers).
%F A030267 G.f.: x * (1 - x)^2/(1 - 3*x + x^2)^2.
%F A030267 a(n) = Sum_{k = 1..n} k*C(n + k - 1, 2*k - 1).
%F A030267 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
%F A030267 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
%F A030267 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
%F A030267 E.g.f.: exp(3*x/2)*(15*x*cosh(sqrt(5)*x/2) + sqrt(5)*(4 + 5*x)*sinh(sqrt(5)*x/2))/25. - _Stefano Spezia_, Mar 04 2025
%e A030267 From _Petros Hadjicostas_, Jun 24 2019: (Start)
%e A030267 Recall that with m-color compositions, a part of size m may be colored with one of m colors.
%e A030267 We have a(1) = 1 because we only have one colored composition, namely 1_1, that has only 1 part.
%e A030267 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.
%e A030267 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.
%e A030267 We have a(14) = 46 because we have the following colored compositions of n = 4:
%e A030267 (i) 4_1, 4_2, 4_3, 4_4; with a total of 4 parts.
%e A030267 (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.
%e A030267 (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.
%e A030267 (iv) 1_1 + 1_1 + 1_1 + 1_1; with a total of 4 parts.
%e A030267 Hence, a(4) = 4 + 20 + 18 + 4 = 46.
%e A030267 (End)
%p A030267 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
%t A030267 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 *)
%o A030267 (PARI) a(n)=(2*n*fibonacci(2*n+1)+(2-n)*fibonacci(2*n))/5
%Y A030267 Partial sums of A038731. First differences of A001870.
%Y A030267 Cf. A001629 (right-shifted inverse Binomial Transform), A023610 (inverse Binomial Transform of left-shifted sequence), A030279, A045623, A088305, A121462, A153294, A279282, A307415, A308723.
%K A030267 nonn,nice,easy
%O A030267 1,2
%A A030267 _Christian G. Bower_
%E A030267 Name clarified using a comment of the author by _Peter Luschny_, Aug 03 2019