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,5

Comments

Column 0 is A004148 (RNA secondary structure numbers).

This triangle appears identical to A191579 (apart from offsets). - Philippe Deléham, Jan 26 2014

References

Cameron, Naiomi, and Everett Sullivan. "Peakless Motzkin paths with marked level steps at fixed height." Discrete Mathematics 344.1 (2021): 112154.

He, Tian-Xiao. "A-sequences, Z-sequence, and B-sequences of Riordan matrices." Discrete Mathematics 343.3 (2020): 111718.

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.

A. Nkwanta, 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

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

Example

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

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

Crossrefs

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

Sequence in context: A333878 A099569 A191579 * A091836 A291980 A238281

Adjacent sequences: A097721 A097722 A097723 * A097725 A097726 A097727

Keyword

nonn,tabl

Author

Emeric Deutsch, Sep 11 2004

Status

approved