A023427 -id:A023427 - cp's OEIS frontend

A212364 Number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 5).

1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 23, 35, 57, 96, 161, 264, 425, 682, 1106, 1821, 3030, 5055, 8412, 13956, 23145, 38487, 64261, 107673, 180762, 303651, 510187, 857692, 1443597, 2433495, 4108299, 6943862, 11746362, 19883655, 33681015, 57096874, 96874214

Offset: 0

Alois P. Heinz, May 10 2012

nonn

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(5) = 1: UDUDUDUDUD.
a(6) = 2: UDUDUDUDUDUD, UUUUUUDDDDDD.
a(7) = 4: UDUDUDUDUDUDUD, UDUUUUUUDDDDDD, UUUUUUDDDDDDUD, UUUUUUDUDDDDDD.
a(8) = 7: UDUDUDUDUDUDUDUD, UDUDUUUUUUDDDDDD, UDUUUUUUDDDDDDUD, UDUUUUUUDUDDDDDD, UUUUUUDDDDDDUDUD, UUUUUUDUDDDDDDUD, UUUUUUDUDUDDDDDD.

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

Column k=5 of A212363.

Cf. A023432 (m=3), A023427 (m=4), this sequence (m=5), A212386(m=6).

a:= proc(n) option remember;
      `if`(n=0, 1, a(n-1) +add(a(k)*a(n-5-k), k=1..n-5))
    end:
seq(a(n), n=0..50);
# second Maple program:
a:= n-> coeff(series(RootOf(A=1+A*(x-x^5*(1-A)), A), x, n+1), x, n):
seq(a(n), n=0..50);

CoefficientList[Series[(1-x+x^5-Sqrt[-4*x^5+(1-x+x^5)^2])/(2*x^5),{x,0,20}],x] (* Vaclav Kotesovec, Mar 20 2014 *)

G.f. satisfies: A(x) = 1+A(x)*(x-x^5*(1-A(x))).
a(n) = a(n-1) + Sum_{k=1..n-5} a(k)*a(n-5-k) if n>0; a(0) = 1.
Recurrence: (n+5)*a(n) = (2*n+7)*a(n-1) - (n+2)*a(n-2) + (2*n-5)*a(n-5) + 2*(n-4)*a(n-6) - (n-10)*a(n-10). - Vaclav Kotesovec, Mar 20 2014
a(n) = Sum_{k=0..(n-1)/4} C(n-4*k,k)*C(n-4*k,k+1)/(n-4*k) for n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019

A212363 Number A(n,k) of Dyck n-paths all of whose ascents and descents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 14, 1, 1, 1, 1, 1, 4, 42, 1, 1, 1, 1, 1, 2, 8, 132, 1, 1, 1, 1, 1, 1, 4, 17, 429, 1, 1, 1, 1, 1, 1, 2, 7, 37, 1430, 1, 1, 1, 1, 1, 1, 1, 4, 12, 82, 4862, 1, 1, 1, 1, 1, 1, 1, 2, 7, 22, 185, 16796, 1

Offset: 0

Alois P. Heinz, May 10 2012

			A(3,0) = 1: UDUDUD.
A(3,1) = 5: UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD.
A(4,2) = 4: UDUDUDUD, UDUUUDDD, UUUDDDUD, UUUDUDDD.
A(5,2) = 8: UDUDUDUDUD, UDUDUUUDDD, UDUUUDDDUD, UDUUUDUDDD, UUUDDDUDUD, UUUDUDDDUD, UUUDUDUDDD, UUUUUDDDDD.
A(5,3) = 4: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDUDDDD.
Square array A(n,k) begins:
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   2,  1,  1,  1,  1,  1,  1, ...
  1,   5,  2,  1,  1,  1,  1,  1, ...
  1,  14,  4,  2,  1,  1,  1,  1, ...
  1,  42,  8,  4,  2,  1,  1,  1, ...
  1, 132, 17,  7,  4,  2,  1,  1, ...
  1, 429, 37, 12,  7,  4,  2,  1, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-10 give: A000012, A000108, A004148, A023432, A023427, A212364, A212365, A212366, A212367, A212368, A212369.

