login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A020474 A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions. 12

%I

%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

%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.

%K nonn,tabl,easy,nice

%O 2,6

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Feb 04 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 18 17:08 EST 2018. Contains 299325 sequences. (Running on oeis4.)