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.

• Next diy biology - How can I create a microcapillary for manipulation of single cells?
• Previous soil - How Do Acid and Base Loving Plants Get Enough PO4?