OFFSET
0,8
COMMENTS
Row sums give the Motzkin numbers (A001006).
Column 0 is A005043.
Riordan array ((1+x-sqrt(1-2*x-3*x^2))/(2*x*(1-x)), (1+x-sqrt(1-2*x-3*x^2))/(2*(1-x))). - Paul Barry, Jun 21 2008
Inverse of Riordan array ((1-x)/(1-x+x^2), x*(1-x)/(1-x+x^2)), which is A104597. - Paul Barry, Jun 21 2008
Triangle read by rows, product of A064189 and A130595 considered as infinite lower triangular arrays; A097609 = A064189*A130195 = B*A053121*B^(-1) where B = A007318. - Philippe Deléham, Dec 07 2009
T(n+1,1) = A187306(n). - Philippe Deléham, Jan 28 2014
The number of lattice paths from (0,0) to (n,k) that do not cross below the x-axis and use up-step=(1,1) and down-steps=(1,-z) where z is a positive integer. For example, T(4,0) = 3: [(1,1)(1,1)(1,-1)(1,-1)], [(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)]. - Nicholas Ham, Aug 20 2015
The convolution triangle of the Riordan numbers A005043. - Peter Luschny, Oct 09 2022
LINKS
G. C. Greubel, Rows n = 0..100 of triangle, flattened
Jean-Luc Baril, Daniela Colmenares, José L. Ramírez, Emmanuel D. Silva, Lina M. Simbaqueba, and Diana A. Toquica, Consecutive pattern-avoidance in Catalan words according to the last symbol, Univ. Bourgogne (France 2023).
Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
Igor Dolinka, James East, and Robert D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015.
D. Merlini, R. Sprugnoli and M. C. Verri, An algebra for proper generating trees, Trends in Mathematics 2000, pp 127-139.
FORMULA
G.f.: 2/(1 -2*t*z +z +sqrt(1-2*z-3*z^2)).
T(n,k) = T(n-1,k-1)+ Sum_{j>=1} T(n-1,k+j) with T(0,0)=1. - Philippe Deléham, Jan 23 2010
T(n,k) = (k/n)*Sum_{j=k..n} (-1)^(n-j)*C(n,j)*C(2*j-k-1,j-1), n>0. - Vladimir Kruchinin, Feb 05 2011
From Emanuele Munarini, Jul 14 2024: (Start)
T(n,k) = Sum_{i=0..floor((n-k)/2)} binomial(n,i)*binomial(n-k-i-1,i-1)*(k+1)/(n-i+1).
T(n,k) = Sum_{i=0..n-k} (-1)^i*binomial(n,i)*binomial(2*n-k-2*i,n-i)*(k+1)/(n-i+1).
T(n,k) = (k+1)/(n+1)*Sum_{i=0..n-k} binomial(2*n-k-i,n)*trinomial(n+1,i)*(-1)^i, where trinomial(n,k) are the trinomial coefficients (A027907).
T(n,k) = Sum_{i=0..n-k} (-1)^i*binomial(2*n-k-i,n)*trinomial(n,i)*(i+k+1)/(n+1).
Recurrence: T(n+1,k+2) = T(n+1,k+1) - T(n,k+2) + T(n,k+1) - T(n,k). (End)
EXAMPLE
Triangle begins:
1;
0, 1;
1, 0, 1;
1, 2, 0, 1;
3, 2, 3, 0, 1;
6, 7, 3, 4, 0, 1;
Row n has n+1 terms.
T(5,2) = 3 because (HH)UHD,(H)UHD(H) and UHD(HH) are the only Motzkin paths of length 5 with 2 horizontal steps at level 0 (shown between parentheses); here U=(1,1), H=(1,0) and D=(1,-1).
Production matrix begins
0, 1;
1, 0, 1;
1, 1, 0, 1;
1, 1, 1, 0, 1;
1, 1, 1, 1, 0, 1;
1, 1, 1, 1, 1, 0, 1;
1, 1, 1, 1, 1, 1, 0, 1;
1, 1, 1, 1, 1, 1, 1, 0, 1;
1, 1, 1, 1, 1, 1, 1, 1, 0, 1;
... - Philippe Deléham, Mar 02 2013
MAPLE
G:=2/(1-2*t*z+z+sqrt(1-2*z-3*z^2)): Gser:=simplify(series(G, z=0, 13)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(coeff(Gser, z^n)) od: seq(seq(coeff(t*P[n], t^k), k=1..n+1), n=0..12);
# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.
PMatrix(10, n -> A005043(n-1)); # Peter Luschny, Oct 09 2022
MATHEMATICA
nmax = 12; t[n_, k_] := ((-1)^(n+k)*k*n!*HypergeometricPFQ[{(k+1)/2, k/2, k-n}, {k, k+1}, 4])/(n*k!*(n-k)!); Flatten[ Table[t[n, k], {n, 0, nmax}, {k, 1, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)
PROG
(PARI) T(n, k) = ((k+1)/(n+1))*sum(j=k+1, n+1, (-1)^(n-j+1)*binomial(n+1, j)* binomial(2*j-k-2, j-1) ); \\ G. C. Greubel, Feb 18 2020
(Magma) [((k+1)/(n+1))*(&+[(-1)^(n-j+1)*Binomial(n+1, j)*Binomial(2*j-k-2, j-1): j in [k+1..n+1]]): k in [0..n], n in [0..10]]; // G. C. Greubel, Feb 18 2020
(Sage) [[((k+1)/(n+1))*sum( (-1)^(n-j+1)*binomial(n+1, j)* binomial(2*j-k-2, j-1) for j in (k+1..n+1)) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Feb 18 2020
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 30 2004
STATUS
approved