A091964 -id:A091964 - cp's OEIS frontend

A191579 Triangular array related to continued fractions of square root of (N^2 - 1) for N>1, apparently containing A004148 and summing to A091964.

1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 4, 6, 6, 4, 1, 8, 13, 13, 10, 5, 1, 17, 28, 30, 24, 15, 6, 1, 37, 62, 69, 59, 40, 21, 7, 1, 82, 140, 160, 144, 105, 62, 28, 8, 1, 185, 320, 375, 350, 271, 174, 91, 36, 9, 1, 423, 740, 885, 852, 690, 474, 273, 128, 45, 10, 1

Offset: 1

Kenneth J Ramsey, Jun 07 2011

The row sums of this triangle seems to be A091964 (verified to 12 terms), cf. diagonal sums of the triangle A124428. The 1st column seems to be A004148.  The 2nd and 3rd column seems to be A089735, and A098075 (verified to 10 terms).
As each of these sequence is related to enumeration of RNA molecule structures, but was generated independently by reference to square array A192062 (re continued fractions for square roots of n^2-1 for n>1, see comments in the example below), it could be interesting to check this further for a relationship. As Mathar noted, this triangle appears identical to A097724. - edited by Kenneth J Ramsey, Oct 25 2012
Is this (apart from offsets) the same as A097724? - R. J. Mathar, Aug 01 2011

			The triangle begins
1;
1, 1;
1, 2, 1;
2, 3, 3, 1;
4, 6, 6, 4, 1;
8, 13, 13, 10, 5, 1;
17, 28, 30, 24, 15, 6, 1;
37, 62, 69, 59, 40, 21, 7, 1;
82, 140, 160, 144, 105, 62, 28, 8, 1;
185, 320, 375, 350, 271, 174, 91, 36, 9, 1;
423, 740, 885, 852, 690, 474, 273, 128, 45, 10, 1;
...
The 4th row is 2,3,3,1 because the 2nd,4th,6th and 8th terms of columns j = 1-5 of square array T(i,j) A192062  form the 4*5 matrix {{1,3,8,21},{1,4,15,56},{1,5,24,115},{1,6,35,204},{1,7,48,329}}. Solving the resulting system of linear equations results in the identities:
2*1 + 3*3 + 3*8 + 1*21 = 56 = T(8,2) of A192062
2*1 + 3*4 + 3*15+ 1*56 = 115 = T(8,3) of A192062
2*1 + 3*5 + 3*24 + 1*115 = 204 = T(8,4) of A192062
2*1 + 3*6 + 3*35 + 1*204 = 329 = T(8,5) of A192062

Cf. A091964, A124428, A004148, A089735, A098075, A192062.

The only way I know to generate this triangle is by reference to the square array A192062. The columns of that array, T(i,j) are such that for any given i>0, each term T(i,2*n) equals the sum as k = 1 to n, T(i-1,2*k)*C_k where C_k is the k th term of the n th row of this triangle. So solving the system of linear equations for each n > 0 gives the n th row of this triangle.

A097724 Triangle read by rows: T(n,k) is the number of left factors of Motzkin paths without peaks, having length n and endpoint height k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 4, 6, 6, 4, 1, 8, 13, 13, 10, 5, 1, 17, 28, 30, 24, 15, 6, 1, 37, 62, 69, 59, 40, 21, 7, 1, 82, 140, 160, 144, 105, 62, 28, 8, 1, 185, 320, 375, 350, 271, 174, 91, 36, 9, 1, 423, 740, 885, 852, 690, 474, 273, 128, 45, 10, 1, 978, 1728, 2102, 2077

Offset: 0

Emeric Deutsch, Sep 11 2004

