A004148 -id:A004148 - cp's OEIS frontend

A190167 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n having a total of k (1,0)-steps at levels 1,3,5,... .

1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 2, 1, 4, 6, 4, 2, 1, 7, 12, 10, 5, 2, 1, 12, 24, 23, 14, 6, 2, 1, 21, 48, 52, 36, 18, 7, 2, 1, 38, 96, 115, 90, 51, 22, 8, 2, 1, 70, 193, 254, 217, 138, 68, 26, 9, 2, 1, 130, 388, 559, 522, 358, 196, 87, 30, 10, 2, 1, 243, 782, 1220, 1240, 926, 542, 264, 108, 34, 11, 2, 1

Offset: 0

Emeric Deutsch, May 06 2011

Row n has n-1 entries (n>=3).
Sum of entries in row n is A004148(n) (the RNA secondary structure numbers).
T(n,0)=A190168(n).
Sum(kT(n,k),k>=0)=A190169(n).
The trivariate g.f. H(t,s,z), where t (s) marks (1,0)-steps at even (odd) levels and z marks length, satisfies
z^2(1-tz+z^2)H^2-(1-tz+z^2)(1-sz+z^2)H+1-sz+z^2=0.

			T(5,2)=2 because we have huh'h'd and uh'h'dh, where u=(1,1), h=(1,0), d=(1,-1) (the odd-level h-steps are marked).
Triangle starts:
1;
1;
1;
1,1;
1,2,1;
2,3,2,1;
4,6,4,2,1;
7,12,10,5,2,1;

Cf. A004148, A190164, A190168, A190169

eq:=z^2*(1-z+z^2)*G^2-(1-z+z^2)*(1-s*z+z^2)*G+1-s*z+z^2 = 0: g:= RootOf(eq, G): Gser:= simplify(series(g, z = 0, 17)): for n from 0 to 13 do P[n] := sort(expand(coeff(Gser, z, n))) end do: 1; 1; for n from 0 to 13 do seq(coeff(P[n], s, k), k = 0 .. n-2) end do; # yields sequence in triangular form

G.f. = G = G(s,z) satisfies the equation z^2*(1-z+z^2)G^2-(1-z+z^2)(1-sz+z^2)G+1-sz+z^2=0.

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

A247290 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having k uhd strings.

Original entry on oeis.org

1, 1, 2, 4, 7, 1, 15, 2, 32, 5, 69, 13, 154, 30, 1, 346, 74, 3, 786, 183, 9, 1806, 449, 28, 4180, 1114, 78, 1, 9745, 2767, 219, 4, 22865, 6882, 611, 14, 53938, 17170, 1674, 50, 127865, 42906, 4569, 161, 1, 304447, 107392, 12398, 506, 5, 727733, 269237, 33450, 1564, 20

Offset: 0

Emeric Deutsch, Sep 16 2014

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2,  u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.
Row n contains 1 + floor(n/4) entries.
Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).
T(n,0) = A247291(n).
Sum(k*T(n,k), k=0..n) = A110320(n-3) (n>=3)

			T(5,1)=2 because we have huhd and uhdh.
Triangle starts:
1;
1;
2;
4;
7,1;
15,2;

Alois P. Heinz, Rows n = 0..300, 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, A110320, A247291, A247292, A247294.

