A364386 Triangle T(n,k) read by rows: the number of Motzkin paths of length n that have k nodes at their peak level, 1 <= k <= n+1.

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 8, 7, 4, 1, 0, 1, 18, 15, 11, 5, 1, 0, 1, 44, 33, 26, 16, 6, 1, 0, 1, 113, 78, 59, 42, 22, 7, 1, 0, 1, 296, 197, 138, 101, 64, 29, 8, 1, 0, 1, 782, 518, 342, 240, 165, 93, 37, 9, 1, 0, 1, 2076, 1388, 892, 590, 406, 258, 130, 46, 10, 1, 0, 1

Offset

0,7

Links

Alois P. Heinz, Rows n = 0..140, flattened

Formula

T(n,n) = 1. (All nodes on level 0, only H steps.)

T(n,n-1) = 0.

T(n,n-2) = 1. (steps UHHH...HHHD)

Example

Example for 9 paths of length n=4: UUDD (k=1 at level 2), UHHD (k=3 at level 1), UHDH (k=2 at level 1), UDUD (k=2 at level 1), UDHH (k=1 at level 1), HUHD (k=2 at level 1), HUDH (k=1 at level 1), HHUD (k=1 at level 1), HHHH (k=5 at level 0). So k=1 appears 4 times, k=2 3 times, k=3 once, k=4 never, k=5 once.
The triangle starts:
      1
      0,     1
      1,     0,    1
      2,     1,    0,    1
      4,     3,    1,    0,    1
      8,     7,    4,    1,    0,    1
     18,    15,   11,    5,    1,    0,    1
     44,    33,   26,   16,    6,    1,    0,   1
    113,    78,   59,   42,   22,    7,    1,   0,   1
    296,   197,  138,  101,   64,   29,    8,   1,   0,  1
    782,   518,  342,  240,  165,   93,   37,   9,   1,  0,  1
   2076,  1388,  892,  590,  406,  258,  130,  46,  10,  1,  0, 1
   5538,  3747, 2401, 1522, 1005,  665,  388, 176,  56, 11,  1, 0, 1
  14856, 10147, 6560, 4085, 2576, 1680, 1054, 564, 232, 67, 12, 1, 0, 1
  ...

Crossrefs

Cf. A001006 (row sums), A088457 (column k=1).

Cf. A152879 (equivalent for Dyck paths).

Sequence in context: A119328 A058716 A048723 * A088455 A361390 A369326

Adjacent sequences: A364383 A364384 A364385 * A364387 A364388 A364389

Keyword

nonn,tabl

Author

R. J. Mathar, Jul 21 2023

Status

approved