A132883 Triangle read by rows: T(n,k) is the number of paths in the first quadrant from (0,0) to (n,0), consisting of steps U=(1,1), D=(1,-1), h=(1,0) and H=(2,0), having k U steps (0 <= k <= floor(n/2)).

1, 1, 2, 1, 3, 3, 5, 9, 2, 8, 22, 10, 13, 51, 40, 5, 21, 111, 130, 35, 34, 233, 380, 175, 14, 55, 474, 1022, 700, 126, 89, 942, 2590, 2450, 756, 42, 144, 1836, 6260, 7770, 3570, 462, 233, 3522, 14570, 22890, 14490, 3234, 132, 377, 6666, 32870, 63600, 52668

Offset

0,3

Comments

Row n has 1+floor(n/2) terms. T(n,0) = A000045(n+1) (the Fibonacci numbers). T(2n,n) = binomial(2n,n)/(n+1) = A000108(n) (the Catalan numbers). Row sums yield A118720. Column k has g.f. = c(k)z^(2k)/(1-z-z^2)^(2k+1), where c(k) = binomial(2k,k)/(k+1) are the Catalan numbers; accordingly, T(n,1) = A001628(n-2), T(n,2) = 2*A001873(n-4), T(n,3) = 5*A001875(n-6). Sum_{k>=0} k*T(n,k) = A106050(n+1).

Links

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

Formula

G.f.: G = G(t,z) satisfies G = 1 + zG + z^2*G + tz^2*G^2 (see explicit expression at the Maple program).

Example

Triangle starts:
   1;
   1;
   2,  1;
   3,  3;
   5,  9,  2;
   8, 22, 10;
  13, 51, 40,  5;
T(3,1)=3 because we have hUD, UhD and UDh.

Maple

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

Crossrefs

Cf. A000045, A118720, A106050, A000108.

Sequence in context: A340623 A059876 A095354 * A132888 A213934 A124774

Adjacent sequences: A132880 A132881 A132882 * A132884 A132885 A132886

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 03 2007

Status

approved