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



Pairs of shortest paths
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.


