A004149 -id:A004149 - cp's OEIS frontend

A190172 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n having k UHD's; here U=(1,1), H=(1,0), and D=(1,-1).

1, 1, 1, 1, 1, 2, 2, 4, 4, 8, 8, 1, 16, 18, 3, 33, 40, 9, 69, 90, 25, 1, 146, 204, 69, 4, 312, 467, 183, 16, 673, 1074, 479, 56, 1, 1463, 2481, 1239, 185, 5, 3202, 5752, 3180, 576, 25, 7050, 13378, 8104, 1734, 105, 1, 15605, 31196, 20544, 5076, 405, 6, 34705, 72912, 51852, 14546, 1451, 36

Offset: 0

Emeric Deutsch, May 06 2011

Number of entries in row n is 1+floor(n/3).
Sum of entries in row n = A004148 (the RNA secondary structure numbers).
T(n,0)=A004149(n).
Sum(k*T(n,k),k>=0)=A110236(n-2) (n>=3).

			T(5,1)=4 because we have HHUHD, HUHDH, UHDH, and UUHDD.
Triangle starts:
1;
1;
1;
1,1;
2,2;
4,4;
8,8,1;
16,18,3;

Cf. A004148, A004149, A110236

eq := G = 1+z*G+z^2*G*(G-1-z+t*z): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 25)): 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, k), k = 0 .. floor((1/3)*n)) end do; # yields sequence in triangular form

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

A136018 Triangle read by rows: r(n,k) = g(n,n-k), where g(n,k) is the number of ideals of size k in a garland (or double fence) of order n (see A137278).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 3, 3, 1, 7, 6, 6, 4, 1, 15, 14, 12, 10, 5, 1, 33, 32, 27, 22, 15, 6, 1, 75, 72, 63, 50, 37, 21, 7, 1, 171, 164, 146, 118, 88, 58, 28, 8, 1, 391, 377, 338, 280, 212, 147, 86, 36, 9, 1, 899, 870, 786, 662, 514, 366, 234, 122, 45, 10, 1, 2077, 2014, 1834, 1564

Offset: 0

Emanuele Munarini, Mar 21 2008

Row n has n+1 terms.

T. S. Blyth, J. C. Varlet, Ockham algebras, Oxford Science Pub. 1994.
E. Munarini, Enumeration of order ideals of a garland, Ars Combin. 76 (2005), 185--192.

Emanuele Munarini, Mar 21 2008, Table of n, a(n) for n = 0..495

Recurrence: r(n+3,k+1) = r(n+2,k) + r(n+2,k+1) + r(n+2,k+2) - r(n+1,k+1) - r(n,k+1).

Riordan matrix: R = ( g(x), f(x) ), where g(x) = ( 1 - x^2 )/sqrt( 1 - 2 x - x^2 - x^4 + 2 x^5 + x^6 ) f(x) = ( 1 - x + x^2 + x^3 - sqrt( 1 - 2 x - x^2 - 3 x^4 + 2 x^5 + x^6 ) )/(2x) g(x) is the generating series for the central ideals c(n) = g(2n,n). f(x)/x is the generating series for sequence A004149.

A258709 Triangle of generalized Catalan numbers read by rows.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 9, 4, 2, 1, 1, 21, 8, 4, 2, 1, 1, 51, 17, 8, 4, 2, 1, 1, 127, 37, 16, 8, 4, 2, 1, 1, 323, 82, 33, 16, 8, 4, 2, 1, 1, 835, 185, 69, 32, 16, 8, 4, 2, 1, 1, 2188, 423, 146, 65, 32, 16, 8, 4, 2, 1, 1, 5798, 978, 312, 133, 64, 32, 16, 8, 4, 2, 1, 1

Offset: 0

N. J. A. Sloane, Jun 13 2015

			Triangle begins
