A307789 -id:A307789 - cp's OEIS frontend

A064189 Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1).

1, 1, 1, 2, 2, 1, 4, 5, 3, 1, 9, 12, 9, 4, 1, 21, 30, 25, 14, 5, 1, 51, 76, 69, 44, 20, 6, 1, 127, 196, 189, 133, 70, 27, 7, 1, 323, 512, 518, 392, 230, 104, 35, 8, 1, 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1, 2188, 3610, 3915, 3288, 2235, 1242, 560, 200, 54, 10, 1

Offset: 0

N. J. A. Sloane, Sep 21 2001

Motzkin triangle read in reverse order.
T(n,k) = number of lattice paths from (0,0) to (n,k), staying weakly above the x-axis and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). Example: T(3,1) = 5 because we have HHU, UDU, HUH, UHH and UUD. Columns 0,1,2 and 3 give A001006 (Motzkin numbers), A002026 (first differences of Motzkin numbers), A005322 and A005323, respectively. - Emeric Deutsch, Feb 29 2004
Riordan array ((1-x-sqrt(1-2x-3x^2))/(2x^2), (1-x-sqrt(1-2x-3x^2))/(2x)). Inverse is the array (1/(1+x+x^2), x/(1+x+x^2)) (A104562). - Paul Barry, Mar 15 2005
Inverse binomial matrix applied to A039598. - Philippe Deléham, Feb 28 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) = T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 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 from 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
Equals binomial transform of triangle A053121. - Gary W. Adamson, Oct 25 2008
Consider a semi-infinite chessboard with squares labeled (n,k), ranks or rows n >= 0, files or columns k >= 0; the number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,k). The recurrence relation given above relates to the movements of the king. This is essentially the comment made by Harrie Grondijs for the Motzkin triangle A026300. - Johannes W. Meijer, Oct 10 2010

			Triangle begins:
  [0]   1;
  [1]   1,    1;
  [2]   2,    2,    1;
  [3]   4,    5,    3,    1;
  [4]   9,   12,    9,    4,   1;
  [5]  21,   30,   25,   14,   5,   1;
  [6]  51,   76,   69,   44,  20,   6,   1;
  [7] 127,  196,  189,  133,  70,  27,   7,  1;
  [8] 323,  512,  518,  392, 230, 104,  35,  8, 1;
  [9] 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1;
  ...
From _Philippe Deléham_, Nov 04 2011: (Start)
Production matrix begins:
  1, 1
  1, 1, 1
  0, 1, 1, 1
  0, 0, 1, 1, 1
  0, 0, 0, 1, 1, 1
  0, 0, 0, 0, 1, 1, 1 (End)

See A026300 for additional references and other information.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 16, 29.
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], 2024. See pp. 3, 7.
Igor Dolinka, James East, Athanasios Evangelou, Desmond FitzGerald, Nicholas Ham, James Hyde, Nicholas Loughlin, and James Mitchell, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015.
Igor Dolinka, James East, and Robert D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015.
Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
Ivana Đurđev, Igor Dolinka, and James East, Sandwich semigroups in diagram categories, arXiv:1910.10286 [math.GR], 2019.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Tom Halverson and Theodore N. Jacobson, Set-partition tableaux and representations of diagram algebras, arXiv:1808.08118 [math.RT], 2018.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See p. 29.
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
Robin Pemantle and Mark C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 265.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017): 3081-3091.
Sheng-Liang Yang and Yuan-Yuan Gao, The Pascal rhombus and Riordan arrays, Fib. Q., 56:4 (2018), 337-347. See Fig. 3.

A026300 (the main entry for this sequence) with rows reversed.
Cf. A001006, A002026, A005322, A005323, A053121.
Row sums give: A005773(n+1) or A307789(n+2).

alias(C=binomial): A064189 := (n,k) -> add(C(n,j)*(C(n-j,j+k)-C(n-j,j+k+2)), j=0..n): seq(seq(A064189(n,k), k=0..n),n=0..10); # Peter Luschny, Dec 31 2019
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> simplify(hypergeom([1 -n/2, -n/2+1/2], [2], 4))); # Peter Luschny, Oct 08 2022

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, 1, 1], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Apr 21 2017 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[(k - n)/2, (k - n + 1)/2, k + 2, 4];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten  (* Peter Luschny, May 19 2021 *)

{T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt(1 - 2*x - 3*x^2) - 2*x*y) + x * O(x^n), n), k))}; /* Michael Somos, Jun 06 2016 */

def A064189_triangel(dim):
    M = matrix(ZZ,dim,dim)
    for n in range(dim): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1]+M[n-1,k]+M[n-1,k+1]
    return M
A064189_triangel(9) # Peter Luschny, Sep 20 2012

Sum_{k=0..n} T(n, k)*(k+1) = 3^n.
Sum_{k=0..n} T(n, k)*T(n, n-k) = T(2*n, n) - T(2*n, n+2)
G.f.: M/(1-t*z*M), where M = 1 + z*M + z^2*M^2 is the g.f. of the Motzkin numbers (A001006). - Emeric Deutsch, Feb 29 2004
Sum_{k>=0} T(m, k)*T(n, k) = A001006(m+n). - Philippe Deléham, Mar 05 2004
Sum_{k>=0} T(n-k, k) = A005043(n+2). - Philippe Deléham, May 31 2005
Column k has e.g.f. exp(x)*(BesselI(k,2*x)-BesselI(k+2,2*x)). - Paul Barry, Feb 16 2006
T(n,k) = Sum_{j=0..n} C(n,j)*(C(n-j,j+k) - C(n-j,j+k+2)). - Paul Barry, Feb 16 2006
n-th row is generated from M^n * V, where M = the infinite tridiagonal matrix with all 1's in the super, main and subdiagonals; and V = the infinite vector [1,0,0,0,...]. E.g., Row 3 = (4, 5, 3, 1), since M^3 * V = [4, 5, 3, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 04 2006
T(n,k) = A122896(n+1,k+1). - Philippe Deléham, Apr 21 2007
T(n,k) = (k/n)*Sum_{j=0..n} binomial(n,j)*binomial(j,2*j-n-k). - Vladimir Kruchinin, Feb 12 2011
Sum_{k=0..n} T(n,k)*(-1)^k*(k+1) = (-1)^n. - Werner Schulte, Jul 08 2015
Sum_{k=0..n} T(n,k)*(k+1)^3 = (2*n+1)*3^n. - Werner Schulte, Jul 08 2015
G.f.: 2 / (1 - x + sqrt(1 - 2*x - 3*x^2) - 2*x*y) = Sum_{n >= k >= 0} T(n, k) * x^n * y^k. - Michael Somos, Jun 06 2016
T(n,k) = binomial(n, k)*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4). - Peter Luschny, May 19 2021
The coefficients of the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + x + x^2)^n expanded about the point x = 0 give the entries in row n in reverse order. - Peter Bala, Sep 06 2022

More terms from Vladeta Jovovic, Sep 23 2001

cp's OEIS Frontend

A064189 Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions