Lattice Path Combinatorics: Given point find paths that pass through and avoid

combinatoricsdiscrete mathematics

I am given a lattice where one must start at (4, 4) and end at (15, 15). I have tried various measures to try solving this for the number of shortest paths where

a) you must avoid the point (10,8) and

b) pass through the point (10,8).

I'm aware that there is 1365 paths from (4, 4) to (15, 15). I have tried the approach where I try to generate all the paths that go through (10,8) from (4, 4) and then go from (10,8) to (15, 15) but I can't seem to find the answer or perhaps my approach in understanding the given point $(A, B)$ the number of shortest lattice paths to $(X,Y)$ is
$$\frac{(A-X)!\cdot (B-Y)!}{(A-X)! + (B-Y)!}$$

Best Answer

Recall that the number of (North-East) lattice paths from $(c,d)$ to $(a,b)$ with $0\leq c\leq a$ and $0\leq d\leq b$ is equal to $$\binom{a-c+b-d}{a-c}=\binom{a-c+b-d}{b-d}=\frac{(a-c+b-d)!}{(a-c)!\cdot(b-d)!}.$$

Therefore we have that:

  • from $(4,4)$ to $(15,15)$ there are $\binom{11+11}{11}=705432$ paths,

  • from $(4,4)$ to $(10,8)$ there are $\binom{6+4}{4}=210$ paths,

  • from $(10,8)$ to $(15,15)$ there are $\binom{5+7}{5}=792$ paths.

Hence, the answer for b) is $210\cdot 792=166320$ whereas the answer for a) is the complement $705432-166320=539112$.