1,
1,1,
2,1,1,
4,2,1,1,
9,4,2,1,1,
21,8,4,2,1,1,
51,17,8,4,2,11,
127,37,16,8,4,2,1,1,
323,82,33,16,8,4,2,1,1,
835,185,69,32,16,8,4,2,1,1,
...

Manfred Scheucher, Table of n, a(n) for n = 0..5150
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers [Corrected annotated scanned copy] See Table 1.
Manfred Scheucher, Sage Script

Cf. A064645.

First 3 columns are A001006, A004148, A004149.

Corrected and extended by Manfred Scheucher, Jul 25 2015

A329664 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HH and DU.

Original entry on oeis.org

1, 1, 0, 1, 2, 2, 4, 8, 12, 21, 40, 69, 122, 227, 412, 747, 1386, 2567, 4744, 8851, 16566, 31004, 58268, 109858, 207368, 392331, 744072, 1413291, 2688822, 5124738, 9781492, 18694896, 35780444, 68566567, 131546440, 252661515, 485806614, 935017790, 1801327884, 3473467328, 6703610548

Offset: 0

Valerie Roitner, Nov 19 2019

The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending on the x-axis and never crossing the x-axis, i.e., staying at nonnegative altitude.

			a(4)=2 as one has 2 excursions of length 4, namely: HUHD and UHDH.

Cf. A004149 (avoiding UD and DU).

Cf. A329666, A329665.

G.f.: (t+1)*(1 - t - sqrt(4*t^4 - 4*t^3 + t^2 - 2*t + 1))/(2*t^3).

A387224 Number of dissections of a convex n-gon by strictly disjoint diagonals so as to create no triangles.

Original entry on oeis.org

0, 1, 1, 4, 8, 17, 37, 81, 177, 389, 859, 1905, 4241, 9477, 21251, 47806, 107864, 244045, 553575, 1258687, 2868285, 6549757, 14985361, 34347444, 78860152, 181347591, 417653187, 963234195, 2224464087, 5143567237, 11907471643, 27597112946, 64028244032, 148703128913, 345690623119

Offset: 3

Muhammed Sefa Saydam, Aug 22 2025

Strictly disjoint diagonals means that the diagonals are non-crossing and may not share endpoints.

			         n=4                         n=5                            n=6
    (1)       (2)                    (1)              (1) (2)     (1) (2)     (1) (2)
                                  (5)   (2)         (6)  \  (3) (6)-----(3) (6)  /  (3)
    (4)       (3)                  (4) (3)            (5) (4)     (5) (4)     (5) (4)
 Diagonal cannot be drawn   Diagonal cannot be drawn
    Number of cases = 1       Number of cases = 1         Number of cases = 3

Muhammed Sefa Saydam, Table of n, a(n) for n = 3..104

Cf. A004149, A093128.

seq(n) = my(g=2/(1 - x + x^2 + x^3 + sqrt((1-x^4)*(1-2*x-x^2) + O(x*x^n)))); Vec((1 - x^2 - 2*x^3)*g - 1 - x + 2*x^3 + 2*x^4, -n+2) \\ Andrew Howroyd, Aug 28 2025

a(n) = A004149(n) - A004149(n-2) - 2*A004149(n-3) for n >= 5.

G.f.: (1 - x^2 - 2*x^3)*B(x) - 1 - x + 2*x^3 + 2*x^4, where B(x) is the g.f. of A004149. - Andrew Howroyd, Aug 28 2025

cp's OEIS Frontend

A190172 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n having k UHD's; here U=(1,1), H=(1,0), and D=(1,-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A136018 Triangle read by rows: r(n,k) = g(n,n-k), where g(n,k) is the number of ideals of size k in a garland (or double fence) of order n (see A137278).

Views

Author

Keywords

Comments

References

Links

Formula

A258709 Triangle of generalized Catalan numbers read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A329664 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HH and DU.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A387224 Number of dissections of a convex n-gon by strictly disjoint diagonals so as to create no triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula