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