Vladimir Nikolin

1. Definition

Lattice path is a path composed of connected horizontal and vertical line segments, which are restricted to east and north steps. A path represents a subset of m elements in a set of m+n elements, so the number of paths p(O,M) , of length m+n, from the origin (0,0) to a point M(m,n) is given by the binomial coefficient

p(O,M) = C(m+n,m)={m+n \choose m}
where C(n,k) is the number of k-combinations from a given set of n elements.

Example (see the picture):

Total number of paths from point O(0,0) to point B(7,5) is

p(O,B)= {7+5 \choose 7} = {12 \choose 7} = 792

Let M={x \in N|x \leq 12} is an "ordered" set with 12 elements, N is its subset with 7 elements, generated by path on the picture. Every path has a unique code. A horizontal line gives 1 and vertical line gives 0, we get an characteristic function (array):

p = { {1,2,3,4,5,6,7,8,9,0,11,12} \choose {1,0,1,0,0,1,1,0,1,0,1,1}}

or p(1) = p(3) = p(6) = p(7) = p(9) = p(11) = p(12)= 1. Subset N, generated by the characteristic function p is N={1,3,6,7,9,11,12}.

In conclusion: In a mxn rectangle, there is m+n \choose m different paths, and length of these paths is m+n.

2. Multiplication Principle

Let B is a dot on the lattice between points O and A. Let \wp (B) denote the set of all paths passing through the point B. Let p(O,B) denote the number of paths from O to B, p(B,A) the number of paths from B to A. Total number of paths from O to A via B is:

 
|\wp (B)| = p(O,B) \cdot p(B,A)

3. Disjoint paths - trap points

Given is a point A(m,n) and number k \leq m+n . Let A0(k,0), A1(k-1,1) ...Ai(k-i,i)... An(k-n,n) are points on the grid which belong to line x + y = k . Let's call it trap points. Let \wp (A_i) is a set of paths from O to A(m,n) passing through the point Ai.

THEOREM: Every path from O to A, passing through one and only one of trap points. Total number of paths from O to A is equal to sum of paths from each of trap points.

Proof: Distance between point O and trap points is exactly k and there are no other points with this feature in rectangle determined by points O and A. After k steps, the path is in exactly one trap point. Let notice that length of path is k \leq m+n. The second sentence is direct consequence of the first.

4. Vandermonde's Convolution Formula

Vandermonde's Convolution Formula is usually presented as:

{n+m \choose k} = \sum_{j=0}^{k}{m \choose j}{n \choose k-j}

In a rectangle, where is the length of paths m+n and width is k, trap points are given by formula x+y=m, so the distance between trap points and origin point O(0,0) is m. Also, the distance between trap points and point A(k,m+n-k) is n. Total number of paths is

p(O,A)= {m+n \choose k}
.

On the other hand, let Aj(j,m-j) is a trap point. From definition, we get:

p(O,A_j) = {m \choose j} \; , \; p(A_j,A) = {n \choose {k-j}}
Since the paths above and below the point Aj are independent, by multiplication principle:

p(O - A_j - A)= p(O,A_j) \cdot p(A_j,A)

Finally, by disjoint paths theorem, the total number of paths is a sum of paths from each of trap points, from A0 to Ak:

p(O,A) = \sum_{j=0}^{k}{m \choose j}{n \choose k-j}

Note: More about this formula, you can see in a separate page.

5.Recursive formula and Fibonacci numbers

Here is the famous recursive formula for binomial coefficients.For 1 \leq m,n:

{m+n \choose n}={m+n-1 \choose n}+{m+n-1 \choose n-1}

Proof is very simple: Let A(m,n) and A0(m,n-1), A1(m-1,n). All paths from origin to A, must pass through A0 or through A1:

{m+n \choose n} = p(O,A) = p(O-A_0-A) + p(O-A_1-A) =
=1 \cdot p(O,A_0)+1 \cdot p(O,A_1)={m+n-1 \choose n}+{m+n-1 \choose n-1}

We now can say: if a point B is left from a point A, total number of paths from origin to the point below point A is p(O,A)-p(O,B) .

Here is a proof without words that sum:

f(n)=\sum_{k=0}^{}{n-k \choose k}

is a variant of Fibonacci sequence:

f(1)=1 \; , \;f(2)=2 \; , \; f(n)=f(n-1)+f(n-2)

More precisely, f(n)=F n+1 , where Fn is the nth Fibonacci number.

