A097609 Triangle read by rows: T(n,k) is number of Motzkin paths of length n having k horizontal steps at level 0.
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, 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, 602, 438, 264, 155, 66, 42, 8, 9, 0, 1, 1585, 1586, 1147, 719, 390, 215, 84, 52, 9, 10, 0, 1
Offset: 0
Examples
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
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.
Programs
-
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
-
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 *) -
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
-
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
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)
Comments