login
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.
4

%I #30 Feb 04 2024 18:23:18

%S 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,

%T 127,106,76,46,22,7,1,323,323,272,200,128,69,29,8,1,835,835,708,530,

%U 352,204,99,37,9,1,2188,2188,1865,1415,965,587,311,137,46,10,1,5798,5798,4963

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A348840/b348840.txt">Rows n = 2..150, flattened</a>

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

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

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

%F From _Alois P. Heinz_, Nov 01 2021: (Start)

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

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

%F 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

%e The triangle starts:

%e 1

%e 1 1

%e 2 2 1

%e 4 4 3 1

%e 9 9 7 4 1

%e 21 21 17 11 5 1

%e 51 51 42 29 16 6 1

%e 127 127 106 76 46 22 7 1

%e 323 323 272 200 128 69 29 8 1

%e 835 835 708 530 352 204 99 37 9 1

%e 2188 2188 1865 1415 965 587 311 137 46 10 1

%e 5798 5798 4963 3805 2647 1667 937 457 184 56 11 1

%e ...

%e T(n,n-1)=1 counts udhhhhh... staying on the horizontal line.

%e T(4,1)=2 counts uudd, uhhd.

%e T(4,2)=2 counts udud, uhdh.

%e T(4,3)=1 counts udhh.

%e T(5,1)=4 counts uudhd uuhdd uhudd uhhhd.

%e T(5,2)=4 counts uuddh uduhd uhdud uhhdh.

%e T(5,3)=3 counts ududh udhud uhdhh.

%e T(5,4)=1 counts udhhh.

%p b:= proc(x, y) option remember; expand(`if`(y>x or y<0, 0,

%p `if`(x=0, 1, add(b(x-1, y-j), j=-1..1))*`if`(y=0, z, 1)))

%p end:

%p T:= n-> (p-> seq(coeff(p, z, i), i=1..n-1))(b(n-1, 1)):

%p seq(T(n), n=2..14); # _Alois P. Heinz_, Nov 01 2021

%t b[x_, y_] := b[x, y] = Expand[If[y > x || y < 0, 0,

%t If[x == 0, 1, Sum[b[x - 1, y - j], {j, -1, 1}]]*If[y == 0, z, 1]]];

%t T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n-1}]][b[n-1, 1]];

%t Table[T[n], {n, 2, 14}] // Flatten (* _Jean-François Alcover_, Mar 17 2022, after _Alois P. Heinz_ *)

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

%Y Cf. A000108, A005322, A344502.

%K nonn,tabl

%O 2,4

%A _R. J. Mathar_, Nov 01 2021