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

Comments

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

References

See A026300 for additional references and other information.

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.

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

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.

I. Dolinka, J. East, A. Evangelou, D. FitzGerald, and N. Ham, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015.

I. Dolinka, J. East, and R. D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015.

R. Donaghey and L. 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.

Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

R. Pemantle and M. 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.

Formula

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

Example

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)

Maple

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

Mathematica

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

Prog

(Sage)
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
(PARI) {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 */

Crossrefs

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

Sequence in context: A273713 A339067 A322329 * A273897 A330792 A063415

Adjacent sequences: A064186 A064187 A064188 * A064190 A064191 A064192

Keyword

nonn,easy,tabl

Author

N. J. A. Sloane, Sep 21 2001

Extensions

More terms from Vladeta Jovovic, Sep 23 2001

Status

approved