Column 0 is A004148 (RNA secondary structure numbers).
This triangle appears identical to A191579 (apart from offsets). - Philippe Deléham, Jan 26 2014
Conjecture: the row reverse triangle is the triangle of connection constants for expressing the polynomial u(n,x+1) as a linear combination of the polynomials u(k,x), 0 <= k <= n, where u(n,x) = U(n,x/2) with U(n,x) the n-th Chebyshev polynomial of the second kind. An example is given below.  Cf. A205810. - Peter Bala, Jun 26 2025

			Triangle starts:
  1;
  1, 1;
  1, 2, 1;
  2, 3, 3, 1;
  4, 6, 6, 4, 1;
Row n has n+1 terms.
T(3,2)=3 because we have HUU, UHU and UUH, where U=(1,1) and H=(1,0).
Row 7: let u(n,x) = U(n,x/2). Then u(7,x+1) = u(7,x) + 7*u(6,x) + 21*u(5,x) + 40*u(4,x) + 59*u(3,x) + 69*u(2,x) + 62*u(1,x) + 37. - _Peter Bala_, Jun 26 2025

Alois P. Heinz, Rows n = 0..140, flattened
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Naiomi Cameron and Everett Sullivan, Peakless Motzkin paths with marked level steps at fixed height, Discrete Mathematics 344.1 (2021): 112154.
Tian-Xiao He, A-sequences, Z-sequence, and B-sequences of Riordan matrices, Discrete Mathematics 343.3 (2020): 111718.
A. Nkwanta and A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.
A. Panayotopoulos and P. Vlamos, Cutting Degree of Meanders, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From _N. J. A. Sloane_, Dec 29 2012

Cf. A004148, A191579, A091964 (row sums), A205810.

T:=proc(n,k) if k=n then 1 else (k+1)*sum(binomial(j,n-k-j)*binomial(j+k,n+1-j)/j,j=ceil((n-k+1)/2)..n-k) fi end: seq(seq(T(n,k),k=0..n),n=0..12); T:=proc(n,k) if k=n then 1 else (k+1)*sum(binomial(j,n-k-j)*binomial(j+k,n+1-j)/j,j=ceil((n-k+1)/2)..n-k) fi end: TT:=(n,k)->T(n-1,k-1): matrix(10,10,TT); # gives the sequence as a matrix

