cp's OEIS Frontend

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

%I A091965 #85 Apr 23 2025 09:00:06
%S A091965 1,3,1,10,6,1,36,29,9,1,137,132,57,12,1,543,590,315,94,15,1,2219,2628,
%T A091965 1629,612,140,18,1,9285,11732,8127,3605,1050,195,21,1,39587,52608,
%U A091965 39718,19992,6950,1656,259,24,1,171369,237129,191754,106644,42498,12177,2457
%N 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).
%C A091965 T(n,0) = A002212(n+1), T(n,1) = A045445(n+1); row sums give A026378.
%C A091965 The inverse is A207815. - _Gary W. Adamson_, Dec 17 2006 [corrected by _Philippe Deléham_, Feb 22 2012]
%C A091965 Reversal of A084536. - _Philippe Deléham_, Mar 23 2007
%C A091965 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
%C A091965 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
%C A091965 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
%C A091965 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
%D A091965 A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.
%H A091965 Vincenzo Librandi, <a href="/A091965/b091965.txt">Rows n = 0..100, flattened</a>
%H A091965 Shu-Chiuan Chang and Robert Shrock, <a href="https://doi.org/10.1007/s10955-009-9868-0">Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips</a>, J. Stat. Physics 137 (2009) 667, table 5.
%H A091965 Helmut Prodinger, <a href="https://arxiv.org/abs/2104.07596">The amplitude of Motzkin paths</a>, arXiv:2104.07596 [math.CO], 2021. Mentions this sequence.
%H A091965 Helmut Prodinger, <a href="https://arxiv.org/abs/2105.03350">Multi-edge trees and 3-coloured Motzkin paths: bijective issues</a>, arXiv:2105.03350 [math.CO], 2021.
%H A091965 Helmut Prodinger, <a href="https://arxiv.org/abs/2106.14782">Weighted unary-binary trees, Hex-trees, marked ordered trees, and related structures</a>, arXiv:2106.14782 [math.CO], 2021.
%F A091965 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.
%F A091965 Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A002212(m+n+1). - _Philippe Deléham_, Sep 14 2005
%F A091965 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
%F A091965 Sum_{k=0..n} T(n,k)*(k+1) = 5^n. - _Philippe Deléham_, Mar 27 2007
%F A091965 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
%F A091965 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
%F A091965 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
%e A091965 Triangle begins:
%e A091965      1;
%e A091965      3,    1;
%e A091965     10,    6,    1;
%e A091965     36,   29,    9,    1;
%e A091965    137,  132,   57,   12,    1;
%e A091965    543,  590,  315,   94,   15,    1;
%e A091965   2219, 2628, 1629,  612,  140,   18,    1;
%e A091965 T(3,1)=29 because we have UDU, UUD, 9 HHU paths, 9 HUH paths and 9 UHH paths.
%e A091965 Production matrix begins
%e A091965   3, 1;
%e A091965   1, 3, 1;
%e A091965   0, 1, 3, 1;
%e A091965   0, 0, 1, 3, 1;
%e A091965   0, 0, 0, 1, 3, 1;
%e A091965   0, 0, 0, 0, 1, 3, 1;
%e A091965   0, 0, 0, 0, 0, 1, 3, 1;
%e A091965   0, 0, 0, 0, 0, 0, 1, 3, 1;
%e A091965   0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
%e A091965   0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
%e A091965 - _Philippe Deléham_, Nov 07 2011
%t A091965 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 A091965 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 A091965 T[n - 1, k - 1, x, y] + y*T[n - 1, k, x, y] + T[n - 1, k + 1, x, y]];
%t A091965 Table[T[n, k, 3, 3], {n, 0, 10}, {k, 0, n}] // Flatten (* _G. C. Greubel_, May 22 2017 *)
%o A091965 (Maxima)
%o A091965 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 */
%o A091965 (Sage)
%o A091965 @CachedFunction
%o A091965 def A091965(n,k):
%o A091965     if n==0 and k==0: return 1
%o A091965     if k<0 or k>n: return 0
%o A091965     if k==0: return 3*A091965(n-1,0)+A091965(n-1,1)
%o A091965     return A091965(n-1,k-1)+3*A091965(n-1,k)+A091965(n-1,k+1)
%o A091965 for n in (0..7):
%o A091965     [A091965(n,k) for k in (0..n)] # _Peter Luschny_, Nov 05 2012
%Y A091965 Cf. A002212, A045445, A026378.
%Y A091965 Cf. A123965.
%K A091965 nonn,tabl
%O A091965 0,2
%A A091965 _Emeric Deutsch_, Mar 13 2004