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

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 $\frac{1}{n+1} {2n\choose n}$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_{1},P_{2})$ where each $P_{i}$ is a shortest lattice path from $(0,0)$ to $(n,n)$ such that $P_{1}$ never goes above $P_{2}\ ?$ Here, "$P_{1}$ never goes above $P_{2}$" means that $P_{1}$ lies inside or on the boundary of the region determined by $P_{2}$, the $x$-axis, and the line $x=n$.

share|improve this question

5 Answers 5

up vote 14 down vote accepted

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.

share|improve this answer
    
Thank you very much. The Gessel-Viennot method seems to be very powerful. –  Philipp Lampe Oct 21 '09 at 16:33
1  
This formula says that the expected number of paths that stay below a random path from (0,0) to (n,n) is C_n * (2n+1)/(n+1), or about 2 C_n, where C_n is the nth Catalan number. Is there a natural explanation for this 2? –  Kevin P. Costello Oct 22 '09 at 3:32
    
More generally, there are (n+m)!(n+m+1)! / n!(n+1)!m!(m+1)! pairs of noncrossing paths from (0,0) to (n,m). –  Philipp Lampe Oct 23 '09 at 13:51
    
The formula also says that the number of bad pairs of paths from (0,0) to (n,n) is equal to (2n choose n+1)^2. Maybe there is a bijective proof similar to André's reflection proof for Catalan numbers. –  Philipp Lampe Oct 23 '09 at 14:40

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.

share|improve this answer
    
I agree with mattiast. You are not counting all the pairs. I doubt that the answer is a polynomial in n. –  Philipp Lampe Oct 21 '09 at 12:36
    
Right. My bad. –  Anna Varvak Oct 21 '09 at 14:16

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.

share|improve this answer
    
Very good. But can you simplify your determinant? Is there a simple explicit formula - maybe in terms of binomial coefficients? –  Philipp Lampe Oct 21 '09 at 12:39
    
See David Speyer's answer, who was actually worked through the details! –  Robert Parviainen Oct 21 '09 at 13:43

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?

share|improve this answer
    
This is very good. It should simplify to David Speyer's formula above. –  Philipp Lampe Oct 22 '09 at 15:59

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.

share|improve this answer
    
That's very helpful and very general! –  Philipp Lampe Oct 23 '09 at 21:30

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.