|
%I M1141 #339 Apr 04 2024 10:54:53
%S 1,1,1,2,4,8,17,37,82,185,423,978,2283,5373,12735,30372,72832,175502,
%T 424748,1032004,2516347,6155441,15101701,37150472,91618049,226460893,
%U 560954047,1392251012,3461824644,8622571758,21511212261,53745962199,134474581374
%N Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=1..n-1} a(k)*a(n-1-k).
%C Arises in enumerating secondary structures of RNA molecules. The 17 structures with 6 nucleotides are shown in the illustration (after Waterman, 1978).
%C Hankel transform is period 8 sequence [1, 0, -1, -1, -1, 0, 1, 1, ...] (A046980).
%C Enumerates peak-less Motzkin paths of length n. Example: a(5)=8 because we have HHHHH, HHUHD, HUHDH, HUHHD, UHDHH, UHHDH, UHHHD, UUHDD, where U=(1,1), D=(1,-1) and H=(1,0). - _Emeric Deutsch_, Nov 19 2003
%C Number of Dyck paths of semilength n-1 with no UUU's and no DDD's, where U=(1,1) and D=(1,-1) (n>0). - _Emeric Deutsch_, Nov 19 2003
%C For n >= 1, a(n) = number of dissections of an (n+2)-gon with strictly disjoint diagonals and no diagonal incident with the base. (One side of the (n+2)-gon is designated the base.) - _David Callan_, Mar 23 2004
%C For n >= 2, a(n-2)= number of UU-free Motzkin n-paths = number of DU-free Motzkin n-paths. - _David Callan_, Jul 15 2004
%C a(n) = number of UU-free Motzkin n-paths containing no low peaks (A low peak is a UD pair at ground level, i.e., whose removal would create a pair of Motzkin paths). For n >= 1, a(n) = number of UU-free Motzkin (n-1)-paths = number of DU-free Motzkin (n-1)-paths. a(n) is asymptotically ~ c n^(-3/2) (1 + phi)^n with c = 1.1043... and phi=(1+sqrt(5))/2. - _David Callan_, Jul 15 2004. In closed form, c = sqrt(30+14*sqrt(5))/(4*sqrt(Pi)) = 1.104365547309692849... - _Vaclav Kotesovec_, Sep 11 2013
%C a(n) = number of Dyck (n+1)-paths with all pyramid sizes >= 2. A pyramid is a maximal subpath of the form k upsteps immediately followed by k downsteps and its size is k. - _David Callan_, Oct 24 2004
%C a(n) = number of Dyck paths of semilength n+1 with no small pyramids (n >= 1). A pyramid is a maximal sequence of the form k Us followed by k Ds with k >= 1. A small pyramid is one with k=1. For example, a(4)=4 counts the following Dyck 5-paths (pyramids denoted by lowercase letters and separated by a vertical bar): uuuuuddddd, Uuudd|uuddD, uudd|uuuddd, uuuddd|uudd. - _David Callan_, Oct 25 2004
%C From _Emeric Deutsch_, Jan 08 2006: (Start)
%C a(n) = number of Motzkin paths of length n-1 with no peaks at level >= 1. Example: a(4)=4 because we have HHH, HUD, UDH and UHD, where U=(1,1), D=(1,-1) and H=(1,0).
%C a(n) = number of Motzkin paths of length n+1 with no level steps on the x-axis and no peaks at level >=1. Example: a(4)=4 because we have UHHHD, UHDUD, UDUHD and UUHDD, where U=(1,1), D=(1,-1) and H=(1,0).
%C a(n) = number of Dyck paths of length 2n having no ascents and descents of even length. An ascent (descent) is a maximal sequence of up (down) steps. Example: a(4)=4 because we have UDUDUDUD, UDUUUDDD, UUUDDDUD and UUUDUDDD, where U=(1,1), D=(1,-1) and H=(1,0).
%C a(n) = number of Dyck paths of length 2n having ascents only of length 1 or 2 and having no peaks of the form UUDD. An ascent is a maximal sequence of up steps. Example: a(4)=4 because we have UDUDUDUD, UDUUDUDD, UUDUDDUD and UUDUDUDD, where U=(1,1), D=(1,-1) and H=(1,0).
%C a(n) = number of noncrossing partitions of [n+1] having no singletons and in each block the two leftmost points are of the form i,i+1. Example: a(4)=4 because we have 12345, 12/345, 123/45 and 125/34; the noncrossing partition 145/23 does not satisfy the requirements because 1 and 4 are not consecutive.
%C a(n) = number of noncrossing partitions of [n+1] with no singletons, except possibly the block /1/ and no blocks of the form /i,i+1/, except possibly the block /1,2/. Example: a(4)=4 because we have 12345, 1/2345, 12/345 and 15/234.
%C (End)
%C a(n+1) = [1, 1, 2, 4, 8, 17, 37, ...] gives the antidiagonal sums of triangle of Narayana, A001263. - _Philippe Deléham_, Oct 21 2006
%C a(n) = number of Dyck (n+1)-paths with no UDUs and no DUDs. For example, a(4)=4 counts UUUUUDDDDD, UUUDDUUDDD, UUDDUUUDDD, UUUDDDUUDD. - _David Callan_, May 08 2007
%C a(n) is also the number of Dyck paths of semilength n without height of peaks and valleys 2(mod 3). - Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008
%C G.f. of a(n+1) is 1/(1-x-x^2-x^3/(1-x-x^2-x^3/(1-... (continued fraction). - _Paul Barry_, May 20 2009
%C A Chebyshev transform of the Motzkin numbers A001006: g.f. is the image of (1-x-(1-2x-3x^2)^(1/2))/(2x^2) under the mapping that takes g(x) to (1/(1+x^2))g(x/(1+x^2)). - _Paul Barry_, Mar 10 2010
%C For n >= 1, the number of lattice paths of weight n -1 that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: an (1,0)-step with weight 1, an (1,0)-step with weight 2, a (1,1)-step with weight 2, and a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps. a(4)=4 because, denoting by h (H) the (1,0)-step of weight 1 (2), and u=(1,1), d=(1,-1), we have the following four paths of weight 3: hH, Hh, hhh, and ud. (See the g.f. C(x) on p. 295 of the Bona-Knopfmacher reference.)
%C From _David Callan_, Aug 27 2014: (Start)
%C a(n) = number of noncrossing partitions of [n] with all blocks of size 1 or 2 and no blocks of the form /i,i+1/. Example: a(4)=4 because we have 1234, 13/2/4, 14/2/3, and 1/24/3.
%C It appears that a(n) = number of permutations of [n] that avoid the three dashed patterns 123, 132, 24-13, and contain no small jumps (jumps of one unit). For example, a(4)=4 counts 3214, 3241, 4213, and 4321 but not 4312 because 12 is a small jump. (End)
%C Number of DU_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - _Sergey Kirgizov_, Apr 08 2018
%C a(n) is also the number of 3412-avoiding involutions on [n] with no transpositions of the form (i,i+1). For example, a(4)=4 counts the involutions 1234, 1432, 3214, 4231. - _Juan B. Gil_, May 23 2020
%C For n >= 2, a(n) equals the number of Dyck paths with air pockets of length n. A Dyck path with air pockets is a nonempty lattice path in the first quadrant of Z^2 starting at the origin, ending on the x-axis, and consisting of up-steps U = (1,1) and down-steps D_k = (1, -k), k >= 1, where two down-steps cannot be consecutive. For example, the only path of length 2 is UD_1; for length 3 we have UU_D2; for length 4 there are 2 paths: UUUD_3, UD_1UD_1; and for length 5 we have 4 paths: UUUUD_4, UUD_2UD_1, UD_1UUD_2, UUD_1UD_2. - _Sergey Kirgizov_, Dec 15 2022
%D Cameron, Naiomi, and Everett Sullivan. "Peakless Motzkin paths with marked level steps at fixed height." Discrete Mathematics 344.1 (2021): 112154.
%D A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seiichi Manyama, <a href="/A004148/b004148.txt">Table of n, a(n) for n = 0..2404</a> (first 201 terms from T. D. Noe)
%H Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, <a href="http://doi.org/10.1007/978-3-319-77313-1_15">Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects</a>, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
%H Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
%H Andrei Asinowski, Cyril Banderier and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H Sergey Avgustinovich, Sergey Kitaev and Alexander Valyuzhenich, <a href="http://personal.strath.ac.uk/sergey.kitaev/Papers/mesh.pdf">Avoidance of boxed mesh patterns on permutations</a>.
%H Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2211.04914">Grand Dyck paths with air pockets</a>, arXiv:2211.04914 [math.CO], 2022.
%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.
%H Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/knight.pdf">Knight's paths towards Catalan numbers</a>, Univ. Bourgogne Franche-Comté (2022).
%H Jean-Luc Baril and José Luis Ramírez, <a href="https://arxiv.org/abs/2302.12741">Descent distribution on Catalan words avoiding ordered pairs of Relations</a>, arXiv:2302.12741 [math.CO], 2023.
%H Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/pathwall.pdf">Fibonacci and Catalan paths in a wall</a>, 2023.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.html">On a Generalization of the Narayana Triangle</a>, J. Int. Seq. 14 (2011) # 11.4.5.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.
%H Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.
%H Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.
%H Paul Barry, <a href="https://arxiv.org/abs/2211.12637">Conjectures on Somos 4, 6 and 8 sequences using Riordan arrays and the Catalan numbers</a>, arXiv:2211.12637 [math.CO], 2022.
%H Paul Barry, Aoife Hennessy and Nikolaos Pantelidis, <a href="https://doi.org/10.1007/s10801-020-00953-4">Algebraic properties of Riordan subgroups</a>, J Algebr Comb 53, 1015-1036 (2021).
%H Antonio Bernini, Matteo Cervetti, Luca Ferrari and Einar Steingrimsson, <a href="https://arxiv.org/abs/1910.00299">Enumerative combinatorics of intervals in the Dyck pattern poset</a>, arXiv:1910.00299 [math.CO], 2019.
%H M. Bona and A. Knopfmacher, <a href="http://dx.doi.org/10.1007/s00026-010-0060-7">On the probability that certain compositions have the same number of parts</a>, Ann. Comb., 14 (2010), 291-306.
%H A. J. Bu and Robert Dougherty-Bliss, <a href="https://arxiv.org/abs/2009.09061">Enumerating Restricted Dyck Paths with Context-Free Grammars</a>, arXiv:2009.09061 [math.CO], 2020.
%H Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%H Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
%H C. Coker, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00037-2">Enumerating a class of lattice paths</a>, Discrete Math., 271 (2003), 13-28.
%H Emeric Deutsch and Sergi Elizalde, <a href="https://doi.org/10.1007/s00026-012-0129-6">Restricted simsun permutations</a>, Ann. Comb. 16, No. 2, 253-269 (2012).
%H Emeric Deutsch and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00341-2">A bijection between ordered trees and 2-Motzkin paths and its many consequences</a>, Disc. Math. 256 (2002) 655-670.
%H R. Donaghey, <a href="http://dx.doi.org/10.1016/0095-8956(80)90045-3">Automorphisms on Catalan trees and bracketing</a>, J. Combin. Theory, Series B, 29 (1980), 75-90.
%H Robert G. Donnelly, Molly W. Dunkum, Sasha V. Malone, and Alexandra Nance, <a href="https://arxiv.org/abs/2012.14991">Symmetric Fibonaccian distributive lattices and representations of the special linear Lie algebras</a>, arXiv:2012.14991 [math.CO], 2020.
%H T. Doslic, D. Svrtan and D. Veljan, <a href="http://dx.doi.org/10.1016/j.disc.2004.04.001">Enumerative aspects of secondary structures</a>, Discr. Math., 285 (2004), 67-82.
%H Robert Dougherty-Bliss, <a href="https://sites.math.rutgers.edu/~zeilberg/Theses/RobertDoughertyBlissThesis.pdf">Experimental Methods in Number Theory and Combinatorics</a>, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 96.
%H D. Drake, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Drake/drake.html">Bijections from Weighted Dyck Paths to Schröder Paths</a>, J. Int. Seq. 13 (2010) # 10.9.2.
%H Eric S. Egge and Kailee Rubin, <a href="http://arxiv.org/abs/1508.05310">Snow Leopard Permutations and Their Even and Odd Threads</a>, arXiv:1508.05310 [math.CO], 2015.
%H S. B. Ekhad and M. Yang, <a href="http://arxiv.org/abs/1707.04654">Automated proofs of many conjectured recurrences in the OEIS made by R. J. Mathar</a>, arXiv:1707.04654 (2017).
%H Juan B. Gil and Luiz E. Lopez, <a href="https://arxiv.org/abs/2203.10589">Enumeration of symmetric arc diagrams</a>, arXiv:2203.10589 [math.CO], 2022.
%H Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, <a href="http://dx.doi.org/10.1016/j.disc.2011.06.004">Symmetric circular matchings and RNA folding</a>. Discr. Math., 312:100-112, 2012. See Eq. 27.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=421">Encyclopedia of Combinatorial Structures 421</a>
%H Emma Y. Jin and Christian M. Reidys, <a href="http://dx.doi.org/10.1007/s11538-007-9265-2">Asymptotic Enumeration of RNA Structures with Pseudoknots</a>, Bulletin of Mathematical Biology 70 (2008), 951-970. See Eq. 22.
%H Shu-Chung Liu, Jun Ma and Yeong-Nan Yeh, <a href="http://dx.doi.org/10.1111/j.1467-9590.2008.00415.x">Dyck Paths with Peak- and Valley-Avoiding Sets</a>, Stud. Appl Math. 121 (3) (2008) 263-289. [From Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008]
%H Sophie Morier-Genoud and Valentin Ovsienko, <a href="https://arxiv.org/abs/1908.04365">On q-deformed real numbers</a>, arXiv:1908.04365 [math.QA], 2019.
%H Sophie Morier-Genoud and Valentin Ovsienko, <a href="https://arxiv.org/abs/2011.10809">Quantum real numbers and q-deformed Conway-Coxeter friezes</a>, arXiv:2011.10809 [math.QA], 2020. See section 3.3. Mentions this sequence.
%H E. Munarini and N. Z. Salvi, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s49zagaglia.html">Binary strings without zigzags</a>, Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.
%H A. Nkwanta and A. Tefera, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Nkwanta/nkwanta4.html">Curious Relations and Identities Involving the Catalan Generating Function and Numbers</a>, Journal of Integer Sequences, 16 (2013), #13.9.5.
%H Valentin Ovsienko, <a href="https://amathr.org/wp-content/uploads/2023/03/QOMBINUMReview-1.pdf">Modular invariant q-deformed numbers: first steps</a>, 2023.
%H A. Panayotopoulos and P. Vlamos, <a href="http://dx.doi.org/10.1007/978-3-642-33412-2_49">Cutting Degree of Meanders</a>, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From _N. J. A. Sloane_, Dec 29 2012
%H N. J. A. Sloane, <a href="/A004148/a004148.gif">Illustration of a(6) = 17</a> (after Waterman, 1978).
%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1978), 261-272.
%H P. R. Stein and M. S. Waterman, <a href="/A001006/a001006_4.pdf">On some new sequences generalizing the Catalan and Motzkin numbers</a> [Corrected annotated scanned copy]
%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86.
%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)
%H M. S. Waterman, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.4425">Secondary structure of single-stranded nucleic acids</a>, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.
%F a(n+1) = a(n) + a(1)*a(n-2) + a(2)*a(n-3) + ... + a(n-1)*a(0).
%F G.f.: (1 - x + x^2 - sqrt(1 - 2*x - x^2 - 2*x^3 + x^4)) / (2*x^2). - _Michael Somos_, Jul 20 2003
%F G.f.: (1/z)*(1-C(-z/(1-3*z+z^2))), where C(z)=(1-sqrt(1-4*z))/(2*z) is the Catalan function. - _Emeric Deutsch_, Nov 19 2003
%F G.f.: 1 + F(x, x)/x, where F(x, t) is the g.f. of the Narayana numbers: xF^2 - (1-x-tx)F + tx = 0. - _Emeric Deutsch_, Nov 19 2003
%F G.f. A(x) satisfies the functional equation: x^2*A(x)^2 - (x^2 - x + 1)*A(x) + 1 = 0. - _Michael Somos_, Jul 20 2003
%F Series reversion of g.f. A(x) is -A(-x) (if offset 1). - _Michael Somos_, Jul 20 2003
%F a(n) = A088518(2n) + A088518(2n+1) - A088518(2n+2). - _Emeric Deutsch_, Nov 19 2003
%F a(n) = Sum_{k=ceiling((n+1)/2)..n} (binomial(k, n-k)*binomial(k, n-k+1)/k) for n >= 1. - _Emeric Deutsch_, Nov 12 2003 This formula counts (i) disjoint-diagonal dissections by number of diagonals, (ii) peak-less Motzkin paths by number of up steps, (iii) UUU- and DDD-free Dyck paths by number of ascents. - _David Callan_, Mar 23 2004
%F a(n) = Sum_{k=0..floor(n/2)} A131198(n-k,k). - _Philippe Deléham_, Nov 06 2007
%F G.f.: 1/(1-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-x... (continued fraction). - _Paul Barry_, Dec 08 2008
%F G.f.: 1/(1-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-... (continued fraction). - _Paul Barry_, May 16 2009
%F From _Paul D. Hanna_, Jun 26 2009: (Start)
%F Let A(x)^m = Sum_{n>=0} a(n,m)*x^n, then
%F a(n,m) = Sum_{k=0..n} Sum_{j=0..k} C(n-k+j+m,n-k)*m/(n-k+j+m) * C(n-k,k-j)*C(k-j,j).
%F (End)
%F From _Paul Barry_, Mar 10 2010: (Start)
%F G.f.: (1/(1+x^2))*M(x/(1+x^2)), M(x) the g.f. of the Motzkin numbers A001006;
%F G.f.: 1/(1-x+x^2-x^2/(1-x+x^2-x^2/(1-x+x^2-x^2/(1-x+x^2-x^2/(1-... (continued fraction).
%F a(n) = Sum_{k=0..floor(n/2)} (-1)^k*C(n-k,k)*A001006(n-2*k). (End)
%F G.f.: 1 + x*exp( Sum_{n>=1} (x^n/n)*(Sum_{k=0..n} C(n,k)^2*x^k) ). - _Paul D. Hanna_, Mar 15 2011
%F G.f.: exp( Sum_{n>=1} A051292(n)*x^n/n ), where A051292(n) is a Whitney number of level n. - _Paul D. Hanna_, Mar 15 2011
%F Let the g.f. be A(x), then B(x)=(1+x*A(x)) = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1+x+x^2), B(x) = 1 +1*x + 1*x^2 +1*x^3 + 2*x^4 + 4*x^5 + ... is the g.f. of this sequence prepended with 1; more generally B(x) = C(x/(1+x+x^2)) where C(x) is the g.f. for the Catalan numbers (A000108). - _Joerg Arndt_, Mar 18 2011
%F D-finite with recurrence: (n+2)*a(n) - (2n+1)*a(n-1) + (1-n)*a(n-2) + (5-2n)*a(n-3) + (n-4)*a(n-4) = 0. - _R. J. Mathar_, Dec 01 2011. This recurrence follows from the Wilf-Zeilberger (WZ) proof technique applied to Sum_{k=ceiling((n+1)/2)..n} (binomial(k,n-k) * binomial(k,n-k+1)/k). - _T. Amdeberhan_, Jul 23 2012
%F Given g.f. A(x), then B(x) = x * A(x) satisfies B(x) = x + x*B(x) / (1 - x*B(x)). - _Michael Somos_, Jun 05 2014
%F G.f.: 1 - x / (x^2 - 1 / (1 - x / (x^2 - 1 / (1 - x / (x^2 - ...))))). - _Michael Somos_, Jun 05 2014
%F 0 = a(n)*(a(n+1) - 5*a(n+2) - 4*a(n+3) - 11*a(n+4) + 7*a(n+5)) + a(n+1)*(a(n+1) + 6*a(n+2) + 12*a(n+3) + 11*a(n+4) - 11*a(n+5)) + a(n+2)*(-a(n+2) - 7*a(n+3) + 12*a(n+4) - 4*a(n+5)) + a(n+3)*(-a(n+3) + 6*a(n+4) - 5*a(n+5)) + a(n+4)*(a(n+4) + a(n+5)) if n >= -1. - _Michael Somos_, Jun 05 2014
%F a(n) = hypergeom([-n/2, (1 - n)/2, (1 - n)/2, 1 - n/2], [2, -n, -n + 1], 16). - _Peter Luschny_, Jan 25 2020
%F a(n) = Sum_{k=0..n-1} binomial(n-k,k+1)*binomial(n-k,k)/(n-k) for n > 0. - _Rigoberto Florez_, Apr 17 2023
%F a(n) ~ 5^(1/4) * phi^(2*n + 2) / (2 * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, May 05 2023
%e G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 8*x^5 + 17*x^6 + 37*x^7 + 82*x^8 + 185*x^9 + 432*x^10 + ...
%e Det([1]) = 1, Det([1, 1; 1, 1]) = 0, Det([1, 1, 1; 1, 1, 2; 1, 2, 4]) = -1. - _Michael Somos_, May 12 2022
%p w := proc(l) x - 1 - x^2*(1 - x^l)/(1-x) end:
%p S := proc(l) (-w(l) - sqrt(w(l)^2 - 4*x^2))/(2*x^2) end:
%p # S(0) is g.f. for Motzkin numbers A001006,
%p # S(1) is g.f. for this sequence,
%p # S(2) is g.f. for A004149, etc.
%t a[0]=1; a[n_Integer]:= a[n]= a[n-1]+Sum[a[k]*a[n-2-k], {k,n-2}]; Array[a, 35, 0]
%t CoefficientList[Series[(1-x+x^2-Sqrt[x^4-2x^3-x^2-2x+1])/(2x^2), {x,0,40}], x] (* _Harvey P. Dale_, May 09 2011 *)
%t a[n_]:= SeriesCoefficient[(1 -x +x^2 -Sqrt[1 -2x -x^2 -2x^3 +x^4])/(2x^2), {x, 0, n}]; (* _Michael Somos_, Jun 05 2014 *)
%t a[n_] := HypergeometricPFQ[{-n/2, (1-n)/2, (1-n)/2, 1-n/2}, {2, -n, -n + 1}, 16]; Array[a, 33, 0] (* _Peter Luschny_, Jan 25 2020 *)
%t Table[If[n==0,1, Sum[(Binomial[n-k,k+1]Binomial[n-k,k]/(n-k)), {k,0,n-1}]], {n,0,10}] (* _Rigoberto Florez_, Apr 17 2023 *)
%o (PARI) {a(n) = polcoeff( (1 - x + x^2 - sqrt(1 - 2*x - x^2 + x^3 * (-2 + x + O(x^n)))) / 2, n + 2)}; /* _Michael Somos_, Jul 20 2003 */
%o (PARI) a(n,m=1)=sum(k=0,n,sum(j=0,k,binomial(n-k+j+m,n-k)*m/(n-k+j+m)*binomial(n-k,k-j)*binomial(k-j,j))) \\ _Paul D. Hanna_, Jun 26 2009
%o (PARI) {a(n)=polcoeff(1+x*exp(sum(m=1,n,sum(k=0,m,binomial(m,k)^2*x^k)*x^m/m)+x*O(x^n)),n)} /* _Paul D. Hanna_, Mar 15 2011 */
%o (PARI) {a(n)=local(A051292=1+(1-x^2)/sqrt((1-3*x+x^2)*(1+x+x^2) +x*O(x^n)));polcoeff(exp(sum(m=1,n,polcoeff(A051292,m)*x^m/m)+x*O(x^n)),n)} /* _Paul D. Hanna_, Mar 15 2011 */
%o (Maxima) a(n):=coeff(taylor((1-x+x^2-sqrt(1-2*x-x^2-2*x^3+x^4))/(2*x^2),x,0,n),x, n); makelist(a(n),n,0,12); // _Emanuele Munarini_, Jul 07 2001
%o (Haskell)
%o a004148 n = a004148_list !! n
%o a004148_list = 1 : f [1] where
%o f xs'@(x:xs) = y : f (y : xs') where
%o y = x + sum (zipWith (*) xs $ reverse $ tail xs)
%o -- _Reinhard Zumkeller_, Nov 13 2012
%o (PARI) {a(n) = my(A = 1 + O(x)); for(k=1, n, A = 1 - x / (x^2 - 1/A)); polcoeff( A, n)}; /* _Michael Somos_, Jun 05 2014 */
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 35); Coefficients(R!( (1-x+x^2 - Sqrt(1-2*x-x^2-2*x^3+x^4))/(2*x^2) )); // _G. C. Greubel_, Dec 30 2019
%o (Sage)
%o def A004148_list(prec):
%o P = PowerSeriesRing(ZZ, 'x', prec)
%o x = P.gen().O(prec)
%o return ( (1-x+x^2 -sqrt(1-2*x-x^2-2*x^3+x^4))/(2*x^2) ).list()
%o A004148_list(35) # _G. C. Greubel_, Dec 30 2019
%Y Second row of A064645.
%Y Cf. A000108, A001006, A088518, A051292 (lgf), A004149, A131198.
%Y Cf. A046980 (Hankel transform).
%K easy,nonn,nice
%O 0,4
%A _N. J. A. Sloane_
|
