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
KEYWORD
AUTHOR
N. J. A. Sloane, Sep 21 2001
EXTENSIONS
More terms from Vladeta Jovovic, Sep 23 2001
STATUS
approved