A097607 - OEIS

A097607

Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having leftmost valley at altitude k (if path has no valleys, then this altitude is considered to be 0).

1, 1, 2, 4, 1, 9, 4, 1, 23, 13, 5, 1, 65, 41, 19, 6, 1, 197, 131, 67, 26, 7, 1, 626, 428, 232, 101, 34, 8, 1, 2056, 1429, 804, 376, 144, 43, 9, 1, 6918, 4861, 2806, 1377, 573, 197, 53, 10, 1, 23714, 16795, 9878, 5017, 2211, 834, 261, 64, 11, 1, 82500, 58785, 35072

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

FORMULA

G.f.: (1-z+zC-tzC)/[(1-z)(1-tzC)], where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

From Alois P. Heinz, Nov 25 2025: (Start)

Sum_{k>0} k * T(n,k) = A143955(n).

Sum_{k>=0} (-1)^k * T(n,k) = A193215(n). (End)

EXAMPLE

Triangle starts:

4, 1;

9, 4, 1;

23, 13, 5, 1;

65, 41, 19, 6, 1;

...

T(4,1) = 4 because we have UU(DU)DDUD, UU(DU)DUDD, UU(DU)UDDD and UUUD(DU)DD, where U=(1,1), D=(1,-1); the first valleys, all at altitude 1, are shown between parentheses.

MAPLE

b:= proc(x, y, h, t) option remember; `if`(y>x or y<0, 0,

`if`(x=0, z^max(h, 0), b(x-1, y-1, h, true)+

b(x-1, y+1, `if`(t and h<0, y, h), false)))

end:

T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, -1, false)):

seq(T(n), n=0..12); # Alois P. Heinz, Nov 25 2025

CROSSREFS

Row sums are the Catalan numbers (A000108).

Column 0 is A014137 (partial sums of Catalan numbers).

Column 1 is A001453 (Catalan numbers -1).

Cf. A143955, A193215.