A119011 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k valleys strictly above the x-axis (0<=k<=n-2; n>=2). A hill in a Dyck path is a peak at level 1.

1, 1, 1, 2, 3, 1, 3, 8, 6, 1, 5, 18, 23, 10, 1, 8, 38, 70, 54, 15, 1, 13, 76, 186, 215, 110, 21, 1, 21, 147, 451, 710, 560, 202, 28, 1, 34, 277, 1025, 2065, 2269, 1288, 343, 36, 1, 55, 512, 2220, 5480, 7854, 6321, 2688, 548, 45, 1, 89, 932, 4634, 13574, 24227, 25830

Offset: 2

Author

Emeric Deutsch, May 08 2006

Keywords

• nonn
• tabl

Comments

Row sums yield the Fine numbers (A000957). T(n,0)=A000045(n-1) (the Fibonacci numbers). T(n,1)=A006478(n). Sum(k*T(n,k),k=0..n-2)=A119012(n)

Examples

			T(5,2)=6 because we have uud|ud|uuddd, uuudd|ud|udd, uud|uudd|udd, uuud|ud|uddd, uuud|udd|udd and uud|uud|uddd (the valleys above the x-axis are marked with |).
Triangle starts:
1;
1,1;
2,3,1;
3,8,6,1;
5,18,23,10,1;
		

Links

• E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Crossrefs

Cf. A000957, A000045, A006478, A119012.

Programs

Maple

G:=2*t/(2*t+z*t+z-1+sqrt(z^2*t^2-2*z^2*t-2*z*t+z^2-2*z+1))-1: Gser:=simplify(series(G,z=0,15)): for n from 2 to 12 do P[n]:=sort(coeff(Gser,z^n)) od: for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form

Formula

G.f.: G(t,z)=1/[1-zr(t,z)]-1, where r=r(t,z) is the Narayana function, defined by (1+r)(1+tr)z=r, r(t,0)=0. See Maple program for the explicit form of G(t,z).