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

Author

Emeric Deutsch, Jun 04 2004

Keywords

• nonn
• tabl

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

Examples

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

Crossrefs

Cf. A082989, A000108.

Programs

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

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.