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
Reinhard Zumkeller, Rows n = 2..120 of triangle, flattened
M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.
J. L. Chandon, J. LeMaire and J. Pouget, Denombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.
R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
Paul Peart and Wen-jin Woan, A divisibility property for a subgroup of Riordan matrices, Discrete Appl. Math. 98 (2000), 255-263.
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)];
for n from 0 to M do lprint(rho(n)); od: # N. J. A. Sloane, Apr 11 2020
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
-- Reinhard Zumkeller, Jan 03 2013
(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
KEYWORD
AUTHOR
EXTENSIONS
More terms from James A. Sellers, Feb 04 2000
STATUS
approved