A:= proc(n, k) option remember;
      `if`(k=0, 1, `if`(n=0, 1, A(n-1, k)
                   +add(A(j, k)*A(n-k-j, k), j=1..n-k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);
# second Maple program:
A:= (n, k)-> `if`(k=0, 1, coeff(series(RootOf(
              A||k=1+A||k*(x-x^k*(1-A||k)), A||k), x, n+1), x, n)):
seq(seq(A(n, d-n), n=0..d), d=0..15);

A[n_, k_] := A[n, k] = If[k == 0, 1, If[n == 0, 1, A[n-1, k] + Sum[A[j, k]*A[n-k-j, k], {j, 1, n-k}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Jan 15 2014, translated from first Maple program *)

G.f. of column k>0 satisfies: A_k(x) = 1+A_k(x)*(x-x^k*(1-A_k(x))), g.f. of column k=0: A_0(x) = 1/(1-x).
A(n,k) = A(n-1,k) + Sum_{j=1..n-k} A(j,k)*A(n-k-j,k) for n,k>0; A(n,0) = A(0,k) = 1.
G.f. of column k > 0: (1 - x + x^k - sqrt((1 - x + x^k)^2 - 4*x^k)) / (2*x^k). - Vaclav Kotesovec, Sep 02 2014

A202849 Number of secondary structures of size n having no stacks of even length.

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 14, 31, 66, 141, 313, 702, 1577, 3581, 8207, 18903, 43770, 101903, 238282, 559322, 1317717, 3114676, 7383914, 17552857, 41831618, 99923471, 239200459, 573750288, 1378763083, 3319005743, 8002573350, 19324601494, 46731582653, 113160019865

Offset: 0

Emeric Deutsch, Dec 26 2011

nonn

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

			a(5)=7; 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; only the last one has stacks of even length.

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. A202845, A202846, A023427, A202848

f := z^2/(1-z^4): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 37)): seq(coeff(Gser, z, n), n = 0 .. 33);

G.f.: G=G(z) satisfies G = 1+zG +fG(G-1)/(1+f), where f = z^2/(1-z^4).
a(n) = A202848(n,0).
D-finite with recurrence (n+2)*a(n) +(-2*n-1)*a(n-1) +(n-1)*a(n-2) +3*(-2*n+5)*a(n-3) +(-n+7)*a(n-6) +3*(2*n-17)*a(n-7) +(-n+10)*a(n-8) +(-2*n+23)*a(n-9) +(n-13)*a(n-10)=0. - R. J. Mathar, Jul 26 2022

A365727 G.f. satisfies A(x) = 1 + x^4A(x)(1 + x*A(x)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 0, 0, 1, 3, 2, 0, 1, 6, 10, 5, 1, 10, 30, 35, 15, 15, 70, 140, 127, 63, 140, 420, 631, 490, 384, 1050, 2311, 2808, 2136, 2739, 6931, 12057, 12672, 11055, 19449, 42097, 61050, 60060, 66353, 131054, 241670, 306735, 308881, 428792, 835614, 1337765

Offset: 0

Seiichi Manyama, Sep 17 2023

nonn

Cf. A365728, A365729, A365730, A365731.

Cf. A023427.

a(n) = sum(k=0, n\4, binomial(k, n-4*k)*binomial(n-3*k+1, k)/(n-3*k+1));

a(n) = Sum_{k=0..floor(n/4)} binomial(k,n-4*k) * binomial(n-3*k+1,k) / (n-3*k+1).

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

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

A365696 G.f. satisfies A(x) = 1 + x^4A(x)^2 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 3, 6, 10, 15, 26, 49, 92, 165, 294, 535, 994, 1852, 3437, 6379, 11905, 22344, 42058, 79260, 149601, 283038, 536806, 1020066, 1941317, 3699922, 7062308, 13500402, 25842489, 49528164, 95031920, 182545222, 351023451, 675678911, 1301838177

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A023427, A215341, A215342, A357308, A365697.

Cf. A112805.

CoefficientList[Series[(1 + x - Sqrt[1 - 2*x + x^2 - 4*x^4])/(2*x*(1 + x^3)), {x, 0, 40}], x] (* Vaclav Kotesovec, Sep 26 2023 *)

a(n) = sum(k=0, n\4, binomial(n-3*k-1, n-4*k)*binomial(n-2*k+1, k)/(n-2*k+1));

a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k-1,n-4*k) * binomial(n-2*k+1,k) / (n-2*k+1).
From Vaclav Kotesovec, Sep 26 2023: (Start)
G.f.: (1 + x - sqrt(1 - 2*x + x^2 - 4*x^4)) / (2*x*(1 + x^3)).
a(n) ~ 2^(n + 3/2) / (sqrt(Pi) * 3^(3/2) * n^(3/2)). (End)

A365697 G.f. satisfies A(x) = 1 + x^4A(x)^3 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 4, 8, 13, 19, 38, 79, 153, 273, 509, 999, 1979, 3818, 7331, 14279, 28189, 55599, 109275, 215165, 426093, 846638, 1683215, 3348212, 6673679, 13333171, 26679522, 53437369, 107151335, 215154204, 432586412, 870678377, 1754094266

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A023427, A215341, A215342, A357308, A365696.

Cf. A365245.

a(n) = sum(k=0, n\4, binomial(n-3*k-1, n-4*k)*binomial(n-k+1, k)/(n-k+1));

a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k-1,n-4*k) * binomial(n-k+1,k) / (n-k+1).

A216116 G.f. satisfies: A(x) = (1 + xA(x)) (1 + x^4*A(x)).

Original entry on oeis.org

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, 1240963218

Offset: 0

Paul D. Hanna, Oct 29 2012

nonn

			A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 11*x^7 + 17*x^8 + 28*x^9 +...
The logarithm of the g.f. equals the series:
log(A(x)) = (1 + x^3)*x +
(1 + 2^2*x^3 + x^6)*x^2/2 +
(1 + 3^2*x^3 + 3^2*x^6 + x^9)*x^3/3 +
(1 + 4^2*x^3 + 6^2*x^6 + 4^2*x^9 + x^12)*x^4/4 +
(1 + 5^2*x^3 + 10^2*x^6 + 10^2*x^9 + 5^2*x^12 + x^15)*x^5/5 +
(1 + 6^2*x^3 + 15^2*x^6 + 20^2*x^9 + 15^2*x^12 + 6^2*x^15 + x^18)*x^6/6 +...

Cf. A023427, A023432, A004148.

{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)}

