A101920 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k up steps starting at an odd height.

2, 5, 1, 13, 8, 1, 34, 42, 13, 1, 89, 183, 102, 19, 1, 233, 717, 624, 205, 26, 1, 610, 2622, 3275, 1650, 366, 34, 1, 1597, 9134, 15473, 11020, 3716, 602, 43, 1, 4181, 30691, 67684, 64553, 30520, 7483, 932, 53, 1, 10946, 100284, 279106, 342867, 215481

Offset

1,1

Comments

A Schroeder path of length 2n is a lattice path starting from (0,0), ending at (2n,0), consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis (Schroeder paths are counted by the large Schroeder numbers, A006318). Row sums are the large Schroeder numbers (A006318). Column 0 yields the odd-indexed Fibonacci numbers (A001519).

Links

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

Formula

G.f.=G=G(t, z) satisfies tz(1-z)G^2-(1-3z+tz+z^2)G+1-z=0.

Example

T(3,1)=8 because we have HUU'DD, UDUU'DD, UU'DDH, UU'DDUD, UHU'DD, UU'DHD, UU'HDD and UU'UDDD, the up steps starting at odd heights being shown with the prime sign.
Triangle begins:
2;
5,1;
13,8,1;
34,42,13,1;
89,183,102,19,1;

Maple

G := 1/2/(-t*z+t*z^2)*(-1+3*z-t*z-z^2+sqrt(1-6*z-2*t*z+11*z^2+2*t*z^2-6*z^3+t^2*z^2-2*t*z^3+z^4)): Gser:=simplify(series(G, z=0, 13)):for n from 1 to 11 do P[n]:=coeff(Gser, z^n) od: for n from 1 to 11 do seq(coeff(t*P[n], t^k), k=1..n) od; # yields the sequence in triangular form

Crossrefs

Cf. A006318, A001519, A101919.

Sequence in context: A156067 A352577 A263487 * A114494 A118964 A263771

Adjacent sequences: A101917 A101918 A101919 * A101921 A101922 A101923

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 20 2004

Status

approved