A118972 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having length of first descent equal to k (1<=k<=n; n>=1). A hill in a Dyck path is a peak at level 1.

0, 0, 1, 1, 0, 1, 3, 2, 0, 1, 10, 5, 2, 0, 1, 33, 16, 5, 2, 0, 1, 111, 51, 16, 5, 2, 0, 1, 379, 168, 51, 16, 5, 2, 0, 1, 1312, 565, 168, 51, 16, 5, 2, 0, 1, 4596, 1934, 565, 168, 51, 16, 5, 2, 0, 1, 16266, 6716, 1934, 565, 168, 51, 16, 5, 2, 0, 1, 58082, 23604, 6716, 1934, 565, 168

Offset: 1

Author

Emeric Deutsch, May 08 2006

Keywords

• nonn
• tabl

Comments

Row sums are the Fine numbers (A000957).

T(n,1) = A001558(n-3) for n>=3.

T(n,k) = A118973(n-k) for n>=k>=2.

Sum_{k=1..n} k*T(n,k) = A118974(n).

Examples

			T(5,2)=5 because we have uu(dd)uududd, uu(dd)uuuddd,uuu(dd)uuddd,uuu(dd)ududd and uuuu(dd)uddd, where u=(1,1), d=(1,-1) (the first descents are shown between parentheses).
Triangle starts:
  0;
  0,1;
  1,0,1;
  3,2,0,1;
  10,5,2,0,1;
  33,16,5,2,0,1;
  ...
		

Links

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

Crossrefs

Cf. A000957, A001558, A118973, A118974.

Programs

Maple

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

Formula

G.f.: t*z^2*C*F*(C-(1-t)/(1-t*z)), where F = (1-sqrt(1-4*z))/(z*(3-sqrt(1-4*z))) and C = (1-sqrt(1-4*z))/(2*z) is the Catalan function.