A020474 A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.

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

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• easy
• nice

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

Examples

			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
		

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.

Crossrefs

Main diagonal is A001006.

Other diagonals include A002026, A005322, A005323, A005324, A005325. Row sums are (essentially) A005043.

The triangle version of A062105 has the same recurrence with different initial conditions. - N. J. A. Sloane, Apr 11 2020

Programs

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

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 *)

PARI

T(n,k)=if(n==0&&k==0,1,if(n<=0||k<=0||nRalf Stephan

Sage

@cached_function
def T(n, k):
    if k<0 or nPeter Luschny, Jun 23 2015

Formula

a(n,k) = a(n,k-1) + a(n-1,k-1) + a(n-2,k-1), n > k >= 2.

Extensions

More terms from James Sellers, Feb 04 2000