|
%I #132 Mar 29 2024 06:44:20
%S 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,
%T 127,196,189,133,70,27,7,1,323,512,518,392,230,104,35,8,1,835,1353,
%U 1422,1140,726,369,147,44,9,1,2188,3610,3915,3288,2235,1242,560,200,54,10,1
%N 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).
%C Motzkin triangle read in reverse order.
%C 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
%C 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
%C Inverse binomial matrix applied to A039598. - _Philippe Deléham_, Feb 28 2007
%C 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
%C 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
%C Equals binomial transform of triangle A053121. - _Gary W. Adamson_, Oct 25 2008
%C 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
%D See A026300 for additional references and other information.
%D 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.
%H G. C. Greubel, <a href="/A064189/b064189.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Barry/barry601.html">On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
%H Paul Barry, <a href="https://arxiv.org/abs/2307.00098">Moment sequences, transformations, and Spidernet graphs</a>, arXiv:2307.00098 [math.CO], 2023.
%H I. Dolinka, J. East, A. Evangelou, D. FitzGerald, and N. Ham, <a href="http://arxiv.org/abs/1507.04838">Idempotent Statistics of the Motzkin and Jones Monoids</a>, arXiv preprint arXiv:1507.04838 [math.CO], 2015.
%H I. Dolinka, J. East, and R. D. Gray, <a href="http://arxiv.org/abs/1512.02279">Motzkin monoids and partial Brauer monoids</a>, arXiv preprint arXiv:1512.02279 [math.GR], 2015.
%H R. Donaghey and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, 23 (1977), 291-301.
%H Ivana Đurđev, Igor Dolinka, and James East, <a href="https://arxiv.org/abs/1910.10286">Sandwich semigroups in diagram categories</a>, arXiv:1910.10286 [math.GR], 2019.
%H Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.
%H Tom Halverson and Theodore N. Jacobson, <a href="https://arxiv.org/abs/1808.08118">Set-partition tableaux and representations of diagram algebras</a>, arXiv:1808.08118 [math.RT], 2018.
%H Donatella Merlini and Massimo Nocentini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Merlini/merlini5.html">Algebraic Generating Functions for Languages Avoiding Riordan Patterns</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
%H R. Pemantle and M. C. Wilson, <a href="http://dx.doi.org/10.1137/050643866">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 265.
%H Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, <a href="http://dx.doi.org/10.1016/j.disc.2017.07.006">Some matrix identities on colored Motzkin paths</a>, Discrete Mathematics 340.12 (2017): 3081-3091.
%H Sheng-Liang Yang and Yuan-Yuan Gao, <a href="https://www.fq.math.ca/Papers1/56-4/yanggao1032018.pdf">The Pascal rhombus and Riordan arrays</a>, Fib. Q., 56:4 (2018), 337-347. See Fig. 3.
%F Sum_{k=0..n} T(n, k)*(k+1) = 3^n.
%F Sum_{k=0..n} T(n, k)*T(n, n-k) = T(2*n, n) - T(2*n, n+2)
%F 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
%F Sum_{k>=0} T(m, k)*T(n, k) = A001006(m+n). - _Philippe Deléham_, Mar 05 2004
%F Sum_{k>=0} T(n-k, k) = A005043(n+2). - _Philippe Deléham_, May 31 2005
%F Column k has e.g.f. exp(x)*(BesselI(k,2*x)-BesselI(k+2,2*x)). - _Paul Barry_, Feb 16 2006
%F 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
%F 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
%F T(n,k) = A122896(n+1,k+1). - _Philippe Deléham_, Apr 21 2007
%F T(n,k) = (k/n)*Sum_{j=0..n} binomial(n,j)*binomial(j,2*j-n-k). - _Vladimir Kruchinin_, Feb 12 2011
%F Sum_{k=0..n} T(n,k)*(-1)^k*(k+1) = (-1)^n. - _Werner Schulte_, Jul 08 2015
%F Sum_{k=0..n} T(n,k)*(k+1)^3 = (2*n+1)*3^n. - _Werner Schulte_, Jul 08 2015
%F 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
%F T(n,k) = binomial(n, k)*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4). - _Peter Luschny_, May 19 2021
%F 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
%e Triangle begins:
%e [0] 1;
%e [1] 1, 1;
%e [2] 2, 2, 1;
%e [3] 4, 5, 3, 1;
%e [4] 9, 12, 9, 4, 1;
%e [5] 21, 30, 25, 14, 5, 1;
%e [6] 51, 76, 69, 44, 20, 6, 1;
%e [7] 127, 196, 189, 133, 70, 27, 7, 1;
%e [8] 323, 512, 518, 392, 230, 104, 35, 8, 1;
%e [9] 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1.
%e .
%e From _Philippe Deléham_, Nov 04 2011: (Start)
%e Production matrix begins:
%e 1, 1
%e 1, 1, 1
%e 0, 1, 1, 1
%e 0, 0, 1, 1, 1
%e 0, 0, 0, 1, 1, 1
%e 0, 0, 0, 0, 1, 1, 1 (End)
%p 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
%p # Uses function PMatrix from A357368. Adds a row above and a column to the left.
%p PMatrix(10, n -> simplify(hypergeom([1 -n/2, -n/2+1/2], [2], 4))); # _Peter Luschny_, Oct 08 2022
%t 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 T[n_, k_] := Binomial[n, k] Hypergeometric2F1[(k - n)/2, (k - n + 1)/2, k + 2, 4];
%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Peter Luschny_, May 19 2021 *)
%o (Sage)
%o def A064189_triangel(dim):
%o M = matrix(ZZ,dim,dim)
%o for n in range(dim): M[n,n] = 1
%o for n in (1..dim-1):
%o for k in (0..n-1):
%o M[n,k] = M[n-1,k-1]+M[n-1,k]+M[n-1,k+1]
%o return M
%o A064189_triangel(9) # _Peter Luschny_, Sep 20 2012
%o (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 */
%Y A026300 (the main entry for this sequence) with rows reversed.
%Y Cf. A001006, A002026, A005322, A005323, A053121.
%Y Row sums give: A005773(n+1) or A307789(n+2).
%K nonn,easy,tabl
%O 0,4
%A _N. J. A. Sloane_, Sep 21 2001
%E More terms from _Vladeta Jovovic_, Sep 23 2001
|
