OFFSET
0,2
FORMULA
Define u(x, y, t) by: u(0, 0, t) = 2^t, u(x, y, 0) = 0 if (x, y) <> 0, otherwise u(x, y, t) = u(x+1, y, t-1) + u(x-1, y, t-1) + u(x, y+1, t-1) + u(x, y-1, t-1). Then a(p) = u(1, 0, 2*p+1).
EXAMPLE
a(0)=1 because there is only one path of length 1 which passes though the origin.
a(1)=21 because there are 21 paths of length 3 which pass through the origin, namely:
if the first step leads to (0,0) there are now 16 possibilities;
if the first step leads to (1,1) there are 2 possibilities;
if the first step leads to (1,-1) there are 2 possibilities;
if the first step leads to (2,0) there is only one possibility.
MAPLE
f:=proc(M, z) n:=nops(M); p:=(n+3)/2; A:=[seq(0, i=1..(n+2))]; B:=[seq(A, i=1..(n+2))]; for i from 1 to n do for j from 1 to n do B:=subsop(i+1=subsop(j= B[i+1][j] + M[i][j], B[i+1]), B); B:=subsop(i+1=subsop(j+2= B[i+1][j+2] + M[i][j], B[i+1]), B); B:=subsop(i=subsop(j+1= B[i][j+1] + M[i][j], B[i]), B); B:=subsop(i+2=subsop(j+1= B[i+2][j+1] + M[i][j], B[i+2]), B); od; od; B:=subsop(p=subsop(p= 4*z, B[p]), B); (B, 4*z) end: g:=proc(n, M, z) option remember; if n = 0 then (M, z) else f(g(n-1, M, z)) fi; end; a:=proc(n) C:=g(2*n+1, [[1]], 1); C[1][2*n+2][2*n+1]; end;
CROSSREFS
KEYWORD
nonn
AUTHOR
Nussbaumer Jonathan (jonathan.nussbaumer(AT)wanadoo.fr), Jun 22 2005
STATUS
approved