{a(n)=polcoeff(exp(sum(m=1, n+1, sum(j=0, m, binomial(m, j)^2*(x+x*O(x^n))^(3*j))*x^m/m)), n)}

{a(n)=polcoeff(((1-x-x^4) - sqrt((1-x-x^4)^2 - 4*x^5 +x^6*O(x^n)))/(2*x^5), n)}
for(n=0,45,print1(a(n),", "))

G.f.: A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * x^(3*k) ).
G.f.: A(x) = ((1-x-x^4) - sqrt((1-x-x^4)^2 - 4*x^5))/(2*x^5).
a(n) = A023427(n+1) for n>=0.

cp's OEIS Frontend

A212364 Number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 5).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212363 Number A(n,k) of Dyck n-paths all of whose ascents and descents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A202849 Number of secondary structures of size n having no stacks of even length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A365727 G.f. satisfies A(x) = 1 + x^4*A(x)*(1 + x*A(x)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

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

A365696 G.f. satisfies A(x) = 1 + x^4*A(x)^2 / (1 - x*A(x)).

Views

Author

Keywords

Crossrefs

A365727 G.f. satisfies A(x) = 1 + x^4A(x)(1 + x*A(x)).

A365696 G.f. satisfies A(x) = 1 + x^4A(x)^2 / (1 - xA(x)).

A365697 G.f. satisfies A(x) = 1 + x^4A(x)^3 / (1 - xA(x)).

A216116 G.f. satisfies: A(x) = (1 + xA(x)) (1 + x^4*A(x)).