A091836 A triangle of Motzkin ballot numbers.

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, 51, 72, 72, 59, 40, 21, 7, 1, 127, 178, 178, 148, 105, 62, 28, 8, 1, 323, 450, 450, 378, 276, 174, 91, 36, 9, 1, 835, 1158, 1158, 980, 730, 480, 273, 128, 45, 10, 1, 2188, 3023, 3023

Offset: 0

Author

Emeric Deutsch, Mar 09 2004

Keywords

• nonn
• tabl

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

Examples

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

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.

Crossrefs

Mirror image of A034929.

T(n, 0) = A086246(n+1) = A001006(n-1).

T(n, 1) = A005554(n).

Row sums are the Motzkin numbers (A001006).

Programs

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

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

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)