Esther and Daniel are playing a video game called Latticeville. Each level in Latticeville consists of a grid of $m \times n$ rooms, and the two players start in the southwest-most room. From each room in the level, the players are only permitted to move north or east. The level ends when both players reach the room furthest northeast. Esther and Daniel want to maximize the amount of the game that they explore collectively, so they want to ensure that — as much as possible — they never visit the same rooms as each other. But there seem to be many different ways to accomplish this. Given the size of a level in Latticeville, determine how many different subsets of rooms Esther and Daniel can visit such that the number of rooms visited is maximal. For $m = 3$ and $n = 4$ the output should be $6$.
What's the formula for this? I searched a lot but I could not find a good answer. Hope to get a good answer here.
We can compute this with an application of Lindström-Gessel-Viennot's lemma.
Let $a_1, a_2$ be two sources and $b_1, b_2$ be two sinks. Note that each path has a distinct source and a distinct sink, roughly illustrated here:
This is because the top path must always start with an UP and end with a RIGHT move, and the bottom path always starts with a RIGHT ends with an UP move.
Now that we have an acyclic graph, two distinct sinks and two distinct sources we can apply Lindström-Gessel-Viennot's lemma. Let $p(m, n)$ be the total number of lattice paths going up and right on an $m$ by $n$ grid. We let all weights be equal to $1$, so we find:
\begin{align*} e(a_1, b_1) &= p(m-1, n-1)\\ e(a_1, b_2) &= p(m-2, n)\\ e(a_2, b_1) &= p(m, n-2)\\ e(a_2, b_2) &= p(m-1, n-1)\\ \end{align*}
Because no path is permutable and we took all weights to be $1$, we find that the total number of these non-intersecting paths is:
$$ p(m-1, n-1)^2 - p(m-2, n)p(m, n-2)$$
Now it's a well-known formula that $p(m, n) = \binom{m + n - 2}{m - 1} = \binom{m + n - 2}{n - 1}$, which we can expand and simplify:
$$\binom{m + n - 4}{m-2}^2 - \binom{m + n - 4}{m-1}\binom{m + n - 4}{n - 1}$$
After some more research, these are closely related to the Narayana numbers.