eq := G = 1+z*G+z^2*G+z^3*(G-z+t*z)*G: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 25)): 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 .. floor((1/4)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y, t) option remember; `if`(y<0 or y>n, 0, `if`(n=0, 1,
      expand(b(n-1, y, `if`(t=1, 2, 0))+`if`(n>1, b(n-2, y, 0)+
      b(n-2, y+1, 1), 0)+b(n-1, y-1, 0)*`if`(t=2, x, 1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..20);  # Alois P. Heinz, Sep 16 2014

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

G.f. G = G(t,z) satisfies G = 1 + z*G + z^2*G + z^3*G*(G - z + t*z).

A247292 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having k uHd strings.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 1, 35, 2, 77, 5, 172, 13, 391, 32, 899, 78, 1, 2085, 195, 3, 4877, 487, 9, 11490, 1217, 28, 27236, 3055, 81, 64916, 7687, 228, 1, 155483, 19374, 641, 4, 374027, 48925, 1782, 14, 903286, 123760, 4908, 50, 2189219, 313512, 13451, 165, 5322965, 795263, 36690, 522, 1

Offset: 0

Emeric Deutsch, Sep 16 2014

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.
Row n contains 1 + floor(n/5) entries.
Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).
T(n,0) = A247293(n).
Sum(k*T(n,k), k=0..n) = A110320(n-4) (n>=4).

			T(6,1)=2 because we have uHdh and huHd.
Triangle starts:
1;
1;
2;
4;
8;
16,1;
35,2;

Alois P. Heinz, Rows n = 0..320, 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, A110320, A247290, A247293, A247294.

eq := G = 1+z*G+z^2*G+z^3*(G-z^2+t*z^2)*G: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 25)): 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 .. floor((1/5)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y, t) option remember; `if`(y<0 or y>n, 0, `if`(n=0, 1,
      expand(b(n-1, y, 0)+`if`(n>1, b(n-2, y, `if`(t=1, 2, 0))+
      b(n-2, y+1, 1), 0)+b(n-1, y-1, 0)*`if`(t=2, x, 1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..20);  # Alois P. Heinz, Sep 16 2014

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

G.f. G = G(t,z) satisfies G = 1 + z*G + z^2*G + z^3*G*(G - z^2 + t*z^2).

A247293 Number of weighted lattice paths B(n) having no uHd strings.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 35, 77, 172, 391, 899, 2085, 4877, 11490, 27236, 64916, 155483, 374027, 903286, 2189219, 5322965, 12980660, 31740404, 77804885, 191160040, 470662449, 1161123461, 2869754099, 7104856781, 17618234456, 43754467510, 108816781175

Offset: 0

Emeric Deutsch, Sep 16 2014

nonn

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.

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

			a(6)=35 because among the 37 (=A004148(7)) members of B(6) only huHd and uHdh contain uHd.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
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, A247291, A247292, A247295.

eq := G = 1+z*G+z^2*G+z^3*(G-z^2)*G: G := RootOf(eq, G): Gser := series(G, z = 0, 37): seq(coeff(Gser, z, n), n = 0 .. 35);
# second Maple program:
b:= proc(n, y, t) option remember; `if`(y<0 or y>n or t=3, 0,
      `if`(n=0, 1, b(n-1, y, 0)+`if`(n>1, b(n-2, y, `if`(t=1,
      2, 0))+b(n-2, y+1, 1), 0)+b(n-1, y-1, `if`(t=2, 3, 0))))
    end:
a:= n-> b(n, 0$2):
seq(T(n), n=0..40);  # Alois P. Heinz, Sep 16 2014

b[n_, y_, t_] := b[n, y, t] = If[y<0 || y>n || t == 3, 0, If[n == 0, 1, b[n-1, y, 0] + If[n>1, b[n-2, y, If[t == 1, 2, 0]] + b[n-2, y+1, 1], 0] + b[n-1, y-1, If[t == 2, 3, 0]]]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

G.f. G = G(z) satisfies G = 1 + z*G + z^2*G + z^3*G*(G - z^2).

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

A247295 Number of weighted lattice paths B(n) having no uhd and no uHd strings.

Original entry on oeis.org

1, 1, 2, 4, 7, 14, 30, 64, 141, 316, 713, 1626, 3740, 8659, 20176, 47274, 111302, 263201, 624860, 1488736, 3558412, 8530533, 20505468, 49413242, 119347708, 288873639, 700582008, 1702190653, 4142880297, 10099352082, 24656876772, 60283224645, 147581756005

Offset: 0

Emeric Deutsch, Sep 16 2014

nonn

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.

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

			a(6)=30 because among the 37 (=A004148(7)) members of B(6) only uhdhh, huhdh, hhuhd, Huhd, uhdH, uHdh, and huHd contain uhd or uHd (or both).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
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, A247291, A247293, A247294.

eq := G = 1+z*G+z^2*G+z^3*(G-z-z^2)*G: G := RootOf(eq, G): Gser := series(G, z = 0, 37): seq(coeff(Gser, z, n), n = 0 .. 35);
# second Maple program:
b:= proc(n, y, t) option remember; `if`(y<0 or y>n or t=3, 0,
      `if`(n=0, 1, b(n-1, y-1, `if`(t=2, 3, 0))+b(n-1, y,
      `if`(t=1, 2, 0))+`if`(n>1, b(n-2, y, `if`(t=1, 2, 0))+
       b(n-2, y+1, 1), 0)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 16 2014

b[n_, y_, t_] := b[n, y, t] = If[y<0 || y>n || t == 3, 0, If[n == 0, 1, b[n-1, y-1, If[t == 2, 3, 0]] + b[n-1, y, If[t == 1, 2, 0]] + If[n>1, b[n-2, y, If[t == 1, 2, 0]] + b[n-2, y+1, 1], 0]]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

G.f. G = G(z) satisfies G = 1 + z*G + z^2*G + z^3*G*(G - z- z^2 ).

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

A097777 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k U H^j Us for some j>0, where U=(1,1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 16, 1, 32, 5, 65, 17, 134, 50, 1, 280, 136, 7, 592, 355, 31, 1264, 904, 114, 1, 2722, 2264, 378, 9, 5906, 5604, 1176, 49, 12900, 13752, 3504, 215, 1, 28344, 33530, 10112, 835, 11, 62608, 81358, 28468, 2997, 71, 138949, 196688, 78576, 10173, 361, 1

Offset: 0

Emeric Deutsch, Sep 11 2004

Row n contains floor(n/3) entries (n>=3).
Row sums are the RNA secondary structure numbers (A004148).
T(n,0)=A098051(n).
Sum(k*T(n,k), k>=0)=A187257(n).

			Triangle starts:
  1;
  1;
  1;
  2;
  4;
  8;
  16,1;
  32,5;
  65,17;
  134,50,1;
  280,136,7;
  ...
Row n has floor(n/3) terms, n>=3.
T(7,1)=5 because we have H(UHU)HDD, (UHU)HHDD, (UHU)HDHD, (UHU)HDDH and (UHHU)HDD, where U=(1,1), H=(1,0) and D=(1,-1); the U H^j U's are shown between parentheses.

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.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08; Sem. Loth. Comb. B08l (1984) 79-86.

Cf. A004148, A098051, A187257

eq := G = 1+z*G+z^2*G*(G-1+(t-1)*(z*G-z/(1-z))): g := RootOf(eq, G): gser := simplify(series(g, z = 0, 23)): for n from 0 to 18 do P[n] := sort(coeff(gser, z, n)) end do: 1; 1; 1; for n from 3 to 18 do seq(coeff(P[n], t, k), k = 0 .. floor((1/3)*n)-1) end do; # yields sequence in triangular form

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

The generating function H=H(t,z) relative to the number of subwords of the form UH^bU for a fixed b>=1 satisfies H = 1+zH+z^2*H[H-1+(t-1)z^b*(H-1-zH)].

A097885 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k valleys (n>=0, 0<=k<=floor(n/2)-1; a valley is a downstep followed by an upstep).

Original entry on oeis.org

1, 1, 2, 4, 8, 1, 17, 4, 37, 13, 1, 82, 40, 5, 185, 116, 21, 1, 423, 326, 80, 6, 978, 899, 279, 31, 1, 2283, 2444, 924, 140, 7, 5373, 6578, 2948, 568, 43, 1, 12735, 17576, 9136, 2156, 224, 8, 30372, 46702, 27690, 7777, 1035, 57, 1, 72832, 123568, 82453, 26952, 4422

Offset: 0

Emeric Deutsch, Sep 02 2004

Also, triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k double rises (i.e. UU's, where U=(1,1)). E.g. T(5,1)=4 counts HUUDD, UUDDH, UUHDD and UUDHD, where U=(1,1), H=(1,0) and D=(1,-1).

Row sums are the Motzkin numbers (A001006). Column 0 gives A004148.

			Triangle starts:
   1;
   1;
   2;
   4;
   8,  1;
  17,  4;
  37, 13, 1;
  ...
Row n (n>=2) has floor(n/2) terms.
T(5,1)=4 counts HU(DU)D, U(DU)DH, U(DU)HD and UH(DU)D (here U=(1,1), H=(1,0) and D=(1,-1); valleys are shown between parentheses).

Alois P. Heinz, Rows n = 0..300, flattened

Cf. A001006, A004148, A097860.

eq:=G=1+z*G+z^2*G*(t*(G-1-z*G)+1+z*G): sol:=solve(eq,G): Gser:=simplify(series(sol[1],z=0,15)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(coeff(Gser,z^n)) od: 1,1,seq(seq(coeff(t*P[n],t^k),k=1..floor(n/2)),n=0..12);
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, b(x-1, y, 1)+b(x-1, y-1, z)+
            expand(b(x-1, y+1, 1)*t)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Oct 23 2019

(CoefficientList[#, t]& ) /@ CoefficientList[(-(t z^2) + Sqrt[((t-1) z^2 - z + 1)^2 + 4 z^2 (z t - z - t)] + z^2 + z - 1)/(2 z^2 (z t - z - t)) + O[z]^16, z] // Flatten (* Jean-François Alcover, Oct 23 2019 *)

G.f. G=G(t, z) satisfies z^2*(t+z-tz)G^2-(1-z-z^2+tz^2)*G+1=0.

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 16 2007

A098083 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k DHH...HU's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 17, 36, 1, 77, 5, 167, 18, 365, 58, 805, 172, 1, 1790, 486, 7, 4008, 1331, 34, 9033, 3561, 141, 20477, 9370, 524, 1, 46663, 24350, 1810, 9, 106843, 62674, 5930, 55, 245691, 160126, 18652, 279, 567194, 406732, 56832, 1245, 1, 1314086, 1028360

Offset: 0

Emeric Deutsch, Sep 13 2004

Row n >= 3 has ceiling((n-2)/4) terms.
Row sums yield the RNA secondary structure numbers (A004148).
T(n,0) = A190162(n).
Sum_{k>=0} k*T(n,k) = A190163(n).

			Triangle starts:
    1;
    1;
    1;
    2;
    4;
    8;
   17;
   36,  1;
   77,  5;
  167, 18
T(8,1)=5 because we have UH(DHU)HHD, HUH(DHU)HD, UH(DHHU)HD, UH(DHU)HDH and UHH(DHU)HD (the required subwords are shown between parentheses).

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.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

Cf. A004148.

eq := G = 1+z*G+z^2*(G-1)*(G-(1-t)*z*(G-1-z*G)/(1-z)): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 23)): for n from 0 to 20 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 20 do seq(coeff(P[n], t, j), j = 0 .. degree(P[n])) end do; # yields sequence in triangular form

G.f. = G = G(t, z) satisfies G = 1 + z*G + z^2*(G-1)*(G - (1-t)*z*(G-z*G-1)/(1-z)).

A110319 Triangle read by rows: T(n,k) (1 <= k <= n) is number of RNA secondary structures of size n (i.e., with n nodes) having k blocks (an RNA secondary structure can be viewed as a restricted noncrossing partition).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 6, 1, 0, 0, 0, 6, 10, 1, 0, 0, 0, 1, 20, 15, 1, 0, 0, 0, 0, 10, 50, 21, 1, 0, 0, 0, 0, 1, 50, 105, 28, 1, 0, 0, 0, 0, 0, 15, 175, 196, 36, 1, 0, 0, 0, 0, 0, 1, 105, 490, 336, 45, 1, 0, 0, 0, 0, 0, 0, 21, 490, 1176, 540, 55, 1, 0, 0, 0, 0, 0, 0, 1, 196

Offset: 1

Emeric Deutsch, Jul 19 2005

Row sums yield the RNA secondary structure numbers (A004148).
Column sums yield the Catalan numbers (A000108).
A rearrangement of the Narayana numbers triangle (A001263).

			Triangle begins:
  1;
  0, 1;
  0, 1, 1;
  0, 0, 3, 1;
  0, 0, 1, 6,  1;
  0, 0, 0, 6, 10,  1;
  0, 0, 0, 1, 20, 15,   1;
  0, 0, 0, 0, 10, 50,  21,   1;
  0, 0, 0, 0,  1, 50, 105,  28,  1;
  0, 0, 0, 0,  0, 15, 175, 196, 36, 1;
  ...
T(5,4)=6 because we have 13/2/4/5, 14/2/3/5. 15/2/3/4, 1/24/3/5, 1/25/3/4 and 1/2/35/4.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Cf. A000108, A001263, A004148, A089732, A110320.

T:=(n,k)->(1/k)*binomial(k,n-k)*binomial(k,n-k+1): for n from 1 to 14 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

T[n_, k_] := (1/k)*Binomial[k, n - k]*Binomial[k, n - k + 1];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 06 2018, from Maple *)

T(n,k) = (1/k)*binomial(k, n-k)*binomial(k, n-k+1); \\ Andrew Howroyd, Feb 27 2018

Sum_{k=1..n} k*T(n,k) = A110320(n).
T(n,k) = (1/k)*binomial(k, n-k)*binomial(k, n-k+1).
G.f.: (1 - tz - tz^2 - sqrt(1 - 2tz - 2tz^2 + t^2*z^2 - 2t^2*z^3 + t^2*z^4))/(2tz^2).

cp's OEIS Frontend

A190167 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n having a total of k (1,0)-steps at levels 1,3,5,... .

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

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

A247290 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having k uhd strings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A247292 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having k uHd strings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A247293 Number of weighted lattice paths B(n) having no uHd strings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A247295 Number of weighted lattice paths B(n) having no uhd and no uHd strings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A097777 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k U H^j Us for some j>0, where U=(1,1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple