%I #63 Jul 19 2024 19:23:52
%S 1,0,1,1,0,1,1,2,0,1,3,2,3,0,1,6,7,3,4,0,1,15,14,12,4,5,0,1,36,37,24,
%T 18,5,6,0,1,91,90,67,36,25,6,7,0,1,232,233,165,106,50,33,7,8,0,1,603,
%U 602,438,264,155,66,42,8,9,0,1,1585,1586,1147,719,390,215,84,52,9,10,0,1
%N Triangle read by rows: T(n,k) is number of Motzkin paths of length n having k horizontal steps at level 0.
%C Row sums give the Motzkin numbers (A001006).
%C Column 0 is A005043.
%C 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
%C 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
%C 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
%C T(n+1,1) = A187306(n). - _Philippe Deléham_, Jan 28 2014
%C 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
%C The convolution triangle of the Riordan numbers A005043. - _Peter Luschny_, Oct 09 2022
%H G. C. Greubel, <a href="/A097609/b097609.txt">Rows n = 0..100 of triangle, flattened</a>
%H Jean-Luc Baril, Daniela Colmenares, José L. Ramírez, Emmanuel D. Silva, Lina M. Simbaqueba, and Diana A. Toquica, <a href="http://jl.baril.u-bourgogne.fr/bacorasisito.pdf">Consecutive pattern-avoidance in Catalan words according to the last symbol</a>, Univ. Bourgogne (France 2023).
%H Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.
%H Igor Dolinka, James East, and Robert 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 D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.1007/978-3-0348-8405-1_11">An algebra for proper generating trees</a>, Trends in Mathematics 2000, pp 127-139.
%F G.f.: 2/(1 -2*t*z +z +sqrt(1-2*z-3*z^2)).
%F 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
%F 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
%F From _Emanuele Munarini_, Jul 14 2024: (Start)
%F 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).
%F 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).
%F 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).
%F T(n,k) = Sum_{i=0..n-k} (-1)^i*binomial(2*n-k-i,n)*trinomial(n,i)*(i+k+1)/(n+1).
%F Recurrence: T(n+1,k+2) = T(n+1,k+1) - T(n,k+2) + T(n,k+1) - T(n,k). (End)
%e Triangle begins:
%e 1;
%e 0, 1;
%e 1, 0, 1;
%e 1, 2, 0, 1;
%e 3, 2, 3, 0, 1;
%e 6, 7, 3, 4, 0, 1;
%e Row n has n+1 terms.
%e 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).
%e Production matrix begins
%e 0, 1;
%e 1, 0, 1;
%e 1, 1, 0, 1;
%e 1, 1, 1, 0, 1;
%e 1, 1, 1, 1, 0, 1;
%e 1, 1, 1, 1, 1, 0, 1;
%e 1, 1, 1, 1, 1, 1, 0, 1;
%e 1, 1, 1, 1, 1, 1, 1, 0, 1;
%e 1, 1, 1, 1, 1, 1, 1, 1, 0, 1;
%e ... - _Philippe Deléham_, Mar 02 2013
%p 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);
%p # Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.
%p PMatrix(10, n -> A005043(n-1)); # _Peter Luschny_, Oct 09 2022
%t 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_ *)
%o (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
%o (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
%o (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
%Y Cf. A001006, A005043, A027907, A187306.
%K nonn,tabl
%O 0,8
%A _Emeric Deutsch_, Aug 30 2004