A348840 Triangle T(n,h) read by rows: The number of Motzkin Paths of n>=2 steps that start with an Up step and touch the horizontal axis h>=1 times afterwards.

1, 1, 1, 2, 2, 1, 4, 4, 3, 1, 9, 9, 7, 4, 1, 21, 21, 17, 11, 5, 1, 51, 51, 42, 29, 16, 6, 1, 127, 127, 106, 76, 46, 22, 7, 1, 323, 323, 272, 200, 128, 69, 29, 8, 1, 835, 835, 708, 530, 352, 204, 99, 37, 9, 1, 2188, 2188, 1865, 1415, 965, 587, 311, 137, 46, 10, 1, 5798, 5798, 4963

Offset

2,4

Comments

To touch means: the path reaches the horizontal line with a down-step, or it is at the horizontal level and takes another horizontal step.

Links

Alois P. Heinz, Rows n = 2..150, flattened

Formula

Conjecture: T(n,n-2) = n-2.

Conjecture: T(n,n-3) = A000124(n-3).

Conjecture: T(n,n-4) = -11 + 19*n/3 - 3*n^2/2 + n^3/6.

From Alois P. Heinz, Nov 01 2021: (Start)

Sum_{k=1..n-1} k * T(n,k) = A005322(n).

T(2n,n) = A344502(n-1) for n >= 1. (End)

Conjecture: Riordan array (g(x)^2, x*g(x)), where g(x) = 1/(1 + x)*c(x/(1 + x)) and c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Feb 04 2024

Example

The triangle starts:
     1
     1    1
     2    2    1
     4    4    3    1
     9    9    7    4    1
    21   21   17   11    5    1
    51   51   42   29   16    6   1
   127  127  106   76   46   22   7   1
   323  323  272  200  128   69  29   8   1
   835  835  708  530  352  204  99  37   9  1
  2188 2188 1865 1415  965  587 311 137  46 10  1
  5798 5798 4963 3805 2647 1667 937 457 184 56 11  1
  ...
T(n,n-1)=1 counts udhhhhh... staying on the horizontal line.
T(4,1)=2 counts uudd, uhhd.
T(4,2)=2 counts udud, uhdh.
T(4,3)=1 counts udhh.
T(5,1)=4 counts uudhd uuhdd uhudd uhhhd.
T(5,2)=4 counts uuddh uduhd uhdud uhhdh.
T(5,3)=3 counts ududh udhud uhdhh.
T(5,4)=1 counts udhhh.

Maple

b:= proc(x, y) option remember; expand(`if`(y>x or y<0, 0,
     `if`(x=0, 1, add(b(x-1, y-j), j=-1..1))*`if`(y=0, z, 1)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n-1))(b(n-1, 1)):
seq(T(n), n=2..14);  # Alois P. Heinz, Nov 01 2021

Mathematica

b[x_, y_] := b[x, y] = Expand[If[y > x || y < 0, 0,
     If[x == 0, 1, Sum[b[x - 1, y - j], {j, -1, 1}]]*If[y == 0, z, 1]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n-1}]][b[n-1, 1]];
Table[T[n], {n, 2, 14}] // Flatten (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

Crossrefs

Cf. A002026 (row sums), A001006 (columns h=1,2), A102071 (column h=3).

Cf. A000108, A005322, A344502.

Sequence in context: A104040 A338131 A332601 * A182222 A225639 A110664

Adjacent sequences: A348837 A348838 A348839 * A348841 A348842 A348843

Keyword

nonn,tabl

Author

R. J. Mathar, Nov 01 2021

Status

approved