|
|
A020474
|
|
A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.
|
|
14
|
|
|
1, 0, 1, 0, 1, 2, 0, 0, 2, 4, 0, 0, 1, 5, 9, 0, 0, 0, 3, 12, 21, 0, 0, 0, 1, 9, 30, 51, 0, 0, 0, 0, 4, 25, 76, 127, 0, 0, 0, 0, 1, 14, 69, 196, 323, 0, 0, 0, 0, 0, 5, 44, 189, 512, 835, 0, 0, 0, 0, 0, 1, 20, 133, 518, 1353, 2188, 0, 0, 0, 0, 0, 0, 6, 70, 392, 1422, 3610, 5798, 0, 0, 0, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,6
|
|
COMMENTS
|
T(n,k) = number of Dyck n-paths that start UU, contain no DUDU and no subpath of the form UUPDD with P a nonempty Dyck path and whose terminal descent has length n-k+2. For example, T(5,4)=2 counts UUDUUDUDDD, UUUDDUUDDD (each ending with exactly n-k+2=3 Ds). - David Callan, Sep 25 2006
|
|
LINKS
|
R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
|
|
FORMULA
|
a(n,k) = a(n,k-1) + a(n-1,k-1) + a(n-2,k-1), n > k >= 2.
|
|
EXAMPLE
|
Triangle begins:
1
0, 1
0, 1, 2
0, 0, 2, 4
0, 0, 1, 5, 9
0, 0, 0, 3, 12, 21
0, 0, 0, 1, 9, 30, 51
0, 0, 0, 0, 4, 25, 76, 127
0, 0, 0, 0, 1, 14, 69, 196, 323
|
|
MAPLE
|
M:=16; T:=Array(0..M, 0..M, 0);
T[0, 0]:=1; T[1, 1]:=1;
for i from 1 to M do T[i, 0]:=0; od:
for n from 2 to M do for k from 1 to n do
T[n, k]:= T[n, k-1]+T[n-1, k-1]+T[n-2, k-1];
od: od;
rho:=n->[seq(T[n, k], k=0..n)];
|
|
MATHEMATICA
|
a[2, 2]=1; a[n_, k_]/; Not[n>2 && 2<=k<=n] := 0; a[n_, k_]/; (n>2 && 2<=k<=n) := a[n, k] = a[n, k-1] + a[n-1, k-1] + a[n-2, k-1]; Table[a[n, k], {n, 2, 10}, {k, 2, n}] (* David Callan, Sep 25 2006 *)
|
|
PROG
|
(PARI) T(n, k)=if(n==0&&k==0, 1, if(n<=0||k<=0||n<k, 0, T(n, k-1)+T(n-1, k-1)+T(n-2, k-1))) \\ Ralf Stephan
(Haskell)
a020474 n k = a020474_tabl !! (n-2) !! (k-2)
a020474_row n = a020474_tabl !! (n-2)
a020474_tabl = map fst $ iterate f ([1], [0, 1]) where
f (us, vs) = (vs, scanl (+) 0 ws) where
ws = zipWith (+) (us ++ [0]) vs
(Sage)
@cached_function
def T(n, k):
if k<0 or n<k: return 0
if k==0: return 0^n
return T(n, k-1) + T(n-1, k-1) + T(n-2, k-1)
for n in (0..8): print([T(n, k) for k in (0..n)]) # Peter Luschny, Jun 23 2015
|
|
CROSSREFS
|
The triangle version of A062105 has the same recurrence with different initial conditions. - N. J. A. Sloane, Apr 11 2020
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|