A109157 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and having sum of the heights of its pyramids equal to k (a pyramid is a sequence u^pd^p or U^pd^(2p) for some positive integer p, starting at the x-axis; p is the height of the pyramid).

1, 0, 1, 1, 4, 0, 2, 2, 2, 32, 8, 8, 4, 5, 5, 4, 252, 64, 84, 24, 28, 12, 14, 12, 8, 2112, 520, 680, 240, 232, 88, 76, 37, 37, 28, 16, 18484, 4480, 5804, 1992, 2012, 776, 656, 264, 206, 106, 94, 64, 32, 166976, 40008, 51592, 17440, 17400, 6776, 5680, 2392, 1768

Offset

0,5

Comments

Row n has 2n+1 terms. Row sums yield A027307. Column 0 yields A108449.

Links

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

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Formula

G.f. = (1-z)(1-tz)(1-t^2*z)/[1-2tz-2t^2*z+z+3t^3*z^2-t^3*z^3-z(1-z)(1-t^2*z)(1-tz)A(1+A)], where A=1+zA^2+zA^3=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

Example

T(2,3)=2 because we have udUdd and Uddud.
Triangle begins:
1;
0,1,1;
4,0,2,2,2;
32,8,8,4,5,5,4;
252,64,84,24,28,12,14,12,8;

Maple

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=-(-1+z)*(-1+t*z)*(-1+t^2*z)/(z*(-1+z)*(-1+t^2*z)*(-1+t*z)*A*(1+A)+1-2*t*z-2*t^2*z+z+3*t^3*z^2-t^3*z^3): Gser:=simplify(series(G, z=0, 10)): P[0]:=1: for n from 1 to 7 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 7 do seq(coeff(t*P[n], t^k), k=1..2*n+1) od; # yields sequence in triangular form

Crossrefs

Cf. A027307, A108449.

Sequence in context: A320479 A218769 A180850 * A226955 A123314 A058997

Adjacent sequences: A109154 A109155 A109156 * A109158 A109159 A109160

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 20 2005

Status

approved