Chaitanya's Random Pages

November 11, 2011

Counting rectangular lattice paths

Filed under: mathematics — ckrao @ 9:49 am

This post is inspired by an attempt at the following problem edited from the 1995 AIME.

Starting at (0,0) an object moves in the coordinate plane via a sequence of steps, each of length one. Each step is left, right, up, or down, all four equally likely. Find the probability that the object reaches (2,2) in six or fewer steps.

I wish to show my approach to the problem, which led me to find a formula for the number of ways the object reaches an arbitrary point (p,q) from (0,0) in n steps.

Before reading on, I encourage you to have a go at the above problem to get a feel for it!

The first thing to observe is that the object only can reach (2,2) in an even number of steps. The sum of the coordinates changes parity with each move, so it cannot reach (2,2) in say five steps. It can reach (2,2) in the minimum four steps only if each step moves towards that point, either to the right or upwards. Among four steps one chooses two to go up (and the other two to go right), so the number of ways of going from (0,0) to (2,2) in four steps is \binom{4}{2} = 6. Since in total there are 4^4 = 256 possible paths of four steps (a choice of four paths for each step), the probability that one arrives at (2,2) in exactly 4 steps is 6/256 = 3/128.

Next, we need to find the probability that one arrives at (2,2) for the first time in exactly six steps. To find this we will count the number of ways of arriving at (2,2) in exactly six steps (whether or not it arrived there in four steps) and subtract from that the number of ways in arriving at (2,2) in six steps having arrived there in four steps.

The second of these possibilities is easier to find, so let’s find that first. Above we saw that there are 6 ways of arriving at (2,2) in four steps. After two more steps it needs to return to (2,2), and there are 4 ways of that happening (the sixth step needs to be the reverse of the fifth). Hence in total there are 6 \times 4 = 24 ways for the object to arrive at (2,2) in six steps having been there two steps earlier.

Now we wish to find the number of ways of arriving at (2,2) in six steps without restriction.

We notice that to arrive at (2,2) in six steps, one of the steps needs to be in an “unhelpful” direction – either left or down. There are 6 choices of which of the six steps in which this occurs, and then 2 choices of direction. Then of the remaining five steps, the net position we wish to reach is (3,2) (if the unhelpful direction was left) or (2,3) (if it was down). In each case the number of ways to reach that position is \binom{5}{2} = 10. We conclude there are 6 \times 2 \times 10 = 120 ways of the object arriving at (2,2) in six steps without restriction.

The rest of the problem is easy: since there are 4^6 possible paths of six steps, the probability that one arrives at (2,2) for the first time in six steps is (120-24)/4^6 = 3/128. Combining this with the probability of arriving there in four steps, our final answer becomes 3/128 + 3/128 = 3/64.

After solving this I wondered about the question of how many ways there are of reaching an arbitrary point (p,q) in n steps. Let this number be f_n(p,q). To look for a pattern, I worked with small values of n and concentrating on the first quadrant progressively built up triangular arrays of numbers showing the number of ways of going to each point in n ways. The following recursion is used:

\displaystyle f_{n+1}(p,q) = f_n(p-1,q) + f_n(p+1,q) + f_n(p,q-1) + f_n(p,q+1)

The arrays are shown below for n = 2 to 6. Here the bottom left point corresponds to (0,0) while red dots indicate those lattice points that can not be reached.

Then it was time to stare at the numbers and look for a pattern. One thing I noticed was that the numbers corresponding to p = 0 or q = 0 (along the axes) are perfect squares. Then I noticed that for n = 6, the numbers along the diagonal p=q are multiples of \binom{6}{3} = 20. This enabled me to find the following representation for the numbers in terms of binomial coefficients.

From this the general formula (for any integers p, q) was conjectured to be

\displaystyle f_n(p,q) = \begin{cases} \binom{n}{(n + p + q)/2} \binom{n}{(n + p - q)/2}, & \mbox{if } p + q \equiv n \mod 2\\ 0, & \mbox{if } p + q \not\equiv n \mod 2. \end{cases}

This conjecture can be proven as follows. The above formula suggests that the number of ways to go to (p,q) can somehow be decoupled so that one can consider each of two directions independently. To do this we apply a rotation and replace the directions up, down, left and right with the directions north east, south west, north west, south east respectively:

\displaystyle (1,0) \rightarrow (1,-1) \quad (-1,0) \rightarrow (-1,1)
\displaystyle (0,1) \rightarrow (1,1) \quad (0,-1) \rightarrow (-1,-1)

This maps any point (p,q) to (p+q, q-p). We now consider the equivalent question of how many ways are there for the object to go to (p+q, q-p) from (0,0) using the four allowed steps (\pm 1, \pm 1).

This question is easier to solve since now we may treat each component separately:

  • for the first component we go to p+q in n steps (provided p + q \equiv n \mod 2) by choosing (n+p+q)/2 +1s and (n - (p + q))/2 -1s for each step’s first component. This can be done in \binom{n}{(n + p + q)/2}ways.
  • for the second component we go to q-p in n steps by choosing (n + q - p)/2 +1s and (n - (q-p))/2 -1s for each step’s second component. This can be done in \binom{n}{(n + p -q)/2} ways.

Hence we can go to (p+q,q-p) in a total of \displaystyle \binom{n}{(n + p + q)/2} \binom{n}{(n + p - q)/2} ways. Transforming back, this is equal to the number of ways of going to (p,q) from (0,0) using up, down, left and right moves of unit length provided p + q \equiv n \mod 2 (otherwise (p,q) cannot be reached). This proves the conjecture, an interesting result I had not seen before. The hard part was finding the pattern involving binomial coefficients by considering small cases for n.

It is interesting to see how this generalises the better known problem of reaching (p,q) (p, q non-negative) when using up or right moves only: it is equivalent to the case p + q = n, and using the above formula we find the number of ways to be

\displaystyle \binom{n}{(n + p + q)/2} \binom{n}{(n + p - q)/2} = \binom{n}{(n+n)/2} \binom{n}{(p + q + p - q)/2} = \binom{n}{p},

which we saw earlier (choose p of the n moves to be “right”).

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: