Pairs of shortest paths - MathOverflow

Pairs of shortest paths

2009-10-21T08:33:54Z

It is known that the binomial coefficient (2n choose n) is equal to number of shortest lattice paths from (0,0) to (n,n). The Catalan number (2n choose n)/(n+1) is equal to the number of shortest lattice paths that never go above the diagonal. Here, the diagonal may be viewed as a path from (0,0) to (n,n).

Is there a formula for the number of pairs (P₁,P₂) where each P_i is a shortest lattice path from (0,0) to (n,n) such that P₁ never goes above P₂? Here, "P₁ never goes above P₂" means that P₁ lies inside or on the boundary of the region determined by P₂, the x-axis, and the line x=n.

Answer by Anna Varvak for Pairs of shortest paths

2009-10-21T10:32:22Z

The number of such pairs is (n^2+1)(n^2+2)/2.

Rationale:

Let me rephrase the pairs (P1,P2) as follows: take the Ferrers diagram outlined by P1, x-axis, and the line x=n; the question is about the number of sub-diagrams, including the null diagram outlined by the path P2 that runs along the x-axis and then the line x=n.

To count the number of pairs (P1,P2), let's add one square at a time to the Ferrers diagram (filling columns before rows, for example), and count how many sub-diagrams it has (outlined by P2). Through this process, we count the null diagram n^2+1 times, the diagram with a single square n^2 times, the diagram with two squares n^2-1 times, ..., the diagram with all n^2 squares exactly once.

Thus the number of these pairs is \sum_{k=1}^{n^2+1}k = (n^2+1)(n^2+2)/2.

Answer by Robert Parviainen for Pairs of shortest paths

2009-10-21T10:40:29Z

You should also look up the (Lindström-) Gessel-Viennot theorem for non-intersecting paths, which counts, surprise, sets of non-intersecting lattice paths, and expresses them as a determinant.

Answer by David Speyer for Pairs of shortest paths

2009-10-21T13:32:32Z

The answer is (2n)! (2n+1)! / (n)!^2 (n+1)!^2 .

You can get this by the Gessel-Viennot method suggested above. One difficulty is that GV wants to count paths which don't touch at all, even at vertices, while you just want to count paths that don't cross. To solve this, take your lower path and slide it south-east. You are now looking for two paths, one from (0,0) to (n,n) and one from (-1,1) to (n-1,n+1), that don't touch at all.

The GV method gives the determinant

(2n choose n) (2n choose n+1)

(2n choose n-1) (2n choose n)

Expanding this and simplifying gives the above, if I didn't make any mistakes.

Answer by Marco-Dick CHEUNG for Pairs of shortest paths

2009-10-21T13:34:41Z

Below is an idea to express the answer in terms of sum of Catalan numbers.

Construct a size-(2n) sequence for P1 such that the i-th term is 1 if P1 is moving upward at the i-th step, and 0 otherwise. Similarly for P2. For example, when n=4, and P1 is RRURUURU, the sequence is (0,0,1,0,1,1,0,1); if P2 is UUURRURR, the sequence is (1,1,1,0,0,1,0,0).

The consider the sequence of P2 minus the sequence of P1. For example, in the last paragraph, we get (1,1,1,0,0,1,0,0) - (0,0,1,0,1,1,0,1) = (1,1,0,0,-1,0,0,-1).

The difference sequence has some properties:

1) Each term is either 1, 0 or -1.

2) The partial sum is never negative.

Hence, we can obtain the number answer by

a) choosing a Catalan sequence of size k (where n>=k>=0)

b) in the difference sequence choose 2k coordinates for the Catalan sequence

c) in the other coodinates, put zero's

d) the k one's must correspond to k up's in the sequence of P2. However, there are some other (n-k) ups of P2, which is "hidden" at the zero's of the difference sequence (like the third coordinate in the example I mention above). So we need to choose (n-k) zero's corresponding to the up's in the sequence of P2

This give the answer

$sum_{k=0}^n C(2n,2k) C_k C(2n-2k,n-k) = \sum_{k=0}^n (2n)! / (2k)! / ((n-k)!)^2 * C_k,$

where $C_k$ is the k-th Catalan number, and $C(a,b)$ is "a chooses b".

The sum may be simplified using exponential generating function, but I am uncertain at this moment. Any comment?

Answer by Ricky Liu for Pairs of shortest paths

2009-10-23T17:42:58Z

If you ask the analogous question about p noncrossing paths in an m x n rectangle, you are essentially counting plane partitions (if you write in each box the number of paths it is above, then all rows and columns are weakly decreasing). There is then a beautiful formula by MacMahon for the number of these: it is the product of (i+j+k-1)/(i+j+k-2) over all 1<=i<=m, 1<=j<=n, 1<=k<=p.