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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
Do you have the condition that paths go up and to the right? – anthus Mar 6 '12 at 14:24
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)$


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|cite|improve this answer

Your Answer


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.