A004148 -id:A004148 - cp's OEIS frontend

A182053 G.f. satisfies: A(x) = (1+xA(x))(1+x^2A(x))(1+x^3*A(x)).

1, 1, 2, 5, 11, 26, 64, 159, 402, 1032, 2677, 7010, 18510, 49220, 131691, 354282, 957745, 2600382, 7088008, 19388719, 53207441, 146444424, 404151643, 1118132954, 3100540971, 8615945102, 23989662824, 66917894562, 186983937758, 523314016245, 1466807316032

Offset: 0

Paul D. Hanna, Apr 08 2012

nonn

			G.f.: A(x) = 1 + x + 2*x^2 + 5*x^3 + 11*x^4 + 26*x^5 + 64*x^6 + 159*x^7 +...
Related expansions:
A(x)^2 = 1 + 2*x + 5*x^2 + 14*x^3 + 36*x^4 + 94*x^5 + 249*x^6 + 660*x^7 +...
A(x)^3 = 1 + 3*x + 9*x^2 + 28*x^3 + 81*x^4 + 231*x^5 + 656*x^6 + 1848*x^7 +...
where A(x) = 1 + x*(1+x+x^2)*A(x) + x^3*(1+x+x^2)*A(x)^2 + x^6*A(x)^3.
The logarithm of the g.f. begins:
log(A(x)) = x + 3*x^2/2 + 10*x^3/3 + 23*x^4/4 + 61*x^5/5 + 168*x^6/6 + 456*x^7/7 + 1255*x^8/8 + 3493*x^9/9 + 9753*x^10/10 +...

Vaclav Kotesovec, Table of n, a(n) for n = 0..300

Cf. A004148.

{a(n)=local(A=1+x); for(i=1, n, A=(1+x*A)*(1+x^2*A)*(1+x^3*A)+x*O(x^n)); polcoeff(A, n)}
for(n=0,40,print1(a(n),", "))

Recurrence: 5*(n+2)*(n+3)*(8911*n^7 - 241946*n^6 + 2447725*n^5 - 11084372*n^4 + 19415458*n^3 + 1716316*n^2 - 23882064*n + 2130912)*a(n) = 3*(n+2)*(35644*n^8 - 914318*n^7 + 8350054*n^6 - 29810773*n^5 + 11813540*n^4 + 124863372*n^3 - 96624130*n^2 - 116648601*n + 36899532)*a(n-1) + (17822*n^9 - 448248*n^8 + 3870267*n^7 - 11783352*n^6 - 5744844*n^5 + 67908444*n^4 - 29523545*n^3 - 131900220*n^2 - 65428308*n - 24231312)*a(n-2) + (178220*n^9 - 4749810*n^8 + 45912714*n^7 - 180749091*n^6 + 117079677*n^5 + 903637509*n^4 - 1481741315*n^3 - 502308600*n^2 + 1275968592*n - 5383800)*a(n-3) - 3*(26733*n^9 - 752571*n^8 + 7896778*n^7 - 35859478*n^6 + 44913322*n^5 + 151779908*n^4 - 435106847*n^3 + 135598205*n^2 + 327138534*n - 194418504)*a(n-4) + (17822*n^9 - 528447*n^8 + 6031992*n^7 - 32027385*n^6 + 65161374*n^5 + 61817937*n^4 - 383729654*n^3 + 245358135*n^2 + 217471338*n - 55404648)*a(n-5) + 2*(17822*n^9 - 555180*n^8 + 6785304*n^7 - 40187787*n^6 + 104743872*n^5 + 17193252*n^4 - 685093274*n^3 + 1082675799*n^2 + 285222672*n - 1131441048)*a(n-6) - (17822*n^9 - 581913*n^8 + 7681743*n^7 - 51193035*n^6 + 163962759*n^5 - 87813864*n^4 - 868874108*n^3 + 1698086052*n^2 + 415801800*n - 1243151064)*a(n-7) - (35644*n^9 - 1217292*n^8 + 16363266*n^7 - 106473036*n^6 + 307618491*n^5 - 35551263*n^4 - 1688725327*n^3 + 2463079431*n^2 + 830567142*n - 2522003904)*a(n-8) + (n-8)*(35644*n^8 - 985606*n^7 + 10067008*n^6 - 43505557*n^5 + 43567930*n^4 + 201854264*n^3 - 417755448*n^2 - 116443773*n + 335593314)*a(n-9) - (n-9)*(n-8)*(8911*n^7 - 179569*n^6 + 1183180*n^5 - 2163052*n^4 - 4971815*n^3 + 14491649*n^2 + 4308780*n - 9489060)*a(n-10). - Vaclav Kotesovec, Mar 25 2014

