A151087 Number of walks within N^3 (the first octant of Z^3) starting at (0,0,0) and consisting of n steps taken from {(-1, -1, -1), (-1, 1, 1), (0, 0, 1), (1, 0, 0), (1, 0, 1)}.

1, 3, 11, 41, 165, 687, 2951, 12861, 56937, 255227, 1156995, 5287185, 24325901, 112587815, 523956543, 2449799269, 11500087377, 54174459251, 256027253243, 1213527789561, 5767023994869, 27470856080927, 131136432604919, 627242243728269, 3005666150390713, 14426914113698667, 69354696385966451

Offset

0,2

Links

Robert Israel, Table of n, a(n) for n = 0..234

A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008.

Formula

From Vaclav Kotesovec, May 01 2018: (Start)

Recurrence: (n+1)*(n+2)^2*(2048*n^4 - 16640*n^3 + 43280*n^2 - 34992*n - 2979)*a(n) = (n+1)*(20480*n^6 - 123392*n^5 + 103072*n^4 + 436304*n^3 - 547134*n^2 - 114375*n - 35748)*a(n-1) - (71680*n^7 - 578304*n^6 + 1432624*n^5 - 601872*n^4 - 2284697*n^3 + 3374358*n^2 - 1558113*n + 83412)*a(n-2) + 2*(61440*n^7 - 804352*n^6 + 4058592*n^5 - 9580432*n^4 + 8510358*n^3 + 5565239*n^2 - 15547821*n + 7808040)*a(n-3) + (n-3)*(411648*n^6 - 3619072*n^5 + 8794512*n^4 + 1785776*n^3 - 28370523*n^2 + 22689914*n + 2453460)*a(n-4) - 5*(n-4)*(n-3)*(618496*n^5 - 4658688*n^4 + 10072288*n^3 - 1656912*n^2 - 13667306*n + 8981007)*a(n-5) + 1275*(n-5)*(n-4)*(n-3)*(2048*n^4 - 8448*n^3 + 5648*n^2 + 9840*n - 9283)*a(n-6).

a(n) ~ 5^(n+1) / (Pi*sqrt(2)*n) * (1 + sqrt(5*Pi/(2*n))/4).

(End)

Maple

Steps:= [[-1, -1, -1], [-1, 1, 1], [0, 0, 1], [1, 0, 0], [1, 0, 1]]:
f:= proc(n, p) option remember; local s, r;
  if n <= min(p) then return 5^n fi;
  if min(p)>= 1 then add(procname(n-1, p+s), s=Steps)
  elif p[1]>= 1 then add(procname(n-1, p+s), s=Steps[2..5])
  else add(procname(n-1, p+s), s=Steps[3..5])
  fi
end proc:
map(f, [$0..30]); # Robert Israel, May 01 2018

Mathematica

aux[i_Integer, j_Integer, k_Integer, n_Integer] := Which[Min[i, j, k, n] < 0 || Max[i, j, k] > n, 0, n == 0, KroneckerDelta[i, j, k, n], True, aux[i, j, k, n] = aux[-1 + i, j, -1 + k, -1 + n] + aux[-1 + i, j, k, -1 + n] + aux[i, j, -1 + k, -1 + n] + aux[1 + i, -1 + j, -1 + k, -1 + n] + aux[1 + i, 1 + j, 1 + k, -1 + n]]; Table[Sum[aux[i, j, k, n], {i, 0, n}, {j, 0, n}, {k, 0, n}], {n, 0, 10}]

Crossrefs

Sequence in context: A339037 A027103 A151086 * A149066 A149067 A018962

Adjacent sequences: A151084 A151085 A151086 * A151088 A151089 A151090

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved