login
The OEIS is supported by the many generous donors to the OEIS 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). 12

%I #57 Jun 27 2022 13:50:46

%S 1,1,1,1,1,2,4,7,11,17,28,49,87,152,262,453,794,1408,2507,4462,7943,

%T 14179,25415,45713,82398,148731,268859,486890,883411,1605582,2922259,

%U 5325377,9716564,17750332,32464980,59443403,108951953,199886003,367052947,674620772

%N Number of Dyck n-paths with ascents and descents of length equal to 1 (mod 4).

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

%C 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

%H Alois P. Heinz, <a href="/A023427/b023427.txt">Table of n, a(n) for n = 0..1000</a>

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

%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 (1979), 261-272.

%F 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

%F 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

%F G.f. satisfies: A(x) = 1 + x*A(x)/(1 - x^4*A(x)). - _Paul D. Hanna_, Oct 29 2012

%F 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

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

%F 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

%F 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

%F 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

%e (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

%p 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

%p a:= proc(n) option remember;

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

%p end:

%p seq(a(n), n=0..50); # _Alois P. Heinz_, May 09 2012

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

%t 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 *)

%o (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

%o (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

%o (Maxima)

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

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

%K nonn,easy

%O 0,6

%A _Olivier GĂ©rard_

%E New name, using a comment of _Alois P. Heinz_, from _Peter Luschny_, Jan 21 2019

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)