OFFSET
0,5
COMMENTS
T(n-1,k) is the number of Motzkin paths of length n that have k points on the horizontal axis (besides the first and last point). For example T(1,0)=1 counts the path UD with 2 steps and no intermediate interception with the y=0 axis, and T(1,1)=1 counts the path FF with 2 steps, staying on the y=0 axis. - R. J. Mathar, Jul 23 2017
Riordan matrix A=(g(t),t*g(t)), where g(t)=1+t*M(t)=C(t/(1-t)), where M(t) and C(t) are the g.f. of Motzkin and Catalan numbers. A is a pseudo-involution. - Emanuele Munarini, Jul 03 2024
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)
M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
Jean-Luc Baril and Paul Barry, Two kinds of partial Motzkin paths with air pockets, arXiv:2212.12404 [math.CO], 2022.
Richard J. Mathar, Motzkin Islands: a 3-dimensional Embedding of Motzkin Paths, viXra:2009.0152, 2020.
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.
FORMULA
Column k has g.f.: z^k(1+zM)^(k+1).
G.f.: (1+zM)/(1-tz(1+zM)), where M = 1 + zM+ z ^2M^2 is the g.f. of the Motzkin numbers (A001006).
T(n,m) = (m*(Sum_{k=1..n-m} k*(-1)^(n+m+k)*binomial(n+k-1,n-1) * Sum_{j=0..n-m} binomial(j,-n+m-k+2*j)*binomial(n-m,j)))/(n*(n-m)), n>m, T(n,n)=1. - Vladimir Kruchinin, Aug 20 2012
From Emanuele Munarini, Jul 03 2024: (Start)
T(n,k) = Sum_{i=0..n-k} (-1)^(n-k-i)*binomial(n-k-1,n-k-i) * binomial(2*i+k,i+k) * (k+1) / (i+k+1).
T(n,k) = Sum_{i=0..n-k} binomial(n-k-1,n-k-i)*binomial(n-i+1,i)*(k+1)/(n-i+1) for k < n.
T(n,k) = Sum_{i=0..n-k} trinomial(n-k,n-k-i)*binomial(k+1,i)*i/(n-k) for k < n, where trinomial(n,k) = A027907(n,k).
Recurrence: T(n+2,k+2) = T(n+2,k+1) + T(n+1,k+1) - T(n+1,k) - T(n,k). (End)
EXAMPLE
Triangle begins:
1;
1, 1;
1, 2, 1;
2, 3, 3, 1;
4, 6, 6, 4, 1;
9, 13, 13, 10, 5, 1;
21, 30, 30, 24, 15, 6, 1;
...
MATHEMATICA
T[n_, m_] := If[n == m, 1, (-1)^m (m Sum[k (-1)^(n+k) Binomial[n+k-1, n-1] Sum[Binomial[j, -n+m-k+2j] Binomial[n-m, j], {j, 0, n-m}], {k, 1, n-m}])/ (n(n-m))];
Table[T[n, m], {n, 1, 11}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
PROG
(Maxima) T(n, m):=if n=m then 1 else (-1)^m*(m*sum(k*(-1)^(n+k)*binomial(n+k-1, n-1)*sum(binomial(j, -n+m-k+2*j)*binomial(n-m, j), j, 0, n-m), k, 1, n-m))/(n*(n-m)); /* Vladimir Kruchinin, Aug 20 2012 */
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Mar 09 2004
STATUS
approved