0,4

Arises in enumerating secondary structures of RNA molecules. The 17 structures with 6 nucleotides are shown in the illustration (after Waterman, 1978).

Hankel transform is period 8 sequence [1,1,1,0,-1,-1,-1,0,...].

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

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

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

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

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

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

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

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

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

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

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

"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.

"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."

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

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

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]

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]

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.

C. Coker, Enumerating a class of lattice paths, Discrete Math., 271, 2003, 13-28.

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.

R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.

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]

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.

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.

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

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 421

E. Munarini and N. Z. Salvi, Binary strings without zigzags

N. J. A. Sloane, Illustration of a(6) = 17 (after Waterman, 1978).

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.

M. S. Waterman, Home Page (contains copies of his papers)

a(n+1)=a(n)+a(1)a(n-2)+a(2)a(n-3)+...+a(n-1)a(0).

G.f.: (1-x+x^2-sqrt(1-2x-x^2-2*x^3+x^4))/(2x^2).

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

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

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

Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos, Jul 20 2003

a(n)=A088518(2n)+A088518(2n+1)-A088518(2n+2). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 19 2003

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

a(n) = Sum_{k, 0<=k<=[n/2]}A131198(n-k,k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 06 2007

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]

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]

Contribution from Paul D. Hanna (pauldhanna(AT)juno.com), Jun 26 2009: (Start)

Let A(x)^m = Sum_{n>=0} a(n,m)*x^n, then

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

(End)

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.

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 ]

(PARI) a(n)=polcoeff((1-x+x^2-sqrt(1-2*x-x^2+x^3*(-2+x+O(x^n))))/2, n+2)

(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]

Second row of A064645.

Cf. A088518.

Sequence in context: A136671 A024557 A025241 this_sequence A085022 A003426 A087803

Adjacent sequences: A004145 A004146 A004147 this_sequence A004149 A004150 A004151

easy,nonn,nice

N. J. A. Sloane (njas(AT)research.att.com).