Lattice Paths

We shall make cases based on no. of (2,0) steps.

Generalization : If no. of (2,0) steps is x and no. of (1,-1) and (1,1) steps is y.

Then no. of lattice paths is $2^{y} * {{x+y} \choose x}$

Proof: total steps = x+y

No. of ways to place (2,0) step is ${{x+y} \choose x}$ .

Remaining y places to be filled with either (1,1) or (1,-1) step.

Each remaining place can be filled in 2 different ways.

So remaining y places can be filled in $2^{y}$ ways.

So total ways = $2^{y} * {{x+y} \choose x}$

Now We shall make cases based on no. of (2,0) steps.

1.No. of (2,0) steps=0 , no. of ways= $2^{8} * {{8} \choose 0}$

2.No. of (2,0) steps=1 , no. of ways= $2^{6} * {{7} \choose 1}$

3.No. of (2,0) steps=2 , no. of ways= $2^{4} * {{6} \choose 2}$

4.No. of (2,0) steps=3 , no. of ways= $2^{2} * {{5} \choose 3}$

5.No. of (2,0) steps=4 , no. of ways= $2^{0} * {{4} \choose 4}$

Ans = 985

To simplify the problem, we need to find the value of $f(0)$ , in which $f(n)$ denotes the number of different lattice paths available from a point in line $x=n$ to the line $x=8$ using the given steps.

We want to know how many lattice paths will stop exactly at the line $x=8$ . Since all the steps have positive x-values, any point $(x_i,y_i)$ with $x_i>8$ will never reach the line $x=8$ again. i.e,

For $(n>8)$ , $f(n)=0$

Any point in line $x=8$ is already located at the target x-coordinate. Therefore, there is only one possible lattice path for any point in the line $x=8$ , which is an empty set. Therefore,

For $(n=8)$ , $f(n)=1$

