1
$\begingroup$

Let $P_1, P_2, Q_1$ and $Q_2$ be four points on a rectangle $ABCD$ such that $P_1$ is on $AB$, $P_2$ is on $BC$, $Q_1$ is on $CD$ and $Q_2$ is on $DA$.

I want to find the number of non-intersecting pairs of paths when each pair contains paths from $P_i$ to $Q_i$.

Example

It seems that I should apply the Gessel-Viennot method somehow, but I do not know how.

  • 1
    Do you have the condition that paths go up and to the right?2012-03-06

1 Answers 1

2

Consider the square lattice of height $m$ and width $n$.

If $P_1 = (0,i)$, $Q_1 = (j,m)$, $P_2 = (i',0)$ and $Q_2=(n,j')$

Then $Q_1 - P_1=(j,m-i)$ and $Q_2 - P_2=(n-i',j')$.

Similarly, $Q_2 - P_1 = (n,j'-i)$ and $Q_1 - P_2 = (j-i',m)$.

Assuming the path segments are in an east and north direction only,then the number of paths between $P_1$ and $Q_1$ is $\binom{m-i+j}{j}$ and the number of paths between $P_2$ and $Q_2$ is $\binom{n-i'+j'}{j'}$.

Likewise, the number of paths between $P_1$ and $Q_2$ is $\binom{n+j'-i}{n}$ and the number of paths between $P_2$ and $Q_1$ is $\binom{m+j-i'}{m}$.

The Lemma of Gessel and Viennot states that the number of non-intersecting paths $(P_1,P_2)\mapsto(Q_1,Q_2)$ is the determinant of the path matrix of the above system:

$ \binom{m-i+j}{j} \binom{n-i'+j'}{j'} - \binom{n+j'-i}{n} \binom{m+j-i'}{m} $

For example, in a $2\times3$ rectangle, with $P_1=(0,1),Q_1=(2,3),P_2=(2,0)$ and $Q_2=(3,1)$

rectangulater

There are $\binom{3}{2} \binom{2}{1} - \binom{3}{3} \binom{2}{2} = 6-1 = 5$ non-intersecting lattice paths whose path segments head in an easterly or northern direction only.