|
| |
|
|
A020474
|
|
A Motzkin triangle: a(n,k), n >= 2, 1<=k<=n, = number of complete, strictly subdiagonal staircase functions.
|
|
9
| |
|
|
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; 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 (callan(AT)stat.wisc.edu), Sep 25 2006
|
|
|
REFERENCES
| Martin Aigner, Motzkin numbers. European J. Combin. 19 (1998), 663-675.
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
| 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
|
|
|
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 (callan(AT)stat.wisc.edu), 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))) (from R. Stephan)
|
|
|
CROSSREFS
| Main diagonal is A001006.
Other diagonals include A002026, A005322, A005323, A005324, A005325. Row sums are (essentially) A005043.
Sequence in context: A115509 A134312 A195581 * A135589 A158122 A028641
Adjacent sequences: A020471 A020472 A020473 * A020475 A020476 A020477
|
|
|
KEYWORD
| nonn,tabl,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from James A. Sellers (sellersj(AT)math.psu.edu), Feb 04 2000
|
| |
|
|
