Walking in a Rectangular Grid

If you're native to a city like Manhattan, then you're probably intimately familiar with the strategies needed for navigating on a grid. If you want to go from point \(A\) to point \(B\) on a grid, you can make a lot of choices about how to travel. Even restricting yourself to only the most efficient paths that move only eastward and northward along roads (never backtracking to the south or west), there are many ways to make the journey. The question is: How Many?

This page will explain how to solve these "grid-walk" counting puzzles, including exploring the general solution to the basic case of an unrestricted journey between two corners of an \(n\) by \(m\) grid. There are also more complicated extensions to this kind of puzzle, where the paths are constrained in some way.

The approach we'll take on this page is to apply Combinations to the problem, so if you're not yet familiar with calculating \(A \choose B\), you might want to read the combinations wiki first.

Here are some tips to get you started:

1. When given a scenario for a problem, experiment with it. Try to construct a few of the solutions that you're trying to count and get a feel for how the directions or specifications in the problem statement constrain your choices.
2. If you've solved a similar kind of problem before, review your solution technique for that problem and try to modify it to suit the constraints of the new problem.
3. If possible, break a large problem into parts, solve each part separately, and then combine the two solutions together to compute your final answer.
4. Symmetry is at the heart of many combinatorics puzzles. Look for a symmetrical way to think about or group objects that you're counting. Symmetry makes large sets of objects much easier to count.
5. If you get stumped on a particular problem, look at the solution and be sure to study the technique so that you can use solving future problems.

As a tourist in NY, I want to go from the Grand Central Station (42nd street and 4th Avenue) to Times Square (47th street and 7th Avenue). I needed my morning coffee, and wanted to go to a Starbucks that's located at 44th street and 5th avenue.

If I only walk West and North, how many ways are there for me to get there?

This problem can be broken into two parts: first, how many ways are there to get from the station to the coffee shop; second, how many ways are there to get from the coffee shop to Times Square? (In other words: it's early in the morning... let's just get to the coffee first! Then we'll figure out the rest.)

Part 1: Station to Coffee

There are 3 ways to get from the station to the coffee shop:

This part of the problem is small enough that it can be counted just by looking, guessing, and counting. But there's a pattern visible in the 3 cases:

Consider giving a person directions to the form of "Go 1 block North, then 1 block West, then another 1 block North." In order to get from the station to the coffee shop, we have to go West = W once and North = N twice. So, we'll always have 3 steps to our directions: "1, 2, 3", exactly one of which will be moving West.

We can do that one westward move as the first move, the second, or the third:

\[ \text{WNN or NWN or NNW}.\]

Then the other two steps to the directions are definitely going North. So, really, what we are counting is the number of ways to choose 1 of 3 direction steps as our W step: "3 choose 1" = \({3 \choose 1} = 3.\)

Part 2: Coffee to Times Square

By the same reasoning, in any sequence of directions that get one from the coffee shop to Times Square walking on blocks westward and northward, one will in total move 1 block West twice, and 1 block North 3 times. Thinking of the directions again as lists (aka NNWNW would be the path pictured below), we will always have 5 steps in the directions, exactly two of which must be westward moves: "5 choose 2" = \({5 \choose 2} = 10.\)

Quick Combinations Review: "5 choose 2" = \({5 \choose 2} = 10\) because there are 5 ways to pick the first step of the directions that will be a W and then 4 ways to pick the second step of the directions that will be a W, then divide by 2 because the order in which they were chosen doesn't matter.

Part 3: Combine Parts 1 and 2

There are 3 ways to get from the station to the coffee shop, and then 10 ways to get from the coffee shop to Times Square. Therefore, by the Rule of Product, there are \(3 \times 10 = \fbox{30}\) ways to get from the station to Times Square, stopping at the coffee shop on the way.

Back to Quiz: New York, New York

In Combinatorics, you will learn how to strategically solve a tremendous variety of problems. The methods you'll learn include:

• Checking Cases: Taking an organized approach and splitting difficult problems into parts and cases is an essential skill to master.
• Using the Rule of Sum and Rule of Product: If you group the objects that you're counting wisely, the symmetry within the set of your objects and groups can let you use addition and multiplication as shortcuts to count.
• Counting Permutations: Counting the rearrangements of sets of objects.
• Counting Combinations: Counting the number of ways to partition a set of objects into groups.
• Principle of Inclusion and Exclusion (PIE): If the objects being counted are part of a larger context, there are many subtle and clever ways to count a set of objects indirectly, if it's too difficult to count directly.

Additionally, other mathematical fields including Geometry, Algebra, and Number Theory also have counting-related questions. For example: How often do the graphs of two specific functions intersect? How many prime numbers are there between 2 and 4 vs. 4 and 8 vs. 8 and 16...? How many different paths are there between two destinations in a transportation network? Counting challenges such as these can be extremely difficult, nothing like counting "\(1, 2, 3..\)."