A104855 Triangle read by rows: T(n,k) (0 <= k <= n) is the number of three-dimensional lattice walks consisting of n unit steps, each in one of the six coordinate directions, starting at the origin, never going below the horizontal plane and having k vertical steps.

1, 4, 1, 16, 8, 2, 64, 48, 24, 3, 256, 256, 192, 48, 6, 1024, 1280, 1280, 480, 120, 10, 4096, 6144, 7680, 3840, 1440, 240, 20, 16384, 28672, 43008, 26880, 13440, 3360, 560, 35, 65536, 131072, 229376, 172032, 107520, 35840, 8960, 1120, 70, 262144, 589824

Offset

0,2

Links

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

J. Brawner, Three-Dimensional Lattice Walks in the Upper Half-Space: Problem 10795, Amer. Math. Monthly, 108 (Dec. 2001), 980.

Formula

T(n, k) = binomial(n, k)*binomial(k, ceiling(k/2))*4^(n-k).

Example

T(2,1)=8 because we have NU, SU, EU, WU, UN, US, UE and UW, where N=(0,1,0),S=(0,-1,0), E=(1,0,0),W=(-1,0,0), U=(0,0,1) and S=(0,0,-1).
Triangle begins:
   1;
   4,  1;
  16,  8,  2;
  64, 48, 24,  3;

Maple

T:=(n, k)->binomial(n, k)*binomial(k, ceil(k/2))*4^(n-k): for n from 0 to 9 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Crossrefs

Row sums yield A005573. T(n,n) = A001405(n), T(n,0) = A000302(n) (powers of 4).

Cf. A005573, A001405, A000302.

Sequence in context: A188481 A138681 A038231 * A351419 A303054 A143496

Adjacent sequences: A104852 A104853 A104854 * A104856 A104857 A104858

Keyword

nonn,tabl

Author

Emeric Deutsch, Apr 23 2005

Status

approved