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.

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

Author

Emeric Deutsch, Sep 11 2004

Keywords

• nonn
• tabl

Comments

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

Examples

			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
		

Links

• 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

Crossrefs

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

Programs

Maple

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

Mathematica

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

Formula

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