Note: Similar approach you can find here. About patterns in Pascal's triangle, see here.

6.Turn points

Definition: East-North or 'EN' turn point ('10' or 'right up' or \to \uparrow ) is a lattice point on the path, which a rightward move is followed by an upward move. North-East or 'NE' turn point are defined analogously

THEOREM: Number of paths from origin O(0,0) to A(m,n) with k 'EN' turn points is:

{m \choose k} {n \choose k}

Proof: First of all, we must have condition that 'EN' turn points be placed in increasing order, i.e. if P(x1,y1) and Q(x2,y2) are two 'EN' turn points in that order, on the path from O(0,0) to A(m,n), then

1 \le x_1 < x_2 \le m \; , \; 0 \le y_1 < y_2 \le n-1

We can place 'EN' points at any point (x,y)\; x \in \{1,2 \cdots m \} \; ,\; y \in \{0,1 \cdots n-1 \}.

Purple area denotes points at which we can place 'EN' turns. Obviously, other points are unavailable. If we can place k turns, we choose k \; x coordinates 1 \le x_1 < x_2 \cdots < x_k \le m and k \; y coordinates 0 \le y_1 < y_2 \cdots < y_k \le n-1 . Coordinates will be (x_1,y_1), \; (x_1,y_1), \; \cdots (x_1,y_1) . Therefore, there are {m \choose k} {n \choose k} total paths with k turning points.

For example if, in (6,9) rectangle, we choose (1,4,5) for x coordinates and (0,2,6) for y coordinates, we would place turn points at (1, 0), (4, 2) and (5, 6) as in figure above.

Summing all paths with k=0 \cdots n turn points, we get a variant of Vandermonde's convolution:

{m+n \choose n}=\sum_{k=0}^{n}{m \choose k}{n \choose k}

For further reading: C. Krattenthaler "The Enumeration of Lattice Paths With Respect to Their Number of Turns"

7.Runs

Definition: Maximal subsequence of moves of the same kind is called a run. For example, the sequence \uparrow\uparrow\uparrow\to\uparrow\uparrow\to\to\to\uparrow has five runs of length 3, 1, 2, 3, 1, respectively. The path on the picture above, from O(0,0) to A(6,9), has seven runs of length 1, 2, 3, 4, 1, 3, 1. Binary sequence 00000001111 has two runs of length 7 and 4 (seven zeros and four ones in a row).

THEOREM: The number of lattice paths from O(0,0) to A(m,n), having i runs ('NE' or 'EN') is:

R_i=\cases { 2{m-1 \choose k-1}{n-1 \choose k-1},&\text{i=2k}\cr {m-1 \choose k}{n-1 \choose k-1}+{m-1 \choose k-1}{n-1 \choose k}, &\text{i=2k+1}}


Proof: 1) If the number of runs i, is even or i=2k, then we have exactly k 'EN' turn points. Let the first move is \to , hence the last move is \uparrow . It means that the last 'EN' turn point has x-coordinate m ( x_k=m ) and the first 'EN' turn point has y-coordinate 0( y_1=0 ). Since we choose k-1 x-coordinates, x_1...x_{k-1} , from the set \{1,2...m-1\} and k-1 y-coordinates, y_2...y_k , from the set \{1,2...n-1\} , we get {m-1 \choose k-1}{n-1 \choose k-1} such paths. Analogously for paths that start with the move \uparrow , but now we have k 'NE' points. Total number is equal.

2) If the number of runs i, is odd or i=2k+1, then we have again, k 'EN' turn points. Let the first move is \to , therefore the last move is also \to . Now we choose k x-coordinates, between 1 and m-1, and k-1 y-coordinates (the first 'EN' turn point has y-coordinate zero) between 1 and n-1, so the number of such paths is {m-1 \choose k}{n-1 \choose k-1} . In the case of paths which begins and ends with a \uparrow move, we have k 'NE' turn points and the number of such paths is {m-1 \choose k-1}{n-1 \choose k} .

Example 1: The number of paths from O(0,0) to A(4,3) for given number of runs is in the table bellow:

runs 2 3 4 5 6 7
paths 1+1 2+3 6+6 3+6 3+3 1


Example 2: (Sloane's A152659) is the number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) and having k runs (NE or EN) (1<=k<=2n-1).

This theorem has many applications in the theory of runs. A different approach, but the same result, you can find in this article.