Wednesday, 16 January 2008

co.combinatorics - Combinatorics of lattice walks with forbidden points

First, let me confirm your formula for walks $(0,0) xrightarrow{m}(x,y)$ with $x+yequiv m ~mod 2$, $p_m(x,y)$, which you stated for $m=2n$.



Choose $(m+x+y)/2$ out of $m$ steps $s_i$ to be $(+1/2,+1/2)$ versus $(-1/2,-1/2)$.



Choose $(m+x-y)/2$ out of $m$ steps $t_i$ to be $(+1/2,-1/2)$ versus $(-1/2,+1/2)$.



Then letting $w_i = s_i + t_i$, $(w_i)$ are the steps of a walk $(0,0) xrightarrow{m}(x,y)$ with steps of $(pm 1,0)$ or $(0,pm 1)$.




Second, let me fill in some details for the generating function approach.



Any walk $(0,0) xrightarrow m (x,y)$ either avoids $(x_f,y_f)$, or it can be broken into $3$ pieces:



$(0,0) xrightarrow t (x_f,y_f)$ which first visits $(x_f,y_f)$ at the end,



$(x_f,y_f) xrightarrow {2u} (x_f,y_f)$ of size ${2u choose u}^2$.



$(x_f,y_f) xrightarrow {m-t-2u} (x,y)$ which last visits $(x_f,y_f)$ at the start.



The first and third pieces have the same form reversed in time. Let $q_n(a,b)$ be the number of paths $(0,0)xrightarrow n (a,b)$ which only visit (a,b) at the end.



$$sum_n p_n(a,b)x^n = bigg(sum_n q_n(a,b)x^nbigg)bigg(sum_n sideset{}{^{^{^2}}}{2n choose n} x^{2n}bigg)$$



$$sum_n q_n(a,b)x^n = sum_{n} p_n(a,b)x^n bigg/sum_n sideset{}{^{^{^2}}}{2n choose n} x^{2n}$$



So, a generating function for walks $(0,0) to (x,y)$ which visit $(x_f,y_f)$ is



$$bigg(sum_n q_n(x_f,y_f)x^nbigg)bigg( sum_nq_n(x-x_f,y-y_f)x^nbigg)bigg(sum_n sideset{}{^{^{^2}}}{2n choose n} x^{2n}bigg)$$



$$=bigg(sum_n p_n(x_f,y_f)x^nbigg)bigg( sum_nq_n(x-x_f,y-y_f)x^nbigg)$$



$$=bigg(sum_n p_n(x_f,y_f)x^nbigg)bigg( sum_np_n(x-x_f,y-y_f)x^nbigg)bigg/sum_n sideset{}{^{^{^2}}}{2n choose n} x^{2n}$$



You want to subtract this from $sum_n p_n(x,y)x^n$.



I don't see a closed form expression for the coefficients.

No comments:

Post a Comment