login
A triangle of Motzkin ballot numbers.
4

%I #62 Jul 05 2024 03:18:50

%S 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,

%T 72,72,59,40,21,7,1,127,178,178,148,105,62,28,8,1,323,450,450,378,276,

%U 174,91,36,9,1,835,1158,1158,980,730,480,273,128,45,10,1,2188,3023,3023

%N A triangle of Motzkin ballot numbers.

%C 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

%C 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

%H Michael De Vlieger, <a href="/A091836/b091836.txt">Table of n, a(n) for n = 0..11475</a> (rows n = 0..150, flattened)

%H M. Aigner, <a href="http://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.

%H Jean-Luc Baril and Paul Barry, <a href="https://arxiv.org/abs/2212.12404">Two kinds of partial Motzkin paths with air pockets</a>, arXiv:2212.12404 [math.CO], 2022.

%H Richard J. Mathar, <a href="https://viXra.org/abs/2009.0152">Motzkin Islands: a 3-dimensional Embedding of Motzkin Paths</a>, viXra:2009.0152, 2020.

%H J.-C. Novelli and J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0512570">Noncommutative Symmetric Functions and Lagrange Inversion</a>, arXiv:math/0512570 [math.CO], 2005-2006.

%F Column k has g.f.: z^k(1+zM)^(k+1).

%F G.f.: (1+zM)/(1-tz(1+zM)), where M = 1 + zM+ z ^2M^2 is the g.f. of the Motzkin numbers (A001006).

%F 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

%F From _Emanuele Munarini_, Jul 03 2024: (Start)

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

%F 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.

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

%F Recurrence: T(n+2,k+2) = T(n+2,k+1) + T(n+1,k+1) - T(n+1,k) - T(n,k). (End)

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 2, 3, 3, 1;

%e 4, 6, 6, 4, 1;

%e 9, 13, 13, 10, 5, 1;

%e 21, 30, 30, 24, 15, 6, 1;

%e ...

%t 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))];

%t Table[T[n, m], {n, 1, 11}, {m, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 27 2018, after _Vladimir Kruchinin_ *)

%o (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 */

%Y Mirror image of A034929.

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

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

%Y Row sums are the Motzkin numbers (A001006).

%K nonn,tabl

%O 0,5

%A _Emeric Deutsch_, Mar 09 2004