A091965 - OEIS

A091965

Triangle read by rows: T(n,k) = number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0) (left factors of 3-Motzkin steps).

1, 3, 1, 10, 6, 1, 36, 29, 9, 1, 137, 132, 57, 12, 1, 543, 590, 315, 94, 15, 1, 2219, 2628, 1629, 612, 140, 18, 1, 9285, 11732, 8127, 3605, 1050, 195, 21, 1, 39587, 52608, 39718, 19992, 6950, 1656, 259, 24, 1, 171369, 237129, 191754, 106644, 42498, 12177, 2457

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

T(n,0) = A002212(n+1), T(n,1) = A045445(n+1); row sums give A026378.

The inverse is A207815. - Gary W. Adamson, Dec 17 2006 [corrected by Philippe Deléham, Feb 22 2012]

Reversal of A084536. - Philippe Deléham, Mar 23 2007

Triangle T(n,k), 0 <= k <= n, read by rows given by T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 3*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 3*T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007

This triangle belongs to the family of triangles defined by T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007

5^n = (n-th row terms) dot (first n+1 terms in (1,2,3,...)). Example for row 4: 5^4 = 625 = (137, 132, 57, 12, 1) dot (1, 2, 3, 4, 5) = (137 + 264 + 171 + 48 + 5) = 625. - Gary W. Adamson, Jun 15 2011

Riordan array ((1-3*x-sqrt(1-6*x+5*x^2))/(2*x^2), (1-3*x-sqrt(1-6*x+5*x^2))/(2*x)). - Philippe Deléham, Feb 19 2012

REFERENCES

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

LINKS

Vincenzo Librandi, Rows n = 0..100, flattened

Shu-Chiuan Chang and Robert Shrock, Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips, J. Stat. Physics 137 (2009) 667, table 5.

Helmut Prodinger, The amplitude of Motzkin paths, arXiv:2104.07596 [math.CO], 2021. Mentions this sequence.

Helmut Prodinger, Multi-edge trees and 3-coloured Motzkin paths: bijective issues, arXiv:2105.03350 [math.CO], 2021.

Helmut Prodinger, Weighted unary-binary trees, Hex-trees, marked ordered trees, and related structures, arXiv:2106.14782 [math.CO], 2021.

FORMULA

G.f.: G = 2/(1 - 3*z - 2*t*z + sqrt(1-6*z+5*z^2)). Alternatively, G = M/(1 - t*z*M), where M = 1 + 3*z*M + z^2*M^2.

Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A002212(m+n+1). - Philippe Deléham, Sep 14 2005

The triangle may also be generated from M^n * [1,0,0,0,...], where M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [3,3,3,...] in the main diagonal. - Gary W. Adamson, Dec 17 2006

Sum_{k=0..n} T(n,k)*(k+1) = 5^n. - Philippe Deléham, Mar 27 2007

Sum_{k=0..n} T(n,k)*x^k = A117641(n), A033321(n), A007317(n), A002212(n+1), A026378(n+1) for x = -3, -2, -1, 0, 1 respectively. - Philippe Deléham, Nov 28 2009

T(n,k) = (k+1)*Sum_{m=k..n} binomial(2*(m+1),m-k)*binomial(n,m)/(m+1). - Vladimir Kruchinin, Oct 08 2011

The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + 3*x + x^2)^n expanded about the point x = 0. - Peter Bala, Sep 06 2022

EXAMPLE

Triangle begins:

3, 1;

10, 6, 1;

36, 29, 9, 1;

137, 132, 57, 12, 1;

543, 590, 315, 94, 15, 1;

2219, 2628, 1629, 612, 140, 18, 1;

T(3,1)=29 because we have UDU, UUD, 9 HHU paths, 9 HUH paths and 9 UHH paths.

Production matrix begins

3, 1;

1, 3, 1;

0, 1, 3, 1;

0, 0, 1, 3, 1;

0, 0, 0, 1, 3, 1;

0, 0, 0, 0, 1, 3, 1;

0, 0, 0, 0, 0, 1, 3, 1;

0, 0, 0, 0, 0, 0, 1, 3, 1;

0, 0, 0, 0, 0, 0, 0, 1, 3, 1;

0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 1;

- Philippe Deléham, Nov 07 2011

MATHEMATICA

nmax = 9; t[n_, k_] := ((k+1)*n!*Hypergeometric2F1[k+3/2, k-n, 2k+3, -4]) / ((k+1)!*(n-k)!); Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)

T[0, 0, x_, y_] := 1; T[n_, 0, x_, y_] := x*T[n - 1, 0, x, y] + T[n - 1, 1, x, y]; T[n_, k_, x_, y_] := T[n, k, x, y] = If[k < 0 || k > n, 0,

T[n - 1, k - 1, x, y] + y*T[n - 1, k, x, y] + T[n - 1, k + 1, x, y]];

Table[T[n, k, 3, 3], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, May 22 2017 *)

PROG

(Maxima)

T(n, k):=(k+1)*sum((binomial(2*(m+1), m-k)*binomial(n, m))/(m+1), m, k, n); / Vladimir Kruchinin, Oct 08 2011 */

(Sage)

@CachedFunction

def A091965(n, k):

if n==0 and k==0: return 1

if k<0 or k>n: return 0

if k==0: return 3*A091965(n-1, 0)+A091965(n-1, 1)