This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004148 Generalized Catalan numbers: a(n+1) = a(n)+ Sum(k=1..n-1, a(k)*a(n-1-k) ).
(Formerly M1141)

%I M1141

%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,1,1,0,-1,-1,-1,0,...].

%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). [From 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)

%D Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

%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).

%D M. S. Waterman, Secondary structure of single-stranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.

%H T. D. Noe and 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 Sergey Avgustinovich, Sergey Kitaev and Alexander Valyuzhenich, <a href="https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/mesh.pdf">Avoidance of boxed mesh patterns on permutations</a>.

%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 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 E. Deutsch, 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 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 Eric S. Egge, 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 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://algo.inria.fr/ecs/ecs?searchType=1&amp;service=Search&amp;searchTerms=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, 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 E. Munarini and N. Z. Salvi, <a href="http://www.mat.univie.ac.at/~slc/opapers/s49zagaglia.html">Binary strings without zigzags</a>

%H A. Nkwanta, 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 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">Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire</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)

%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=ceil((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<=k<=[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 Conjecture: (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=ceil((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

%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 + ...

%p w:=proc(l) x-1-x^2*(1-x^l)/(1-x); end; S:=proc(l) ( -w(l) - sqrt( w(l)^2 - 4*x^2) )/(2*x^2); end; # S(0) is g.f. for Motzkin numbers A001006, S(1) is g.f. for this sequence, 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, 1, n-2} ]; Array[a[#]&, 20, 0]

%t CoefficientList[Series[(1-x+x^2-Sqrt[x^4-2x^3-x^2-2x+1])/(2x^2), {x,0,60}], x] (* _Harvey P. Dale_, May 09 2011 *)

%t a[ n_] := SeriesCoefficient[ (1 - x + x^2 - Sqrt[1 - 2 x - x^2 - 2 x^3 + x^4]) / (2 x^2), {x, 0, n}]; (* _Michael Somos_, Jun 05 2014 *)

%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_ */

%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 */

%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);

%o 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 */

%Y Second row of A064645.

%Y Cf. A088518, A051292 (lgf).

%K easy,nonn,nice

%O 0,4

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 29 07:21 EDT 2017. Contains 284250 sequences.