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

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)

Links

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

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

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

Example

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;

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

Crossrefs

Cf. A000957, A000045, A006478, A119012.

Sequence in context: A295380 A093768 A209419 * A340440 A300866 A130477

Adjacent sequences: A119008 A119009 A119010 * A119012 A119013 A119014

Keyword

nonn,tabl

Author

Emeric Deutsch, May 08 2006

Status

approved