Problem 2.14 Easy Free 4 variations

Lattice Paths Across a Grid

A particle starts at $(0,0)$ on the integer lattice and repeatedly steps either one unit right or one unit up. How many distinct paths take it to $(6,6)$ ?

Work it out, then compare with the answer.

SolutionShow the worked solution

Every path consists of exactly $12$ steps: $6$ to the right ( $R$ ) and $6$ up ( $U$ ), in some order. Each path matches exactly one word of length $12$ with six $R$ ’s and six $U$ ’s. So we only need to choose which $6$ of the $12$ positions hold a $U$ :

\binom{12}{6}=\frac{12!}{6!\,6!}=924.

\boxed{924}

Generalisation. The number of right/up paths from $(0,0)$ to $(m,n)$ is $\binom{m+n}{m}$ .

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 2.14a

Using the same right/up steps from $(0,0)$ to $(6,6)$ , how many paths pass through the point $(2,3)$ ?

Work it out, then compare with the answer.

Solution

Split each path at $(2,3)$ . Any first leg can be followed by any second leg, so the counts multiply.

From $(0,0)$ to $(2,3)$ there are $\binom{5}{2}=10$ paths.
From $(2,3)$ to $(6,6)$ the path needs $4$ right steps and $3$ up steps, giving $\binom{7}{4}=35$ paths.

Hence the number of paths through $(2,3)$ is $10\cdot 35=350$ .

\boxed{350}

Variation 2.14b

Using the same right/up steps from $(0,0)$ to $(6,6)$ , how many paths pass through $(2,3)$ or through $(4,6)$ (or both)?

Work it out, then compare with the answer.

Solution

Let $A$ be the set of paths through $(2,3)$ and $B$ the set of paths through $(4,6)$ . By inclusion–exclusion, the required count is $|A|+|B|-|A\cap B|$ .

From the previous variation, $|A|=350$ .
There are $\binom{10}{4}=210$ paths to $(4,6)$ , and from there only one path ( $RR$ ) to $(6,6)$ . So $|B|=210$ .
A path through both points goes $(0,0)\to(2,3)\to(4,6)\to(6,6)$ . The legs have $\binom{5}{2}=10$ , $\binom{5}{2}=10$ and $1$ paths respectively, so $|A\cap B|=100$ .

Therefore

|A\cup B|=350+210-100=460.

\boxed{460}

Variation 2.14c

A particle starts at $(0,0,0)$ and at each step moves one unit in exactly one of the three positive coordinate directions. How many distinct paths take it to $(3,4,5)$ ?

Work it out, then compare with the answer.

Solution

Each path is a word of length $12$ made of $3$ $X$ ’s, $4$ $Y$ ’s and $5$ $Z$ ’s, one letter per step in that direction. The number of such words is the multinomial coefficient

\binom{12}{3,4,5}=\frac{12!}{3!\,4!\,5!}=27720.

\boxed{27720}

Variation 2.14d

A particle starts at $(4,4)$ . On each turn, independently with probability $\tfrac{1}{3}$ each, it moves one unit in the $-x$ direction, one unit in the $-y$ direction, or one unit diagonally in the $(-1,-1)$ direction. It stops the first time it reaches the $x$ -axis or the $y$ -axis. Find the probability that it stops exactly at the origin.

Work it out, then compare with the answer.

Solution

The particle must pass through $(1,1)$ . Both coordinates never increase. The only points from which one step reaches the origin are $(1,0)$ , $(0,1)$ and $(1,1)$ . The first two lie on an axis, so the particle would already have stopped there. Hence it must reach $(1,1)$ and then step diagonally, which happens with probability $\frac13$ .

Probability of reaching $(1,1)$ . Any path from $(4,4)$ to $(1,1)$ keeps both coordinates at least $1$ , so it never stops early. Suppose the path uses $k$ diagonal steps. Then it also uses $3-k$ left and $3-k$ down steps, for $6-k$ steps in total. Each such path has probability $3^{-(6-k)}$ . Summing over $k$ :

\frac{\binom{6}{3}}{3^6}+\frac{\binom{5}{2,2,1}}{3^5}+\frac{\binom{4}{1,1,2}}{3^4}+\frac{1}{3^3} =\frac{20+90+108+27}{729}=\frac{245}{729}.

Multiplying by the final $\frac13$ gives

\boxed{\frac{245}{2187}\approx 0.112}

Spotted an error? Email us