A202849 -id:A202849 - cp's OEIS frontend

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

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

Offset: 0

Olivier Gérard

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

			(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

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.

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

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

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

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

{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

{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

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

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

A202845 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of odd length (n>=0, k>=0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 6, 4, 10, 3, 7, 16, 14, 11, 30, 40, 1, 17, 62, 90, 16, 28, 126, 184, 85, 49, 241, 384, 295, 9, 87, 444, 839, 808, 105, 152, 820, 1845, 1960, 594, 2, 262, 1547, 3938, 4581, 2331, 76, 453, 2957, 8134, 10731, 7326, 771, 794, 5636, 16529, 25110, 20204, 4529, 30

Offset: 0

Emeric Deutsch, Dec 26 2011

For "secondary structure" and "stack" see the Hofacker et al. reference, p. 209.
Sum of entries in row n is A004148 (the secondary structure numbers).
Sum(k*T(n,k), k>=0)=A202846(n).
T(n,0)=A023427(n).

			Row 5 is 2,6: representing unpaired vertices by v and arcs by AA, BB, etc., the 8 (= A004148(5)) secondary structures of size 5 are vvvvv, ABVBA, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv; except for the first two, each has 1 stack of length 1.
Triangle starts:
1;
1;
1;
1,1;
1,3;
2,6;
4,10,3;
7,16,14;

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.

Cf. A004148, A202846, A202848, A202849,

f := (t*z^2+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, 20)): for n from 0 to 16 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 16 do seq(coeff(P[n], t, k), k = 0 .. degree(P[n])) end do; # yields sequence in triangular form

G.f.: G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G-1), where f = (tz^2 + z^4)/(1-z^4).

The multivariate g.f. H(z, t[1], t[2], ...) of secondary structures with respect to size (marked by z) and number of stacks of length j (marked by t[j]) satisfies H = 1 + zH + (f/(1 + f))H(H-1), where f = t[1]z^2 + t[2]z^4 + t[3]z^6 + ... .

A202846 Number of stacks of odd length in all 2ndary structures of size n.

Original entry on oeis.org

0, 0, 0, 1, 3, 6, 16, 44, 113, 290, 749, 1930, 4966, 12776, 32870, 84577, 217665, 560328, 1442893, 3716837, 9577805, 24689612, 63667585, 164239124, 423824628, 1094065998, 2825169786, 7297681867, 18856458451, 48737762624, 126007604078, 325873570924, 842982118807

Offset: 0

Emeric Deutsch, Dec 26 2011

nonn

For "secondary structure" and "stack" see the Hofacker et al. reference, p. 209.

Number of stacks of even length in all 2ndary structures of size n+2.

			a(5)=6: 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.

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.

Cf. A004148, A171854, A202845, A023427, A202848, A202849

g := z^2*(1-z^2)*S*(S-1)/((1+z^2)*(1-z+z^2-2*z^2*S)): S := ((1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))*1/2)/z^2: gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 32);

a(n) = Sum(k*A202845(n,k), k>=0).
a(n) = Sum(k*A202848(n+2,k), k>=0).
a(n)+a(n-2) = A171854(n) (n>=2).
G.f.: g(z) = z^2*(1-z^2)^2*S(S - 1)/[(1+z^2)(1 - z + z^2 -2*z^2*S)], where S is defined by S = 1 + z*S + z^2*S(S-1) (the g.f. of the secondary structure numbers A004148).
Conjecture D-finite with recurrence +(n+2)*(13230*n^2-96611*n+147133)*a(n) +(-44206*n^3+292903*n^2-261197*n-341332)*a(n-1) +2*(17746*n^3-141629*n^2+231187*n+123600)*a(n-2) +2*(-26460*n^3+157889*n^2-64195*n-381418)*a(n-3) +2*(35492*n^3-320849*n^2+745453*n-240088)*a(n-4) +2*(-13230*n^3+98869*n^2-160610*n-79637)*a(n-5) +(48722*n^3-428591*n^2+982443*n-433110)*a(n-6) -(n-6)*(17746*n^2-68387*n+43705)*a(n-7)=0. - R. J. Mathar, Jul 26 2022

A202848 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of even length (n>=0, k>=0).

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 1, 14, 3, 31, 6, 66, 16, 141, 44, 313, 107, 3, 702, 262, 14, 1577, 663, 43, 3581, 1654, 138, 8207, 4091, 436, 1, 18903, 10178, 1275, 16, 43770, 25339, 3638, 85, 101903, 62952, 10316, 331, 238282, 156495, 28743, 1228, 559322, 389374, 78979, 4320, 9

Offset: 0

Emeric Deutsch, Dec 26 2011

For "secondary structure" and "stack" see the Hofacker et al. reference, p. 209.
Sum of entries in row n is A004148 (the secondary structure numbers).
Sum(k*T(n,k), k>=0) = A202846(n-2).
T(n,0) = A202849(n).

			Row 5 is 7,1: 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; the last one has 1 stack of length 2.
Triangle starts:
1;
1;
1;
2;
4;
7,1;
14,3;
31,6;

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.

Cf. A004145, A202846, A023427, A202849,

f := (z^2+t*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, 25)): for n from 0 to 19 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 19 do seq(coeff(P[n], t, k), k = 0 .. degree(P[n])) end do; # yields sequence in triangular form

G.f.: G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G-1), where f = (z^2 + t*z^4)/(1-z^4).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A202845 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of odd length (n>=0, k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A202846 Number of stacks of odd length in all 2ndary structures of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A202848 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of even length (n>=0, k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula