A094449 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having sum of pyramid heights equal to k.

1, 0, 1, 0, 0, 2, 1, 0, 0, 4, 4, 2, 0, 0, 8, 13, 8, 5, 0, 0, 16, 42, 26, 20, 12, 0, 0, 32, 139, 85, 65, 48, 28, 0, 0, 64, 470, 286, 214, 156, 112, 64, 0, 0, 128, 1616, 982, 727, 517, 364, 256, 144, 0, 0, 256, 5632, 3420, 2518, 1772, 1214, 832, 576, 320, 0, 0, 512, 19852

Offset

0,6

Comments

A pyramid in a Dyck path is a factor of the form U^j D^j (j>0), starting at the x-axis. Here U=(1,1) and D=(1,-1). This definition differs from the one in A091866. Column k=0 is A082989. Row sums are the Catalan numbers (A000108).

Links

Table of n, a(n) for n=0..66.

Formula

G.f.: G(t, z) = (1-t*z)*(1-z)/(1-2*t*z+t*z^2-z*(1-z)*(1-t*z)*C), where C = (1-sqrt(1-4*z))/(2*z) is the Catalan function.

Example

T(3,3)=4 because there are four Dyck paths of semilength 3 having 3 as sum of pyramid heights: (UD)(UUDD),(UUDD)(UD),(UD)(UD)(UD) and (UUUDDD) (the pyramids are shown between parentheses).
Triangle begins:
  [1];
  [0, 1];
  [0, 0, 2];
  [1, 0, 0, 4];
  [4, 2, 0, 0, 8];
  [13, 8, 5, 0, 0, 16];
  [42, 26, 20, 12, 0, 0, 32];

Maple

C:=(1-sqrt(1-4*z))/2/z: G:=(1-t*z)*(1-z)/(1-2*t*z+t*z^2-z*C*(1-z)*(1-t*z)): Gserz:=simplify(series(G, z=0, 16)): P[0]:=1: for n from 1 to 14 do P[n]:=sort(coeff(Gserz, z^n)) od: seq([subs(t=0, P[n]), seq(coeff(P[n], t^k), k=1..n)], n=0..14);

Crossrefs

Cf. A082989, A000108.

Sequence in context: A121465 A383235 A192396 * A274776 A274777 A136129

Adjacent sequences: A094446 A094447 A094448 * A094450 A094451 A094452

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 04 2004

Status

approved