cp's OEIS Frontend

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

%I A020474 #46 Jul 02 2025 16:01:55
%S A020474 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,
%T A020474 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,
%U A020474 0,0,1,20,133,518,1353,2188,0,0,0,0,0,0,6,70,392,1422,3610,5798,0,0,0,0
%N A020474 A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.
%C A020474 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
%H A020474 Reinhard Zumkeller, <a href="/A020474/b020474.txt">Rows n = 2..120 of triangle, flattened</a>
%H A020474 M. Aigner, <a href="http://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.
%H A020474 R. De Castro, A. L. Ramírez and J. L. Ramírez, <a href="http://arxiv.org/abs/1310.2449">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.
%H A020474 J. L. Chandon, J. LeMaire and J. Pouget, <a href="http://www.numdam.org/item?id=MSH_1978__62__61_0">Denombrement des quasi-ordres sur un ensemble fini</a>, Math. Sci. Humaines, No. 62 (1978), 61-80.
%H A020474 R. Donaghey and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, 23 (1977), 291-301.
%H A020474 Paul Peart and Wen-jin Woan, <a href="http://dx.doi.org/10.1016/S0166-218X(99)00166-3">A divisibility property for a subgroup of Riordan matrices</a>, Discrete Appl. Math. 98 (2000), 255-263.
%F A020474 a(n,k) = a(n,k-1) + a(n-1,k-1) + a(n-2,k-1), n > k >= 2.
%e A020474 Triangle begins:
%e A020474   1
%e A020474   0, 1
%e A020474   0, 1, 2
%e A020474   0, 0, 2, 4
%e A020474   0, 0, 1, 5,  9
%e A020474   0, 0, 0, 3, 12, 21
%e A020474   0, 0, 0, 1,  9, 30, 51
%e A020474   0, 0, 0, 0,  4, 25, 76, 127
%e A020474   0, 0, 0, 0,  1, 14, 69, 196, 323
%p A020474 M:=16; T:=Array(0..M,0..M,0);
%p A020474 T[0,0]:=1; T[1,1]:=1;
%p A020474 for i from 1 to M do T[i,0]:=0; od:
%p A020474 for n from 2 to M do for k from 1 to n do
%p A020474 T[n,k]:= T[n,k-1]+T[n-1,k-1]+T[n-2,k-1];
%p A020474 od: od;
%p A020474 rho:=n->[seq(T[n,k],k=0..n)];
%p A020474 for n from 0 to M do lprint(rho(n)); od: # _N. J. A. Sloane_, Apr 11 2020
%t A020474 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 *)
%o A020474 (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_
%o A020474 (Haskell)
%o A020474 a020474 n k = a020474_tabl !! (n-2) !! (k-2)
%o A020474 a020474_row n = a020474_tabl !! (n-2)
%o A020474 a020474_tabl = map fst $ iterate f ([1], [0,1]) where
%o A020474    f (us,vs) = (vs, scanl (+) 0 ws) where
%o A020474      ws = zipWith (+) (us ++ [0]) vs
%o A020474 -- _Reinhard Zumkeller_, Jan 03 2013
%o A020474 (Sage)
%o A020474 @cached_function
%o A020474 def T(n, k):
%o A020474     if k<0 or n<k: return 0
%o A020474     if k==0: return 0^n
%o A020474     return T(n,k-1) + T(n-1,k-1) + T(n-2,k-1)
%o A020474 for n in (0..8): print([T(n,k) for k in (0..n)]) # _Peter Luschny_, Jun 23 2015
%Y A020474 Main diagonal is A001006.
%Y A020474 Other diagonals include A002026, A005322, A005323, A005324, A005325. Row sums are (essentially) A005043.
%Y A020474 The triangle version of A062105 has the same recurrence with different initial conditions. - _N. J. A. Sloane_, Apr 11 2020
%K A020474 nonn,tabl,easy,nice
%O A020474 2,6
%A A020474 _N. J. A. Sloane_
%E A020474 More terms from _James Sellers_, Feb 04 2000