Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
1  
Do you have the condition that paths go up and to the right? –  01000100 Mar 6 '12 at 14:24

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

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.