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,5

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).

Links

Table of n, a(n) for n=2..55.

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

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.

Example

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;
  ...

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

Crossrefs

Cf. A000957, A105641, A116914.

Sequence in context: A030103 A255589 A290053 * A090299 A060693 A172381

Adjacent sequences: A105637 A105638 A105639 * A105641 A105642 A105643

Keyword

nonn,tabf

Author

Emeric Deutsch, May 08 2006

Status

approved