A064645 Table where the entry (n,k) (n >= 0, k >= 0) gives number of Motzkin paths of the length n with the minimum peak width of k.

1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 9, 2, 1, 1, 1, 21, 4, 1, 1, 1, 1, 51, 8, 2, 1, 1, 1, 1, 127, 17, 4, 1, 1, 1, 1, 1, 323, 37, 8, 2, 1, 1, 1, 1, 1, 835, 82, 16, 4, 1, 1, 1, 1, 1, 1, 2188, 185, 33, 8, 2, 1, 1, 1, 1, 1, 1, 5798, 423, 69, 16, 4, 1, 1, 1, 1, 1, 1, 1, 15511, 978, 146, 32, 8, 2, 1, 1, 1, 1, 1, 1, 1, 41835, 2283, 312, 65, 16, 4, 1, 1, 1, 1, 1, 1, 1, 1

Offset

0,4

Links

Seiichi Manyama, Table of n, a(n) for n = 0..9869 (rows n=0..139 of triangle, flattened)

Example

E.g., we have the following nine Motzkin paths of length 4, of which the last 4 have each peak at least of width 1 and the last 2 with each peak at least 2 dashes wide, so M(4,0) = 9, M(4,1) = 4 and M(4,2) = 2.
   /\                                 _       _     __
  /  \   /\/\   __/\   _/\_   /\__   / \_   _/ \   /  \   ____
The array starts:
      1    1   1   1   1   1   1   1   1   1   1
      1    1   1   1   1   1   1   1   1   1   1
      2    1   1   1   1   1   1   1   1   1   1
      4    2   1   1   1   1   1   1   1   1   1
      9    4   2   1   1   1   1   1   1   1   1
     21    8   4   2   1   1   1   1   1   1   1
     51   17   8   4   2   1   1   1   1   1   1
    127   37  16   8   4   2   1   1   1   1   1
    323   82  33  16   8   4   2   1   1   1   1
    835  185  69  32  16   8   4   2   1   1   1
   2188  423 146  65  32  16   8   4   2   1   1
   5798  978 312 133  64  32  16   8   4   2   1
  15511 2283 673 274 129  64  32  16   8   4   2

Maple

# trinv() given in A054425
[seq(A064645(j), j=0..104)]; A064645 := (n) -> Mpw((((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), (n-((trinv(n)*(trinv(n)-1))/2)));
C := (n, k) -> `if`((n <= 0), 0, binomial(n, k));
Mpw := proc(n, m) local i, k; 1+add(add(A001263(i, k)*C(n-(m*k), 2*i), k=1..i), i=0..floor(n/2)); end;

Mathematica

trinv[n_] := Floor[(1 + Sqrt[8 n + 1])/2];
CC[n_, k_] := If[n <= 0, 0, Binomial[n, k]];
a[n_] := Mpw[(((trinv[n] - 1)*(((1/2) trinv[n]) + 1)) - n), (n - ((trinv[n] (trinv[n] - 1))/2))];
Mpw[n_, m_] := 1 + Sum[Sum[If[k == 0, 0, Binomial[i - 1, k - 1] Binomial[i, k - 1]/k] CC[n - m*k, 2i], {k, 1, i}], {i, 0, n/2}];
Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Mar 06 2016, adapted from Maple *)

Crossrefs

Column k=0: Motzkin numbers (A001006), column k=1: A004148, column k=2: A004149, column k=3: A023421, column k=4: A023422, column k=5: A023423. Uses the table A001263(n, k).

Sequence in context: A257598 A294580 A294587 * A285425 A008307 A249694

Adjacent sequences: A064642 A064643 A064644 * A064646 A064647 A064648

Keyword

nonn,tabl

Author

Antti Karttunen, Oct 03 2001

Status

approved