Latticeville game!

Hi. Why is not 20C18 correct?

My go at this problem was to find how many squares each player must have each. For the problem 5x8 grid it is 10 each + 2 together (start & goal). Each player must atleast have the squares at the edge in their domain (the first picture where the arrows follow the edge, they have some squares the other arrow cannot enter). since you cannot enter another players edge squares (which are the 10 distinct square each player at least must have) we can find out how many squares they can share. This is 5x8 -2x10 -2 = 18.

Now we have 3 possibilities, and following the pidgenhole example, the squares can be placed in these 3 "pidgeholes". 1 is in the middle of the arrows, 2 is above the top arrow and 3 is beneath the arrow at the bottom. We follow the pidgenhole example and get: (18+3-1)C18 <=> 20C18 = 190.

Why is this not correct?

Wow! Very impressive. How did you come up with this?

The result is correct, but severely lacking is interpretation and checking that your inputs match the conditions of the Lemma.

Setting $\cal{G}$ to be the weighted, directed graph whose vertices are the squares (bar the bottom left and top right corners), whose edges are all of the form $k=(u,v)$ and of weight $w(k):=1\in\mathbb{Z}$ where $v$ is an adjacent square above or to the right of $u$ , we have as you mentioned to the sources $a_{1},a_{2}$ and two sinks $b_{1},b_{2}$ . As you state, each path from $u$ to $v$ , denoted $P:u\rightarrow v$ , necessarily has weight $w(P):=\prod_{i<|P|}\omega(k_{i})=1$ where $k_{0},k_{1},\ldots$ are the edges in the path. Thus the $e$ -term in the Lemma has the value

$e(u,v):=\sum_{P:u\rightarrow v}\omega(P)=|\{P\mid P~\text{a path from}~u~\text{to}~ v\}|.$

Now we consider twisted path-tuples : $\vec{P}=(P_{1},P_{2})$ where $P_{1}:a_{1}\rightarrow b_{\sigma(1)}$ and $P_{2}:a_{2}\rightarrow b_{\sigma(2)}$ are ‘paths’ in the graph from $a_{1}$ to $b_{\sigma(1)}$ resp. from $a_{2}$ to $b_{\sigma(2)}$ , whereby $\sigma=\sigma(\vec{P})$ is a permutation on $\{1,2\}$ (there are only two). Our goal is actually, to just compute the number of twisted paths $\vec{P}$ whose components share no nodes in common, and for which $\sigma(\vec{P})=1$ the identity permutation. Call such twisted path-tuples non-entangled . Note that the number of non-entangled twisted path-tuples $\vec{P}$ with permutation $\sigma(\vec{P})\neq 1$ is 0, since in the 2-dimensional grid, a path going from $a_{1}$ to $b_{2}$ will necessary cross at some point any path going from $a_{2}$ to $b_{1}$ (this is easy to prove, but should nonetheless be proved in a more thorough treatment). We thus obtain the following expression, relevant to the Lemma:

$\begin{array}{c}[mc]{rcl} \sum_{\vec{P}~\text{non-entangled}}\mathrm{sgn}(\sigma(\vec{P}))\cdot\prod_{i}w(P_{i}) &= &\underbrace{ \sum_{\vec{P}~\text{non-entangled,}~\sigma(\vec{P})=(1 2)}-1\cdot\prod_{i}1 }_{=0,~\text{as no such paths exist}} +\sum_{\vec{P}~\text{non-entangled,}~\sigma(\vec{P})=1}1\cdot\prod_{i}1\\ &= &0+\sum_{\vec{P}~\text{non-entangled,}~\sigma(\vec{P})=1}1\cdot 1\\ &= &\underbrace{|\{\vec{P}\mid\text{non-entangled twisted path-tuples from}~(a_{1},a_{2})~\mathrm{to}~(b_{1},b_{2})\}|}_{\mathrm{lattPaths}(m,n)}\\ \end{array}$

Now the Lindström–Gessel–Viennot lemma says,

$\sum_{\vec{P}~\text{non-entangled}}\mathrm{sgn}(\sigma(\vec{P}))\cdot\prod_{i}w(P_{i})=\det(w(\cal{G}))$

where

$w(\cal{G})=\left(\begin{array}{c}[mc]{cc} e(a_{1},b_{1}) &e(a_{1},b_{2})\\ e(a_{2},b_{1}) &e(a_{2},b_{2})\\ \end{array}\right) =\left(\begin{array}{c}[mc]{cc} p(m-1,n-1) &p(m,n-2)\\ p(m-2,n) &p(m-1,n-1)\\ \end{array}\right).$

Putting all of this together, one has

$\mathrm{lattPaths}(m,n) =\sum_{\vec{P}~\text{non-entangled}}\mathrm{sgn}(\sigma(\vec{P}))\cdot\prod_{i}w(P_{i}) =\det(w(\cal{G})) =p(m-1,n-1)^{2}-p(m,n-2)\cdot p(m-2,n)$

It remains to determine the expressions $p(\cdot,\cdot)$ . Since $p(m,n)$ is the number of paths traversing a 2d grid from $(1,1)$ units to $(m,n)$ using only moves of the form $(1,0)$ and $(0,1)$ , it is a simple matter of computing the combinatorial number of ways of arranging right-moves and up-moves, which yields the expression $p(m,n)=\tbinom{m-1+n-1}{m-1}$ .