login
Triangle read by rows: T(n,k) is the number of dispersed Dyck prefixes (i.e., left factors of Motzkin paths with no (1,0) steps at positive heights) of length n and height k.
3

%I #30 Dec 04 2018 07:19:21

%S 1,1,1,1,2,1,1,4,2,1,1,7,5,2,1,1,12,10,6,2,1,1,20,21,12,7,2,1,1,33,41,

%T 28,14,8,2,1,1,54,81,56,36,16,9,2,1,1,88,155,120,72,45,18,10,2,1,1,

%U 143,297,239,165,90,55,20,11,2,1,1,232,560,492,330,220,110,66,22,12,2,1,1,376,1054,974,715,440,286,132,78,24,13,2,1

%N Triangle read by rows: T(n,k) is the number of dispersed Dyck prefixes (i.e., left factors of Motzkin paths with no (1,0) steps at positive heights) of length n and height k.

%C Row n has n+1 entries.

%H Alois P. Heinz, <a href="/A282869/b282869.txt">Rows n = 0..140, flattened</a>

%H Steven R. Finch, <a href="https://arxiv.org/abs/1802.04615">How far might we walk at random?</a>, arXiv:1802.04615 [math.HO], 2018.

%F T(n,1) = A000071(n+1), (Fibonacci numbers minus 1).

%e Triangle starts:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 4, 2, 1;

%e 1, 7, 5, 2, 1;

%e 1, 12, 10, 6, 2, 1;

%e 1, 20, 21, 12, 7, 2, 1;

%e ...

%e T(4,3) = 2 because we have UUUD and HUUU, where U=(1,1), D=(1,-1), H=(1,0).

%e T(4,2) = 5 because we have UUDD, UUDU, UDUU, HUUD and HHUU.

%p b:= proc(x, y, m) option remember;

%p `if`(x=0, z^m, `if`(y>0, b(x-1, y-1, m), 0)+

%p `if`(y=0, b(x-1, y, m), 0)+b(x-1, y+1, max(m, y+1)))

%p end:

%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..16); # _Alois P. Heinz_, Mar 13 2017

%t b[x_, y_, m_] := b[x, y, m] = If[x == 0, z^m, If[y > 0, b[x - 1, y - 1, m], 0] + If[y == 0, b[x - 1, y, m], 0] + b[x - 1, y + 1, Max[m, y + 1]]];

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

%t Table[T[n], {n, 0, 16}] // Flatten (* _Jean-François Alcover_, May 12 2017, after _Alois P. Heinz_ *)

%Y Row sums give A000079.

%Y T(2n,n) gives A283799.

%Y Cf. A000071, A191314.

%K nonn,tabl

%O 0,5

%A _Steven Finch_, Feb 23 2017