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

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*T(n,k),k=1..n)=A118974(n)

Links

Table of n, a(n) for n=1..72.

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

Formula

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

Example

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

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

Crossrefs

Cf. A000957, A001558, A118973, A118974.

Sequence in context: A291680 A193283 A193277 * A171224 A270741 A212220

Adjacent sequences: A118969 A118970 A118971 * A118973 A118974 A118975

Keyword

nonn,tabl

Author

Emeric Deutsch, May 08 2006

Status

approved