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

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.

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

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

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)

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

njas