login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023427 Number of Dyck n-paths with ascents and descents of length equal to 1 (mod 4). 8
1, 1, 1, 1, 1, 2, 4, 7, 11, 17, 28, 49, 87, 152, 262, 453, 794, 1408, 2507, 4462, 7943, 14179, 25415, 45713, 82398, 148731, 268859, 486890, 883411, 1605582, 2922259, 5325377, 9716564, 17750332, 32464980, 59443403, 108951953, 199886003, 367052947, 674620772 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

Number of secondary structures of size n having no stacks of odd length (see Hofacker et al., p. 209). - Emeric Deutsch, Dec 26 2011

a(n) is the number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 4).  The a(5) = 2 paths for n=5 are: UDUDUDUDUD, UUUUUDDDDD. - Alois P. Heinz, May 09 2012

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.

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

FORMULA

a(n) = A202845(n,0). A(x) satisfies A=1+x*A+f*A*(A-1)/(1+f), where f=x^4/(1-x^4). - Emeric Deutsch, Dec 26 2011

G.f.: A(x) = ((1-x+x^4) - sqrt((1-x+x^4)^2 - 4*x^4))/(2*x^4). - Paul D. Hanna, Oct 29 2012

G.f. satisfies: A(x) = 1 + x*A(x)/(1 - x^4*A(x)). - Paul D. Hanna, Oct 29 2012

G.f.: 1 + x*exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * x^(3*k) ). - Paul D. Hanna, Oct 29 2012

a(n) = A216116(n-1) for n>0.

Recurrence: (n+4)*a(n) = (2*n+5)*a(n-1) - (n+1)*a(n-2) + 2*(n-2)*a(n-4) + (2*n-7)*a(n-5) - (n-8)*a(n-8). - Vaclav Kotesovec, Sep 16 2013

a(n) ~ sqrt(-4*c^2-3*c^3+4-4*c)*(1+2*c-c^3)^n*(-5*c^3-3*c^2+9*c+10) / (2*n^(3/2)*sqrt(Pi)), where c = 1/2*sqrt((4+(155/2-3*sqrt(849)/2)^(1/3) +(155/2+3*sqrt(849)/2)^(1/3))/3) - 1/2*sqrt(8/3-1/3*(155/2-3*sqrt(849)/2)^(1/3) - 1/3*(155/2+3*sqrt(849)/2)^(1/3) + 2*sqrt(3/(4+(155/2-3*sqrt(849)/2)^(1/3) + (155/2+3*sqrt(849)/2)^(1/3)))) = 0.5248885986564... is the root of the equation c^4-2*c^2-c+1=0. - Vaclav Kotesovec, Sep 16 2013

a(n) = Sum_{k=0..(n-1)/3} C(n-3*k,k)*C(n-3*k,k+1)/(n-3*k), n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019

EXAMPLE

(5)=2; representing unpaired vertices by v and arcs by AA, BB, etc., the 8 (= A004148(5)) secondary structures of size 5 are vvvvv, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv, ABvBA; they have 0,1,1,1,1,1,1,0 stacks of odd length, respectively. - Emeric Deutsch, Dec 26 2011

MAPLE

f := z^4/(1-z^4): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 42)): seq(coeff(Gser, z, n), n = 0 .. 39); # Emeric Deutsch, Dec 26 2011

a:= proc(n) option remember;

      `if`(n=0, 1, a(n-1) +add(a(k)*a(n-4-k), k=1..n-4))

    end:

seq(a(n), n=0..50);  # Alois P. Heinz, May 09 2012

MATHEMATICA

Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-4-k ], {k, 1, n-4} ];

CoefficientList[Series[((1-x+x^4) - Sqrt[(1-x+x^4)^2 - 4*x^4)]/(2*x^4), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 16 2013 *)

PROG

(PARI) {a(n)=polcoeff(((1-x+x^4) - sqrt((1-x+x^4)^2 - 4*x^4 +x^5*O(x^n)))/(2*x^4), n)} \\ Paul D. Hanna, Oct 29 2012

(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1 + x*A/(1-x^4*A+x*O(x^n))); polcoeff(A, n)} \\ Paul D. Hanna, Oct 29 2012

(Maxima)

a(n):=if n=0 then 1 else sum(binomial(n-3*q, ((q)))*binomial((n-3*q), (q+1))/(n-3*q), q, 0, (n-1)/3); /* Vladimir Kruchinin, Jan 21 2019 */

CROSSREFS

Cf. A000108, A001006, A004148, A006318, A216116, A202845 - A202849.

Sequence in context: A023428 A093911 A152398 * A216116 A129929 A073738

Adjacent sequences:  A023424 A023425 A023426 * A023428 A023429 A023430

KEYWORD

nonn,easy

AUTHOR

Olivier Gérard

EXTENSIONS

New name, using a comment of Alois P. Heinz, from Peter Luschny, Jan 21 2019

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 11:32 EST 2021. Contains 341656 sequences. (Running on oeis4.)