How many double paths in a grid?

Question

I have a combinatorics problem motivated, of all things, by category theory.

Consider a two-dimensional grid of vertices and edges. Fix two points, $P$ and $Q$, such that $Q$ is $a$ steps right and $b$ steps down from $P$. I'm interested in counting pairs of shortest paths from $P$ to $Q$. That is two paths from $P$ to $Q$ that only go down and right, never up and left. They are also never allowed to touch, either on an edge or a vertex, so one is always down-left and the other up-right.

If $a=1$ or $b=1$ there is just one pair of paths that work, forming a rectangle. If $a=2$ and $b=2$ I count 3 pairs - one forming a square and two forming Ls. How many pairs are there in general?

(This calculation helps count the number of indecomposable objects in a certain abelian category.)

Answer 1

This number of such pairs will be $$\frac{(a+b-1)!(a+b-2)!}{a!b!(a-1)!(b-1)!}.$$ This follows from the Lindstrom-Gessel-Viennot lemma and the fact that the number of directed paths in an $m\times n$ rectangle is $\binom{n+m}{m}$.

Answer 2

It is more convenient to deal with paths going up and right rather than down and right. Remove the first and last step from each path, and move the bottom path one unit up and one unit left. We now have two paths in an $(a-1)\times(b-1)$ rectangle $R$ that don't cross each other, though they may touch. Put the number 2 in each square of $R$ above the top path, the number 1 in each square between the two paths, and the number 0 in each square below the bottom path. This gives a plane partition fitting in an $(a-1)\times (b-1)$ rectangle with largest part at most 2. The enumeration of plane partitions fitting in an $r\times s$ rectangle with largest part at most $m$ is due to MacMahon. (His famous generating function also keeps track of the sum of the parts.) One reference is Theorem 7.21.7 of Enumerative Combinatorics, vol. 2 (set $q=1$).