3
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ You might set up a recurrence on a direction, say down. For b=2 I get a choose 2 (in my head, so don't be alarmed if you get something different), and for b+1 I get a different terms depending on when the upper path leaves the first row. If you generate some recurrences, I or someone else may be able to find a closed form for you. Gerhard "Ask Me About System Design" Paseman, 2012.02.08 $\endgroup$ Feb 9, 2012 at 5:16

2 Answers 2

8
$\begingroup$

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}$.

$\endgroup$
3
$\begingroup$

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$).

$\endgroup$
2
  • $\begingroup$ Do you mean "... and move the top path one unit left." ? Otherwise, I have trouble following the derivation. Gerhard "Ask Me About System Design" Paseman, 2012.02.09 $\endgroup$ Feb 9, 2012 at 16:54
  • $\begingroup$ Oops! I am used to paths that go up and right. I have fixed this. $\endgroup$ Feb 9, 2012 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.