login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
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. 14
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 (list; table; graph; refs; listen; history; text; internal format)
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

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

Sequence in context: A329790 A343649 A195581 * A135589 A244312 A158122

Adjacent sequences: A020471 A020472 A020473 * A020475 A020476 A020477

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from James A. Sellers, Feb 04 2000

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 6 15:54 EST 2022. Contains 358644 sequences. (Running on oeis4.)