Here’s a famous puzzle:

 

Starting at the top-left cell marked S and taking horizontal steps one place only to the right or vertical steps downwards only, how many different paths are to the location marked E?

 

Play with this puzzle for a while before reading on. As you play, perhaps contemplate the following questions:

 

1. Given the location of the point E, is the grid shown in the diagram unnecessarily large?

2. Marking in different paths from S to E is awfully complicated. One could first count paths to different cells first, ones easier to handle, and look for patterns. For example, how many distinct paths are there from S to any cell on the top row? Write the answers in those cells. How many distinct paths take you to any cell in the leftmost column? To cells in the second row? Second column? Third row?

3. If you are willing to trust patterns, can you make a good guess as to the answer to the original puzzle?

 

 

There are two ways to approach this puzzle.

 

APPROACH NUMBER 1: FORMULAS

 

Every path from S to E can be described by a sequence of letters R and D. For example, the path given in the diagram can be described by the sequence:

 

RDRRDDRRRDRR

 

This sequence contains eight Rs and four Ds.  Moreover, any sequence of eight Rs and four Ds corresponds to a path from S to E.

 

 

Practice: Mark in on the diagram the paths given by DDRRRRRDRRRD and RRRRRRRRDDDD.

 

 

Thus the number of paths from S to E matches the number of ways to arrange twelve letters, eight Rs and four Ds. (That is, to label twelve slots with eight Rs and four Ds). The answer to the original puzzle is:

\(\dfrac{12!}{8!4!} = 495\) paths.

 

 

Exercise 30: How many paths are there from S to the bottom-right cell of the grid?

 

 

Exercise 31: Suppose the cell E is \(a\)  steps to the right of S and \(b\) steps down from S. Show that the number of paths from S to E is given by: \(\dfrac{(a+b)!}{a!b!}\).

 

 

Number the rows 0, 1, 2, …  with the top row being the zero-th row (for “zero steps to the right”) and number the columns 0, 1, 2, …  with the leftmost column being the zero-th column (for “zero steps down”). The cell E in the original diagram has position: row 4, column 8. The number of paths to it is \(\dfrac{12!}{4!8!}\). This is the number of ways to arrange 4 Rs and 8 Ds (RRRRDDDDDDDD).

 

 

In general, numbering rows and columns this way, the cell in row \(a\) and column \(b\) requires \(a\) Rs and \(b\) Ds to get to it and so the number of paths to it is:

\(\dfrac{(a+b)!}{a!b!}\).

 

Notice that this formula is correct for the entries on the top row which require \(b=0\) down steps, and for entries in the left column with \(a=0\):

 

\(\dfrac{(a+0)!}{a!0!} = \dfrac{a!}{a!0!} = 1\)

\(\dfrac{(0+b)!}{0!b!} = \dfrac{b!}{0!b!} = 1\)

 

(Thank goodness we set  \(0! = 1\).)  Notice for the top left entry right at position S we get:

 

\(\dfrac{(0+0)!}{0!0!} = \dfrac{0!}{0!0!} = 1\).

Apparently the math suggests there is one way to start at S and end at S – just stay put!

 

 

APPROACH 2: PATTERNS

 

If you fill in the answers for the number of paths to each cell, the following grid of numbers appears:

(Exercise 32 suggests that the position labeled S should also be assigned the number 1.)

 

Exercise 33: Explain why the table is symmetrical about the southeast diagonal line.

 

We have the formula \(\dfrac{(a+b)!}{a!b!}\) for the entry in the \(a\)-th row and \(b\)-th column (starting the counts at zero).

 

 

Have you noticed that each entry in an interior cell is the sum of two numbers – the number just above the cell and the number just to the left of the cell? This makes sense in terms of counting paths. Consider the circled cell. To reach this cell one can either first reach the cell just above – there are 15 ways to do this – and then step down, or reach the cell just to its left – there are 20 ways to accomplish this – and then step right. This gives a total of 15 + 20 = 35 paths to the circled cell.

 

Practice: Use this observation to fill the remainder of the table.

 

Resources