A105640 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k UUDD's, where U=(1,1) and D=(1,-1) (0<=k<=floor(n/2), n>=2). A hill in a Dyck path is a peak at level 1.

0, 1, 1, 1, 2, 3, 1, 5, 10, 3, 14, 29, 13, 1, 39, 89, 52, 6, 111, 279, 195, 36, 1, 322, 881, 722, 185, 10, 947, 2806, 2637, 867, 80, 1, 2818, 8997, 9528, 3846, 520, 15, 8470, 28997, 34163, 16382, 2976, 155, 1, 25677, 93858, 121749, 67696, 15631, 1246, 21

Offset: 2

Author

Emeric Deutsch, May 08 2006

Keywords

• nonn
• tabf

Comments

Row n has 1+floor(n/2) terms. Row sums are the Fine numbers (A000957). T(n,0)=A105641(n). Sum(k*T(n,k),k=0..floor(n/2))=A116914(n).

Examples

			T(5,2)=3 because we have U(UUDD)(UUDD)D, (UUDD)U(UUDD)D and U(UUDD)D(UUDD) (the UUDD's are shown between parentheses).
Triangle starts:
  0,1;
  1,1;
  2,3,1;
  5,10,3;
  14,29,13,1;
  ...
		

Links

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

Crossrefs

Cf. A000957, A105641, A116914.

Programs

Maple

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

Formula

G.f.: G-1, where G =G(t,z) satisfies z(2+z+z^2-tz^2)G^2-(1+2z+z^2-tz^2)G+1=0.