Pairs of shortest paths - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T06:56:48Z http://mathoverflow.net/feeds/question/1610 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1610/pairs-of-shortest-paths Pairs of shortest paths Philipp Lampe 2009-10-21T08:33:54Z 2009-10-23T17:42:58Z <p>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).</p> <p>Is there a formula for the number of pairs (P<sub>1</sub>,P<sub>2</sub>) where each P<sub>i</sub> is a shortest lattice path from (0,0) to (n,n) such that P<sub>1</sub> never goes above P<sub>2</sub>? Here, "P<sub>1</sub> never goes above P<sub>2</sub>" means that P<sub>1</sub> lies inside or on the boundary of the region determined by P<sub>2</sub>, the x-axis, and the line x=n.</p> http://mathoverflow.net/questions/1610/pairs-of-shortest-paths/1622#1622 Answer by Anna Varvak for Pairs of shortest paths Anna Varvak 2009-10-21T10:32:22Z 2009-10-21T10:32:22Z <p>The number of such pairs is (n^2+1)(n^2+2)/2.</p> <p>Rationale: </p> <p>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.</p> <p>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.</p> <p>Thus the number of these pairs is \sum_{k=1}^{n^2+1}k = (n^2+1)(n^2+2)/2.</p> http://mathoverflow.net/questions/1610/pairs-of-shortest-paths/1623#1623 Answer by Robert Parviainen for Pairs of shortest paths Robert Parviainen 2009-10-21T10:40:29Z 2009-10-21T10:40:29Z <p>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. </p> http://mathoverflow.net/questions/1610/pairs-of-shortest-paths/1650#1650 Answer by David Speyer for Pairs of shortest paths David Speyer 2009-10-21T13:32:32Z 2009-10-21T13:32:32Z <p>The answer is (2n)! (2n+1)! / (n)!^2 (n+1)!^2 .</p> <p>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.</p> <p>The GV method gives the determinant</p> <p>(2n choose n) (2n choose n+1)</p> <p>(2n choose n-1) (2n choose n)</p> <p>Expanding this and simplifying gives the above, if I didn't make any mistakes.</p> http://mathoverflow.net/questions/1610/pairs-of-shortest-paths/1651#1651 Answer by Marco-Dick CHEUNG for Pairs of shortest paths Marco-Dick CHEUNG 2009-10-21T13:34:41Z 2009-10-21T13:34:41Z <p>Below is an idea to express the answer in terms of sum of Catalan numbers.</p> <p>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).</p> <p>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).</p> <p>The difference sequence has some properties:</p> <p>1) Each term is either 1, 0 or -1.</p> <p>2) The partial sum is never negative.</p> <p>Hence, we can obtain the number answer by</p> <p>a) choosing a Catalan sequence of size k (where n>=k>=0)</p> <p>b) in the difference sequence choose 2k coordinates for the Catalan sequence</p> <p>c) in the other coodinates, put zero's</p> <p>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</p> <p>This give the answer</p> <p>$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,$</p> <p>where $C_k$ is the k-th Catalan number, and $C(a,b)$ is "a chooses b".</p> <p>The sum may be simplified using exponential generating function, but I am uncertain at this moment. Any comment?</p> http://mathoverflow.net/questions/1610/pairs-of-shortest-paths/2133#2133 Answer by Ricky Liu for Pairs of shortest paths Ricky Liu 2009-10-23T17:42:58Z 2009-10-23T17:42:58Z <p>If you ask the analogous question about p noncrossing paths in an m x n rectangle, you are essentially counting <em>plane partitions</em> (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&lt;=i&lt;=m, 1&lt;=j&lt;=n, 1&lt;=k&lt;=p.</p>