|
| |
|
|
A108740
|
|
On the Z^2 lattice, number of paths of length 2*p+1 that start at (1,0) and pass through the origin.
|
|
0
|
|
|
|
1, 21, 380, 6549, 110300, 1833692, 30235088, 495760277, 8096423740, 131830443644, 2141590812880, 34726805457372, 562280415840208, 9093156652690512, 146905159295338944, 2371308270156391317
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
LINKS
|
|
|
|
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
|
| |
|
|