a(n) ~ sqrt((s*(2-r-r^3*(s-1)+r^5*s))/(1+r+r^2+3*r^3*s))/ (2*sqrt(Pi)* n^(3/2)*r^(n+3/2)), where r = 0.34048516736982998257..., s = 3.7980384578075501949... are roots of the system of equations r + r^2 + r^3 + 2*r^3*s + 2*r^4*s + 2*r^5*s + 3*r^6*s^2 = 1, and (1 + r*s)*(1 + r^2*s)*(1 + r^3*s) = s. - Vaclav Kotesovec, Mar 25 2014

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 6, 4, 10, 3, 8, 15, 14, 14, 27, 40, 1, 23, 56, 90, 16, 38, 122, 178, 85, 65, 253, 356, 295, 9, 117, 494, 762, 805, 105, 214, 938, 1713, 1912, 594, 2, 391, 1783, 3828, 4326, 2331, 76, 708, 3456, 8265, 9882, 7290, 771, 1278, 6793, 17309, 23109, 19784, 4529, 30

Offset: 0

Emeric Deutsch, Dec 25 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)=A202839(n).
T(n,0)=A202840(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, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv, ABvBA; they have 0,1,1,1,1,1,1,0 stacks of length 1, respectively.
Triangle starts:
1;
1;
1;
1,1;
1,3;
2,6;
4,10,3;
8,15,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. A202839, A202840, A202841, A202842, A202843, A202844

f := (t-1)*z^2+z^2/(1-z^2): 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 = (t-1)z^2 + z^2/(1-z^2).

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

A202839 Number of stacks of length 1 in all 2ndary structures of size n.

Original entry on oeis.org

0, 0, 0, 1, 3, 6, 16, 43, 110, 284, 733, 1886, 4853, 12486, 32121, 82647, 212699, 547552, 1410023, 3632260, 9360140, 24129284, 62224692, 160522287, 414246823, 1069376386, 2761502201, 7133442743, 18432633823, 47643696626, 123182434292, 318575889057, 824125660356

Offset: 0

Emeric Deutsch, Dec 25 2011

nonn

For "secondary structure" and "stack" see the Hofacker et al. reference, p. 209.
Number of stacks of length 2 in all 2ndary structures of size n+2.
Number of stacks of length 3 in all 2ndary structures of size n+4.

			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 length 1, 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. A202838, A202840, A202841, A202842, A202843, A202844

g := z^2*(1-z^2)^2*S*(S-1)/(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);

CoefficientList[Series[-(1 - x^2)^2 * ((1 - x) + (-1 + 2*x + x^3) / Sqrt[(1 - 3*x + x^2) * (1 + x + x^2)]) / (2*x^2), {x, 0, 40}], x] (* Vaclav Kotesovec, May 29 2022 *)

a(n) = Sum(k*A202838(n,k), k>=0).
a(n) = Sum(k*A202841(n+2,k), k>=0).
a(n) = Sum(k*A202843(n+4,k), k>=0).
G.f.: g(z) = z^2*(1-z^2)^2*S(S - 1)/(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).
a(n) ~ 5^(3/4) * phi^(2*n-3) / (2*sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 29 2022
D-finite with recurrence -(n+2)*(406*n-3981)*a(n) +(2022*n^2-15917*n-13552)*a(n-1) +4*(-402*n^2+2594*n+593)*a(n-2) +4*(-605*n^2+7719*n-23415)*a(n-3) +4*(-203*n^2-527*n+15295)*a(n-4) +2*(804*n^2-8404*n+14555)*a(n-5) +(2826*n^2-42913*n+153174)*a(n-6) -(1210*n-6753)*(n-10)*a(n-7)=0. - R. J. Mathar, Jul 26 2022

A202840 Number of secondary structures of size n having no stacks of length 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 8, 14, 23, 38, 65, 117, 214, 391, 708, 1278, 2318, 4238, 7803, 14419, 26684, 49433, 91736, 170656, 318280, 594905, 1113868, 2088554, 3921505, 7373367, 13883045, 26174600, 49408932, 93372078, 176637791, 334491586, 634023965, 1202894908, 2284187117

Offset: 0

Emeric Deutsch, Dec 25 2011

nonn

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

a(n) = A202838(n,0).

			a(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 length 1, 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. A202838, A202839, A202841, A202842, A202843, A202844

f := z^4/(1-z^2): 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);

G.f. G=G(z) satisfies G = 1+zG +fG(G-1)/(1+f), where f = z^4/(1-z^2).

D-finite with recurrence +(n+4)*a(n) +(-2*n-5)*a(n-1) +(-n-1)*a(n-2) +2*(2*n-1)*a(n-3) +(-n+2)*a(n-4) +4*(-2*n+7)*a(n-5) +3*(n-5)*a(n-6) +3*(2*n-13)*a(n-7) +2*(-n+8)*a(n-8) +2*(-2*n+19)*a(n-9) +(n-11)*a(n-10)=0. - R. J. Mathar, Jul 26 2022

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

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 1, 14, 3, 31, 6, 66, 16, 142, 43, 316, 104, 3, 708, 256, 14, 1593, 647, 43, 3625, 1610, 138, 8314, 3990, 430, 1, 19165, 9944, 1247, 16, 44433, 24762, 3552, 85, 103557, 61574, 10040, 331, 242376, 153270, 27877, 1225, 569514, 381718, 76491, 4272, 9

Offset: 0

Emeric Deutsch, Dec 25 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).

			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; only the last one has a 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. A004148, A202838, A202839, A202840, A202842, A202843, A202844

f := (t-1)*z^4+z^2/(1-z^2): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 23)): 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

