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

Author

R. J. Mathar, Nov 01 2021

Keywords

• nonn
• tabl

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.

Examples

			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.
		

Links

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

Crossrefs

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

Cf. A000108, A005322, A344502.

Programs

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 *)

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