Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 –  Gerhard Paseman Feb 9 '12 at 5:16

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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 –  Gerhard Paseman Feb 9 '12 at 16:54
    
Oops! I am used to paths that go up and right. I have fixed this. –  Richard Stanley Feb 9 '12 at 18:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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