A134426 Triangle read by rows: T(n,k) is the number of paths of length n in the first quadrant, starting at the origin, ending at height k and consisting of 2 kind of upsteps U=(1,1) (U1 and U2), 3 kind of flatsteps F=(1,0) (F1, F2 and F3) and 1 kind of downsteps D=(1,-1).

1, 3, 2, 11, 12, 4, 45, 62, 36, 8, 197, 312, 240, 96, 16, 903, 1570, 1440, 784, 240, 32, 4279, 7956, 8244, 5472, 2320, 576, 64, 20793, 40670, 46116, 35224, 18480, 6432, 1344, 128, 103049, 209712, 254912, 216384, 132320, 57600, 17024, 3072, 256

Offset

0,2

Comments

T(n,0) = A001003(n+1) (the little Schroeder numbers).

Row sums yield A134425.

Links

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

Formula

T(n,k) = ((k+1)*2^k/(n+1))*Sum_{j=0..n-k} binomial(n+1, j)*binomial(n+1, k+j+1)*2^j (0 <= k <= n).

G.f.: g/(1-2*t*z*g), where g = 1 + 3*z*g + 2*z^2*g^2 is the g.f. of the little Schroeder numbers 1, 3, 11, 45, 197, ... (A001003).

Example

T(2,1)=12 because we have 6 paths of shape FU and 6 paths of shape UF.
Triangle starts:
    1;
    3,   2;
   11,  12,   4;
   45,  62,  36,   8;
  197, 312, 240,  96,  16;

Maple

T:=proc(n, k) options operator, arrow: 2^k*(k+1)*(sum(2^j*binomial(n+1, j)*binomial(n+1, k+1+j), j=0..n-k))/(n+1) end proc: for n from 0 to 8 do seq(T(n, k), k=0..n) end do; # yields sequence in triangular form

Crossrefs

Cf. A001003, A134425.

Sequence in context: A258386 A159610 A074246 * A122672 A194608 A297870

Adjacent sequences: A134423 A134424 A134425 * A134427 A134428 A134429

Keyword

nonn,tabl

Author

Emeric Deutsch, Nov 05 2007

Status

approved