Sum(k*T(n,k), k>=0) = A202839(n-2).
T(n,0) = A202842(n).
G.f. G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G-1), where f = (t-1)z^4 + z^2/(1-z^2).
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 + ... .

A202842 Number of secondary structures of size n having no stacks of length 2.

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 14, 31, 66, 142, 316, 708, 1593, 3625, 8314, 19165, 44433, 103557, 242376, 569514, 1343099, 3177766, 7540845, 17943506, 42804078, 102345017, 245233366, 588785677, 1416247791, 3412495415, 8235829927, 19906780104, 48185131721, 116790380824, 283432579807

Offset: 0

Emeric Deutsch, Dec 25 2011

nonn

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

a(n) = A202841(n,0).

			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 a stack of length 2.

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. A202838, A202839, A202840, A202841, A202843, A202844

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

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

A202843 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of length 3.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 17, 36, 1, 79, 3, 179, 6, 407, 16, 935, 43, 2173, 110, 5089, 284, 12005, 727, 3, 28500, 1858, 14, 68022, 4767, 43, 163154, 12210, 138, 393060, 31255, 433, 950652, 80057, 1295, 2307454, 205088, 3804, 1, 5618906, 525534, 10985, 16, 13723145, 1347174, 31297, 85

Offset: 0

Emeric Deutsch, Dec 25 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) = A202839(n-4).
T(n,0) = A202844(n).

			Row 5 is 8: 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; none of them has stacks of length 3.
Triangle starts:
1;
1;
1;
2;
4;
8;
17;
36,1;
79,3;

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, A202838, A202839, A202840, A202841, A202842, A202844

f := (t-1)*z^6+z^2/(1-z^2): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 26)): for n from 0 to 22 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 22 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 = (t-1)z^6 + z^2/(1-z^2).

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

A202844 Number of secondary structures of size n having no stacks of length 3.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 17, 36, 79, 179, 407, 935, 2173, 5089, 12005, 28500, 68022, 163154, 393060, 950652, 2307454, 5618906, 13723145, 33607242, 82507764, 203028034, 500659653, 1237053269, 3062204227, 7593229687, 18858944533, 46909741893, 116848688876, 291449697298

Offset: 0

Emeric Deutsch, Dec 25 2011

nonn

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

			a(5)=8; 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; none of them has stacks of length 3.

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. A202838, A202839, A202840, A202841, A202842, A202843.

f := z^2*(1-z^4+z^6)/(1-z^2): 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+z^6)/(1-z^2).

a(n) = A202843(n,0).

A246177 Triangle read by rows: T(n,k) is the number of weighted lattice paths in B(n) such that the area between the x-axis and the path is k.

Original entry on oeis.org

1, 1, 2, 3, 1, 5, 2, 1, 8, 5, 3, 1, 13, 10, 8, 4, 2, 21, 20, 18, 12, 7, 3, 1, 34, 38, 39, 30, 22, 12, 7, 2, 1, 55, 71, 80, 70, 57, 39, 26, 14, 7, 3, 1, 89, 130, 160, 154, 138, 106, 81, 52, 34, 18, 10, 4, 2, 144, 235, 312, 327, 315, 267, 220, 163, 118, 78, 49, 28, 16, 7, 3, 1

Offset: 0

Emeric Deutsch, Aug 20 2014

The members of B(n) are paths of weight n that start at (0,0), end on but never go below the horizontal axis, and whose steps are of the following four kinds: an (1,0)-step with weight 1, an (1,0)-step with weight 2, a (1,1)-step with weight 2, and a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps.
Apparently, number of terms in row n is 1+floor(n^2/8).
Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).
T(n,0) = A000045(n+1) (the Fibonacci numbers).
T(n,1) = A001629(n-1) (n>=1).

			Row 3 is 3,1; indeed, B(3) consists of the paths hhh, hH, Hh, UD with areas 0,0,0,1, respectively.
