|
%I #45 Apr 11 2020 14:57:44
%S 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 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 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 A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.
%C 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 Reinhard Zumkeller, <a href="/A020474/b020474.txt">Rows n = 2..120 of triangle, flattened</a>
%H M. Aigner, <a href="http://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.
%H 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 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 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 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 a(n,k) = a(n,k-1) + a(n-1,k-1) + a(n-2,k-1), n > k >= 2.
%e Triangle begins:
%e 1
%e 0, 1
%e 0, 1, 2
%e 0, 0, 2, 4
%e 0, 0, 1, 5, 9
%e 0, 0, 0, 3, 12, 21
%e 0, 0, 0, 1, 9, 30, 51
%e 0, 0, 0, 0, 4, 25, 76, 127
%e 0, 0, 0, 0, 1, 14, 69, 196, 323
%p M:=16; T:=Array(0..M,0..M,0);
%p T[0,0]:=1; T[1,1]:=1;
%p for i from 1 to M do T[i,0]:=0; od:
%p for n from 2 to M do for k from 1 to n do
%p T[n,k]:= T[n,k-1]+T[n-1,k-1]+T[n-2,k-1];
%p od: od;
%p rho:=n->[seq(T[n,k],k=0..n)];
%p for n from 0 to M do lprint(rho(n)); od: # _N. J. A. Sloane_, Apr 11 2020
%t 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 (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 (Haskell)
%o a020474 n k = a020474_tabl !! (n-2) !! (k-2)
%o a020474_row n = a020474_tabl !! (n-2)
%o a020474_tabl = map fst $ iterate f ([1], [0,1]) where
%o f (us,vs) = (vs, scanl (+) 0 ws) where
%o ws = zipWith (+) (us ++ [0]) vs
%o -- _Reinhard Zumkeller_, Jan 03 2013
%o (Sage)
%o @cached_function
%o def T(n, k):
%o if k<0 or n<k: return 0
%o if k==0: return 0^n
%o return T(n,k-1) + T(n-1,k-1) + T(n-2,k-1)
%o for n in (0..8): print([T(n,k) for k in (0..n)]) # _Peter Luschny_, Jun 23 2015
%Y Main diagonal is A001006.
%Y Other diagonals include A002026, A005322, A005323, A005324, A005325. Row sums are (essentially) A005043.
%Y The triangle version of A062105 has the same recurrence with different initial conditions. - _N. J. A. Sloane_, Apr 11 2020
%K nonn,tabl,easy,nice
%O 2,6
%A _N. J. A. Sloane_
%E More terms from _James A. Sellers_, Feb 04 2000
|
