Search: id:A004148 Results 1-1 of 1 results found. %I A004148 M1141 %S A004148 1,1,1,2,4,8,17,37,82,185,423,978,2283,5373,12735,30372,72832,175502, %T A004148 424748,1032004,2516347,6155441,15101701,37150472,91618049,226460893, %U A004148 560954047,1392251012,3461824644,8622571758,21511212261,53745962199 %N A004148 Generalized Catalan numbers: a(n+1)=a(n)+ Sum a(k)a(n-1-k), k=1..n-1. %C A004148 Arises in enumerating secondary structures of RNA molecules. The 17 structures with 6 nucleotides are shown in the illustration (after Waterman, 1978). %C A004148 Hankel transform is period 8 sequence [1,1,1,0,-1,-1,-1,0,...]. %C A004148 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 (deutsch(AT)duke.poly.edu), Nov 19 2003 %C A004148 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 (deutsch(AT)duke.poly.edu), Nov 19 2003 %C A004148 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 (callan(AT)stat.wisc.edu), Mar 23 2004 %C A004148 For n>=2, a(n-2)= number of UU-free Motzkin n-paths = number of DU-free Motzkin n-paths. - David Callan (callan(AT)stat.wisc.edu), Jul 15 2004 %C A004148 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 (callan(AT)stat.wisc.edu), Jul 15 2004 %C A004148 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 (callan(AT)stat.wisc.edu), Oct 24 2004 %C A004148 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 (callan(AT)stat.wisc.edu), Oct 25 2004 %C A004148 Comments from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 08 2006: "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 A004148 "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 A004148 "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 A004148 "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 A004148 "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 A004148 "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 A004148 a(n+1)= [1, 1, 2, 4, 8, 17, 37,...] gives the antidiagonal sums of triangle of Narayana A001263 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 21 2006 %C A004148 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 (callan(AT)stat.wisc.edu), May 08 2007 %C A004148 a(n) is also the number of Dyck paths of length n without height of peaks and valleys 2(mod 3). [From Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008] %C A004148 G.f. of a(n+1) is 1/(1-x-x^2-x^3/(1-x-x^2-x^3/(1-... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), May 20 2009] %D A004148 Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7. %D A004148 C. Coker, Enumerating a class of lattice paths, Discrete Math., 271, 2003, 13-28. %D A004148 E. Deutsch and L.W. Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Discrete Math., 256, 2002, 655-670. %D A004148 R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90. %D A004148 T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82. %D A004148 Shu-Chung Liu, Jun Ma, Yeong-Nan Yeh, "Dyck Paths with Peak- and Valley-Avoiding Sets", Stud. Appl Math. 121 (3) (2008) 263-289 [From Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008] %D A004148 A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147. %D A004148 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %D A004148 P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272. %D A004148 M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en bilogie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86. %D A004148 M. S. Waterman, Secondary structure of single-stranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978. %H A004148 T. D. Noe, Table of n, a(n) for n=0..200 %H A004148 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 421 %H A004148 E. Munarini and N. Z. Salvi, Binary strings without zigzags %H A004148 N. J. A. Sloane, Illustration of a(6) = 17 (after Waterman, 1978). %H A004148 M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86. %H A004148 M. S. Waterman, Home Page (contains copies of his papers) %F A004148 a(n+1)=a(n)+a(1)a(n-2)+a(2)a(n-3)+...+a(n-1)a(0). %F A004148 G.f.: (1-x+x^2-sqrt(1-2x-x^2-2*x^3+x^4))/(2x^2). %F A004148 G.f.: (1/z)[1-C(-z/(1-3z+z^2))], where C(z)=(1-sqrt(1-4z))/(2z) is the Catalan function. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 19 2003 %F A004148 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 (deutsch(AT)duke.poly.edu), Nov 19 2003 %F A004148 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 A004148 Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos, Jul 20 2003 %F A004148 a(n)=A088518(2n)+A088518(2n+1)-A088518(2n+2). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 19 2003 %F A004148 a(n)=sum(binomial(k, n-k)*binomial(k, n-k+1)/k, k=ceil((n+1)/2)..n) for n>=1. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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 (callan(AT)stat.wisc.edu), Mar 23 2004 %F A004148 a(n) = Sum_{k, 0<=k<=[n/2]}A131198(n-k,k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 06 2007 %F A004148 G.f.: 1/(1-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-x..... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Dec 08 2008] %F A004148 G.f.: 1/(1-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), May 16 2009] %F A004148 Contribution from Paul D. Hanna (pauldhanna(AT)juno.com), Jun 26 2009: (Start) %F A004148 Let A(x)^m = Sum_{n>=0} a(n,m)*x^n, then %F A004148 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 A004148 (End) %p A004148 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 A004148 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 ] %o A004148 (PARI) a(n)=polcoeff((1-x+x^2-sqrt(1-2*x-x^2+x^3*(-2+x+O(x^n))))/2,n+2) %o A004148 (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)))} [From Paul D. Hanna (pauldhanna(AT)juno.com), Jun 26 2009] %Y A004148 Second row of A064645. %Y A004148 Cf. A088518. %Y A004148 Sequence in context: A136671 A024557 A025241 this_sequence A085022 A003426 A087803 %Y A004148 Adjacent sequences: A004145 A004146 A004147 this_sequence A004149 A004150 A004151 %K A004148 easy,nonn,nice %O A004148 0,4 %A A004148 N. J. A. Sloane (njas(AT)research.att.com). Search completed in 0.002 seconds