login
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.
2
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
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
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 08 2006
STATUS
approved