Lastly, using only the three different steps, we can conclude that in any point ( $x_i,y_i$ ) (in other words, a point located at line $x=x_i$ , you can either advance to a point located in line $x=x_i+1$ in two different ways, or to a point in line $x=x_i+2$ . Thus,

For $(n<8)$ , $f(n)=2\times f(n+1) + f(n+2)$

Using the functions above, we can obtain the value of $f(0)$ , namely 985.

Let $a_n$ be the number of ways to get to the line $x = n$ . For $n > 1$ , the last step of the path could be any one of the three steps. Consider all paths that end with the step $(1,1)$ . If we remove this step, we are left with paths to the line $x = n-1$ . By definition, there are $a_{n-1}$ such paths. Similarly, there are $a_{n-1}$ paths to $x = n$ that end with the step $(1,-1)$ and $a_{n-2}$ paths that end with $(2,0)$ . Thus, for $n > 1$ , we find the relation

$a_n = 2 a_{n-1} + a_{n-2}$ .

It is easy to check that $a_1 = 2$ and $a_2 = 5$ . By repeated use of the recurrence relation, we easily find $a_8 = 985$ .

Note that if such a path contains a given point $(x,y)$ , there are only 3 possible immediate predecessors to that point: $(x-1, y-1), (x-1, y+1), (x-2, y)$ . Let $S(x,y)$ represent the number of paths from $(0,0)$ to $(x,y)$ . Then $S(x,y) = S(x-1,y-1) + S(x-1,y+1) + S(x-2,y).$ Now let $P_n$ represent the number of paths from $(0,0)$ to $x = n$ . Then $\begin{aligned} P_n &= \sum_{y=-\infty}^\infty S(n,y) \\ &= \sum_{y=-\infty}^\infty S(n-1,y-1) + S(n-1,y+1) + S(n-2,y) \\ &= 2\sum_{y=-\infty}^\infty S(n-1,y) + \sum_{y=-\infty}^\infty S(n-2,y) \\ &= 2P_{n-1} + P_{n-2}, \end{aligned}$ with the initial conditions $P_0 = 1$ and $P_1 = 2$ (which we enumerate by inspection). We may then directly compute $P_2 = 5$ , $P_3 = 12$ , $P_4 = 29$ , $P_5 = 70$ , $P_6 = 169$ , $P_7 = 408$ , and $P_8 = \boxed{985}$ .

Note that $P_n$ are known as Pell numbers.

Since the path is strictly to the x-value of x=8, we don't even need to consider the y-value when creating a path. All we need to consider is that there are two distinct ways of moving to right 1 space and one distinct way of moving to the right 2 spaces.

Let $A$ be the number of times we move 1 space to the right in a path and $B$ be the number of times we move 2 spaces to the right in a path. As we can see, $A+2B=8$ for a valid path.

There are $2^A$ ways to make lattice paths strictly out of 1-space steps because there are 2 ways of moving to the right 1 space (as previously stated). By the multiplication rule for $A$ steps, we get $2^A$ .

There is only 1 way to make a path with just 2-space steps because there is only one 2-space point available to use. But, the number of distinct combinations of 2-space steps in a path is ${A+B \choose B}$ .

Thus, for each pair $(A,B)$ , there are $2^A{A+B \choose B}$ different paths. Since $A=8-2B$ and $0\le B\le 4$ to ensure $0\le A \le 8$ , we can find the total number of paths to be $\sum_{B=0}^4 2^{8-2B}{8-B \choose B}=256\sum_{B=0}^4 \frac{(8-B)!}{B!(8-2B)! 4^{B}}=985\text{ paths}$

To view this in a simpler way, consider this casework (1s symbolize 1-space steps and 2s symbolize 2-space steps):

11111111 - $2^8 {8 \choose 0} = 256$

1111112 - $2^6 {7 \choose 1} = 448$

111122 - $2^4 {6 \choose 2} = 240$

11222 - $2^2 {5 \choose 3} = 40$

2222 - $2^0 {4 \choose 4} = 1$

Summing $256+448+240+40+1=985$ .

Separate into paths with a given number of $(2,0)$ steps.

If there are no $(2,0)$ steps, then the path has length $8$ and there are two choices for each step, so there are $2^8$ such paths.

If there is one $(2,0)$ step, then the path has length $7$ . There are $2^6$ choices for the non-horizontal part of the path, and then $\binom71$ places to put the horizontal step, so there are $2^6 \binom71$ such paths.

If there are two $(2,0)$ steps, then the path has length $6$ . There are $2^4$ choices for the non-horizontal part of the path, and then $\binom62$ choices for the placing of the two horizontal steps, so there are $2^4 \binom62$ such paths.

Similar reasoning leads to $2^2 \binom53$ and $2^0 \binom44$ paths with $3$ and $4$ horizontal steps, respectively. So the sum is $2^8 + 2^6 \binom71 + 2^4 \binom62 + 2^2 \binom53 + 2^0 \binom44 = 985.$

The path could have:

• 4 steps of size (2,0)
• 3 steps of size (2,0) and 2 others (5 total)
• 2 steps of size (2,0) and 4 others (6 total)
• 1 step of size (2,0) and 6 others (7 total)
• 8 steps of size (1,1) or (1,-1)

There's 1 possibility for first case: (2,2) (2,2) (2,2) (2,2)

In the second case, we need to choose 3 of the 5 steps for the (2,2)'s then there are $2^2$ possibilities for the (1,-1) and (-1,1).
${5 \choose 3}*2^2 = 40$

Third case. We need to choose 2 of the 6 steps, then 2 possibilities for every of the 4 remaining steps: ${6 \choose 2}*2^4 = 240$

Fourth case: 7 possibilities for the (2,2) and 2 possibilities for each of the 6 remaining. $7 *2^6 = 448$

Last case: there are 8 steps to choose between (1,1) and (1,-1), i.e. $2^8 = 256$

1+40+240+448+256 = 985

Let $c_i$ be the number of paths from some point in line $x=i$ to the line $x=8$ using the steps given in the problem statement. We get the recursion:

$c_i = 2c_{i+1} + c_{i+2}$

with the initial conditions:

$c_8 = 1$ (there is exactly one path from a point on the line $x = 8$ to itself, the path with 0 steps.

$c_7 = 2$ (to go from a point on line $x=7$ to line $x=8$ we have to use one of the steps $(1,1)$ or $(1,-1)$ .

This gives us:

$c_6 = 2c_7 + c_8 = 5$

$c_5 = 2c_6 + c_7 = 12$

$c_4 = 2c_5 + c_6 = 29$

$c_3 = 2c_4 + c_5 = 70$

$c_2 = 2c_3 + c_4 = 169$

$c_1 = 2c_2 + c_3 = 408$

$c_0 = 2c_1 + c_2 = 985$

From $(0,0)$ we have to go $8$ step toward the $x$ axis. So we have $5$ cases:

Case $1$ : We have to use size $(2,0)$ , $0$ times . So, in this case we can go $2^8 = 256$ ways.

Case $2$ : We have to use size $(2,0)$ , $1$ times . So, in this case we can go $\frac {2^6 \times 7!}{6!} = 448$ ways.

Case $3$ : We have to use size $(2,0)$ , $2$ times . So, in this case we can go $\frac {2^4 \times 6!}{ 2! \times 4!} = 240$ ways.

Case $4$ :We have to use size $(2,0)$ , $3$ times . So, in this case we can go $\frac {2^2 \times 5!}{ 2! \times 3!} = 40$ ways.

Case $5$ : We have to use size $(2,0)$ , $4$ times . So, in this case we can go $1$ ways.

Now, we have total, $256 + 448 + 240 + 40 + 1 = \boxed {985}$

Notice that two steps have x-coordinate 1, while the third has x-coordinate 2. We seek to use a sequence of these three steps so that the x-coordinates of them all add to 8. We break this into cases based on the number of 2's.

Case 1: 4 (2, 0)'s Obviously there is 1 in this case.

Case 2: 3 (2, 0)'s There are 5 steps in this path. Two of them will be non-(2, 0)'s, so there are $2^2\binom{5}{2}$ in this case.

Case 3: 2 (2, 0)'s 6 steps, 4 are non-(2, 0). This gives $2^4\binom{6}{2}$

Case 4: 1 (2, 0) 7 steps, 6 are non-(2, 0). This gives $2^6\binom{7}{1}$

Case 5: No (2, 0)'s There are 2 choices for each step, giving $2^8$ .

Summing these all gives $1+40+240+448+256=\boxed{985}$

Consider a step of size (i, j). If we take 0, 1, 2, n of these steps, we've travelled (0, 0), (i, j), (2i, 2j), (ni, nj). Based on this observation, we can express all possible distances travelled using this step alone as a generating function on $x^i y^j$ .

For step (1, 1), we have $x^0 y^0 + x^1 y^1 + x^2 y^2 + ... = \sum_{a=0}^\infty x^ay^a$

For step (1, -1), we have $x^0 y^0 + x^1 y^{-1} + x^2 y^{-2} + ... = \sum_{b=0}^\infty x^by^{-b}$

For step (2, 0), we have $x^0 y^0 + x^2 y^0 + x^4 y^0 + ... = \sum_{c=0}^\infty x^{2c}$

The steps are pairwise independent, so the product of the generating functions $\sum_{a,b,c \ge 0} x^{a+b+2c}y^{a-b}$ will give us all possible combinations of steps to get from (0, 0) to any point (x, y). For x = 8, we want all non-negative solutions to $a+b+2c=8$ . Each solution represents a path that takes a+b+c steps. These steps can be taken in any order, so this means we need to permute a, b, c objects of types 1, 2, 3 respectively.

Number of paths = 256 + 448 + 240 + 40 + 1 = 985

The number of paths to x = 1 is clearly 2 (select one of the first two moves), and the number of paths to x = 2 is clearly 5 (either one of the first two moves followed by another (4) or just the third (1)).

Then, if $N_n$ denotes the number to x = n, we have $N_n = 2N_{n-1} + N_{n-2}$ , considering each of the three possibilities for the last move.

Running this recurrence generates 2,5,12,29,70,169,408,985.

Let $P_n$ be the number of paths from the point $(0,0)$ to the line $x = n.$ Consider the last step of such a path. If it is a $(2,0)$ step, then the rest of the path is a path in $P_{n-2}.$ If the last step is $(1,1)$ or $(1,-1)$ then the rest of the path is a path in $P_{n-1}.$ Thus, the number of paths of length $n$ is $P_n = P_{n-2} + 2P_{n-1}.$ We know that $P_{0} = 1$ and $P_{1} = 2.$ We recursively calculate the following values:

$\begin{array}{|r|ccccccccc|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline P_n & 1 & 2 & 5 & 12 & 29 & 70 & 169 & 408 & 985\\ \hline \end{array}$

Thus, there are $985$ paths to the line $x = 8.$

Can I possibly contribute a new solution? Yes, I can!

From the point $(0,0)$ to the line $x = n \geq 0$ there are $P(n) = \frac{(2+\sqrt 2)(1 + \sqrt 2)^n + (2-\sqrt 2)(1 - \sqrt 2)^n}{4}$ of these paths. In fact, since the second term is very small, $P(n) = \left[(\tfrac 14(2 + \sqrt 2)\cdot (1 + \sqrt 2)^n\right],$ where $[\cdot]$ stands for rounding off to the nearest integer.

With $n = 8$ , $P(8) \approx [0.85355\cdot 2.4142^8] = \boxed{985}.$

(Admittedly, I first derived the recursion relation that many other solutions here show. But now we have a direct equation that works quickly for all values of $n$ . For instance, for $n = 20$ we have $38\:613\:965$ paths.)

Here is how the equation was derived: the general solution of a recurrence of the form $a_n = 2a_{n-1} + a_{n-2}$ is the sum of two exponential sequences, $a_n = c_{+}\:p_{+}^n + c_{-}\:p_{-}^n.$ The bases $p_\pm$ must satisfy $p_{\pm}^2 = 2p_{\pm} + 1\ \ \therefore\ \ p_{\pm} = 1 \pm \sqrt 2.$ To find the coefficients $c_{\pm}$ , we use $a_{-1} = 0$ and $a_0 = 1$ to find $c_{+} + c_{-} = 1,\ \ \ (-1+\sqrt 2)c_{+} + (-1-\sqrt 2)c_{-} = 0.$ (Note that $1/(1 \pm \sqrt 2) = -1 \pm \sqrt 2$ .) Substituting the first equation in the second, we see that $-1 + (c_{+} - c_{-})\sqrt 2\ \ \therefore\ \ c_{+} - c_{-} = \tfrac12\sqrt 2.$ Adding and subtracting the equations for $c_{+} \pm c_{-}$ , we finally get $c_{\pm} = \tfrac12 \pm \frac14\sqrt 2 = \tfrac14(2\pm \sqrt 2).$

Let $A_{n}$ be the number of paths to \x=n