T[n_, k_] := T[n, k] = If[k==n, 1, (k+1)*Sum[Binomial[j, n-k-j]*Binomial[j +k, n+1-j]/j, {j, Ceiling[(n-k+1)/2], n-k}]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

T(n,k) = (k+1)*Sum_{j=ceiling((n-k+1)/2)..n-k} (C(j,n-k-j)*C(j+k,n+1-j)/j) for 0 <= k < n; T(n,n)=1.
G.f.: G/(1-tzG), where G = (1 - z + z^2 - sqrt(1 - 2z - z^2 - 2z^3 + z^4))/(2z^2) is the g.f. for the sequence A004148.
T(n,k) = T(n-1,k-1) + Sum_{j>=0} T(n-1-j,k+j), T(0,0) = 1, T(n,k) = 0 if k < 0 or if k > n. - Philippe Deléham, Jan 26 2014
Sum_{j=0..n-1} cos(2*Pi*k/3 + Pi/6)*T(n,k) = cos(Pi*n/2)*sqrt(3)/2 - cos(2*Pi*n/3 + Pi/6). - Leonid Bedratyuk, Dec 06 2017

A104559 Triangle, read by rows, of the number of left factors of peakless Motzkin paths of length n having k number of U's and D's (i.e., number of paths from (0,0) to the line x=n, consisting of steps U=(1,1), H=(1,0), D=(1,1), that never go below the x-axis and a U step is never followed by a D step).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 9, 6, 1, 1, 5, 16, 18, 9, 1, 1, 6, 25, 40, 36, 12, 1, 1, 7, 36, 75, 100, 60, 16, 1, 1, 8, 49, 126, 225, 200, 100, 20, 1, 1, 9, 64, 196, 441, 525, 400, 150, 25, 1, 1, 10, 81, 288, 784, 1176, 1225, 700, 225, 30, 1, 1, 11, 100, 405, 1296, 2352

Offset: 0

Paul D. Hanna and Emeric Deutsch, Mar 16 2005

Row sums form A091964, the number of left factors of peakless Motzkin paths of length n.

			Triangle begins:
  1;
  1,   1;
  1,   2,   1;
  1,   3,   4,   1;
  1,   4,   9,   6,   1;
  1,   5,  16,  18,   9,   1;
  1,   6,  25,  40,  36,  12,   1;
  1,   7,  36,  75, 100,  60,  16,   1;
  1,   8,  49, 126, 225, 200, 100,  20,   1; ...

Cf. A091964, A104557.

T:=proc(n,k) if k<=n then binomial(n-floor(k/2),floor((k+1)/2))*binomial(n-floor((k+1)/2),floor(k/2)) else 0 fi end: for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form # Emeric Deutsch, Mar 16 2005

T(n,k)=binomial(n-(k\2),(k+1)\2)*binomial(n-((k+1)\2),k\2)

{T(n,k)=local(X=x+x*O(x^n),Y=y+y*O(y^k));polcoeff(polcoeff( 2/(1-X+X^2*Y^2-2*X*Y+sqrt((1-X+X^2*Y^2)^2-4*X^2*Y^2)),n,x),k,y)}

G.f.: A(x, y) = 2/(1-x+x^2*y^2 - 2*x*y + sqrt((1-x+x^2*y^2)^2 - 4*x^2*y^2)) (due to Emeric Deutsch).

T(n, k) = C(n-floor(k/2), floor((k+1)/2))*C(n-floor((k+1)/2), floor(k/2)) = A104557(n, k)/(n-k)!.

A132893 Triangle read by rows: T(n,k) is the number of paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having k peaks (i.e., UDs), 0 <= k <= floor(n/2).

Original entry on oeis.org

1, 2, 4, 1, 9, 4, 21, 13, 1, 50, 40, 6, 121, 118, 27, 1, 296, 340, 106, 8, 730, 965, 381, 46, 1, 1812, 2708, 1296, 220, 10, 4521, 7535, 4241, 935, 70, 1, 11328, 20828, 13482, 3676, 395, 12, 28485, 57266, 41916, 13658, 1940, 99, 1

Offset: 0

Emeric Deutsch, Oct 08 2007

Row n has 1 + floor(n/2) terms.

Row sums yield A005773.

			T(3,1)=4 because we have HUD, UDH, UDU and UUD.
Triangle starts:
    1;
    2;
    4,   1;
    9,   4;
   21,  13,   1;
   50,  40,   6;
  121, 118,  27,   1;

Alois P. Heinz, Rows n = 0..200, flattened
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

Cf. A005773, A091964, A132894.

G:=((-1+3*z-z^2+t*z^2+sqrt((1+z+z^2-t*z^2)*(1-3*z+z^2-t*z^2)))*1/2)/(z*(1-3*z+z^2-t*z^2)): Gser:=simplify(series(G,z=0,15)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: for n from 0 to 12 do seq(coeff(P[n],t,j), j=0..floor((1/2)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0, 0,
     `if`(x=0, 1, b(x-1, y, 1)+b(x-1, y-1, 1)*t+b(x-1, y+1, z))))
    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, Feb 01 2019

b[x_, y_, t_] := b[x, y, t] = Expand[If[y < 0, 0, If[x == 0, 1, b[x - 1, y, 1] + b[x - 1, y - 1, 1]*t + b[x - 1, y + 1, z]]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]] @ b[n, 0, 1];
T /@ Range[0, 15] // Flatten (* Jean-François Alcover, Oct 06 2019, after Alois P. Heinz *)

T(n,0) = A091964(n).
Sum_{k=0..floor(n/2)} k*T(n,k) = A132894(n-1).
G.f.: G = G(t,z) satisfies z(1 - 3z + z^2 - tz^2)G^2 + (1 - 3z + z^2 - tz^2)G - 1 = 0 (see the Maple program for the explicit expression of G).

A355043 Expansion of the continued fraction 1 / (1-q-q^2 / (1-q-q^2-q^3 / (1-q-q^2-q^3-q^4 / (...)))).

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 50, 121, 296, 730, 1811, 4513, 11285, 28294, 71088, 178904, 450840, 1137345, 2871720, 7256093, 18345060, 46403039, 117421762, 297232446, 752601692, 1906056161, 4828267801, 12232594912, 30996034963, 78549710061, 199079279640, 504596195477, 1279065489044

Offset: 0

Joerg Arndt, Jun 16 2022

nonn

Starts similar to A091964, terms differ after 730.

Cf. A355040, A355046, A091964.

nmax = 40; CoefficientList[Series[1/(1 - x - x^2/(1 - x - x^2 + ContinuedFractionK[-x^k, 1 - x*(1 - x^k)/(1 - x), {k, 3, nmax}])), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jun 16 2022 *)

N=44; q='q+O('q^N);
f(n) = 1 - sum(k=1,n-1,q^k);
s=1; forstep(j=N, 2, -1, s = q^j/s; s = f(j) - s ); s = 1/s;
Vec(s)

a(n) ~ c * d^n, where d = 2.5358790673564851880281667369326354455... and c = 0.14917782209027525483339419811881753... - Vaclav Kotesovec, Jun 16 2022

A325917 Number of Motzkin meanders of length n with an even number of humps and without peaks.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 65, 136, 298, 691, 1694, 4340, 11433, 30510, 81592, 217238, 573970, 1503296, 3904181, 10065079, 25796324, 65837541, 167602092, 426213784, 1084095329, 2760717190, 7043305930, 18008810836, 46151503544, 118529776510, 304998080821

Offset: 0

Andrei Asinowski, May 28 2019

nonn

A Motzkin meander is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), and never goes below the x-axis.
A peak is an occurrence of the pattern UD.
A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).

			For n=0..5 we have a(n)=2^n because for these values we have only the humpless paths {U, H}^n. For n=6, the only "extra" path is UHDUHD. For n=7, the eight "extra" paths are UHDUHHD, UHHDUHD, UHDUHDH, UHDUHDU, UHDHUHD, UHDUUHD, HUHDUHD, UUHDUHD.

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018).

