|
|
A097609
|
|
Triangle read by rows: T(n,k) is number of Motzkin paths of length n having k horizontal steps at level 0.
|
|
12
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Row sums give the Motzkin numbers (A001006).
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
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
|
|
LINKS
|
|
|
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
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;
|
|
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.
|
|
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
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|