Triangle starts:
   1;
   1;
   2;
   3,   1;
   5,   2,   1;
   8,   5,   3,   1;
  13,  10,   8,   4,   2;
  21,  20,  18,  12,   7,   3,  1;
  34,  38,  39,  30,  22,  12,  7,  2,  1;
  55,  71,  80,  70,  57,  39, 26, 14,  7,  3,  1;
  89, 130, 160, 154, 138, 106, 81, 52, 34, 18, 10, 4, 2;

Alois P. Heinz, Rows n = 0..65, flattened
M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Cf. A004148, A000045, A001629.

g := 1/(1-z-z^2-t*z^3*A[1]): for j to 15 do A[j] := 1/(1-t^j*z-t^j*z^2-t^(2*j+1)*z^3*A[j+1]) end do: gser := simplify(series(g, z = 0, 20)): for n from 0 to 17 do P[n] := sort(coeff(gser, z, n)) end do: for n from 0 to 17 do seq(coeff(P[n], t, j), j = 0 .. floor((1/8)*n^2)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0 or y>n, 0, `if`(n=0, 1,
      expand(b(n-1, y)*x^y +`if`(n>1, b(n-2, y)*x^y+b(n-2, y+1)*
      x^(y+1/2), 0) +b(n-1, y-1)*x^(y-1/2))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, Aug 20 2014

b[n_, y_] := b[n, y] = If[y<0 || y>n, 0, If[n == 0, 1, Expand[b[n-1, y]*x^y + If[n>1, b[n-2, y]*x^y + b[n-2, y+1]*x^(y+1/2), 0] + b[n-1, y-1]*x^(y-1/2)]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

The trivariate g.f. G=G(t,s,z), where t marks area, s marks length (=number of steps), and z marks weight, satisfies G = 1+szG+sz^2G+ts^2z^3G(t,ts,z)G. This follows at once from the fact that every nonempty path is of the form hC or HC or UCDC, where h denotes a (1,0)-step of weight 1, H denotes a (1,0)-step of weight 2, U denotes a (1,1)-step, D denotes a (1,-1)-step, and the C's denote paths, not necessarily the same. From the equation one can find G(t,s,z) as a continued fraction (the Maple program makes use of this).

A023421 Generalized Catalan Numbers x^2A(x)^2 -(1-x+x^2+x^3+x^4)A(x) + 1 =0.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 8, 16, 32, 65, 133, 274, 568, 1184, 2481, 5223, 11042, 23434, 49908, 106633, 228505, 490999, 1057683, 2283701, 4941502, 10713941, 23272929, 50642017, 110377543, 240944076, 526717211, 1152996206, 2527166334, 5545804784, 12184053993

Offset: 0

Olivier Gérard

Seiichi Manyama, Table of n, a(n) for n = 0..2795

Cf. A000108, A001006, A004148, A004149, A023422, A023423.

Fourth row of A064645.

A023421 := proc(n)
    option remember;
    if n = 0 then
        1;
    else
        procname(n-1)+add(procname(k)*procname(n-2-k), k=3..n-2) ;
    end if;
end proc: # R. J. Mathar, May 01 2015

a[0]=1; a[n_]:= a[n]=a[n-1] + Sum[a[k]*a[n-2-k], {k,3,n-2}]; Table[a[n], {n,0,30}] (* modified by G. C. Greubel, Jan 01 2018 *)

{a(n) = if(n==0,1, a(n-1) + sum(k=3,n-2, a(k)*a(n-k-2)))};
for(n=0,30, print1(a(n), ", ")) \\ G. C. Greubel, Jan 01 2018

G.f. A(x) satisfies: A(x) = (1 + x^2 * A(x)^2) / (1 - x + x^2 + x^3 + x^4). - Ilya Gutkovskiy, Jul 20 2021

D-finite with recurrence (n+2)*a(n) +(-2*n-1)*a(n-1) +(-n+1)*a(n-2) +(n-4)*a(n-4) +3*(n-7)*a(n-6) +(2*n-17)*a(n-7) +(n-10)*a(n-8)=0. - R. J. Mathar, Feb 03 2025

cp's OEIS Frontend

A182053 G.f. satisfies: A(x) = (1+x*A(x))*(1+x^2*A(x))*(1+x^3*A(x)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A202839 Number of stacks of length 1 in all 2ndary structures of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A202840 Number of secondary structures of size n having no stacks of length 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A202842 Number of secondary structures of size n having no stacks of length 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A202843 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of length 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A202844 Number of secondary structures of size n having no stacks of length 3.

Views

A182053 G.f. satisfies: A(x) = (1+xA(x))(1+x^2A(x))(1+x^3*A(x)).

A023421 Generalized Catalan Numbers x^2A(x)^2 -(1-x+x^2+x^3+x^4)A(x) + 1 =0.