CoefficientList[Series[(1/4)*(x^3 - 4*x^2 + 4*x - 1 + Sqrt[x^6 - 4*x^5 + 4*x^4 - 2*x^3 + 4*x^2 - 4*x + 1])/((-x^3 + 4*x^2 - 4*x + 1)*x) + (1/4)*(-x^3 - 4*x^2 + 4*x - 1 + Sqrt[x^6 + 4*x^5 - 4*x^4 + 2*x^3 + 4*x^2 - 4*x + 1])/((x^3 + 4*x^2 - 4*x + 1)*x), {x, 0, 40}], x] (* Vaclav Kotesovec, Jun 05 2019 *)

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

a(n) + A325919(n) = A091964(n). - R. J. Mathar, Jan 25 2023

cp's OEIS Frontend

A191579 Triangular array related to continued fractions of square root of (N^2 - 1) for N>1, apparently containing A004148 and summing to A091964.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A097724 Triangle read by rows: T(n,k) is the number of left factors of Motzkin paths without peaks, having length n and endpoint height k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

PARI

Formula

A132893 Triangle read by rows: T(n,k) is the number of paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having k peaks (i.e., UDs), 0 <= k <= floor(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A355043 Expansion of the continued fraction 1 / (1-q-q^2 / (1-q-q^2-q^3 / (1-q-q^2-q^3-q^4 / (...)))).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A325917 Number of Motzkin meanders of length n with an even number of humps and without peaks.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula