# Navigate a Grid Using Combinations And Permutations

Puzzles can help develop your intuition -- figuring how to navigate a grid helped me understand combinations and permutations.

Suppose you're on a 4 × 6 grid, and want to go from the bottom left to the top right. How many different paths can you take? Avoid backtracking -- you can only move right or up.

Spend a few seconds thinking about how you'd figure it out.

## Insight: Convert Pictures To Text

When considering the possible paths (tracing them out with your finger), you might whisper "Up, right, up, right...".

Why not write those thoughts down? Using "u" and "r" we can write out a path:

r r r r r r r u u u u


That is, go all the way right (6 r's), then all the way up (4 u's). The path in the diagram would be:

r r r r u u u u r r


Using the text interpretation, the question becomes "How many ways can we re-arrange the letters rrrrrruuuu?"

Ah, the ubiquitous combination/permutation problem -- never thought it'd be useful, eh?

## Understanding Combinations And Permutations

There's several ways to see combination and permutation problems. Once the first explanation clicks, we can go back and see it a different way. When trying to build math intuition for a problem, I imagine several mental models circling a core idea. Starting with one insight, I work around to the others.

## Approach 1: Start The Same

Instead of having 6 rights at 4 ups, imagine we start with 10 rights (r r r r r r r r r r).

Clearly this won't do: we need to change 4 of those rights into ups. How many ways can we pick 4 rights to change?

Well, we have 10 choices for the first 'right' to convert (see the combinations article). And 9 for the second, 8 for the third, and 7 choices for the final right-to-up conversion. There are 10 * 9 * 8 * 7 = 10!/6! = 5040 possibilities.

But, wait! We need to remove the redundancies: after all, converting moves #1 #2 #3 and #4 (in that order) is the same as converting #4 #3 #2 #1. We have 4! (4 * 3 * 2 * 1 = 24) ways to rearrange the ups we picked, so we finally get:

$\displaystyle{\frac{(10!/6!)}{4!} = \frac{5040}{24} = 210 }$

We're just picking the items to convert (10!/6!) and dividing out the redundancies (4!).

## Approach 2: Just Use the Combination Formula

Halfway through that explanation, you might have realized we were recreating the combination formula:

$\displaystyle{C(10,4) = 210}$

That's the shortcut when you know order doesn't matter. However, sometimes I'm not sure whether I need a permutation or combination from the outset. While saying "Just use C(10,4)" may be accurate, it's not helpful as a teaching tool. Sometimes it helps to re-create the situation on your own.

## Approach 3: Start Different

Here's another approach: instead of letting each r and u be interchangeable, label the 'right' moves r1 to r6, and the 'up' moves u1 to u4. How many ways can we re-arrange these 10 items?

This question is easy: 10! = 3,628,800 (wow, big number). We have 10 choices for the 1st move, 9 for the second, and so on, until we have 2 choices for the 9th and only 1 for the last. Cool.

Of course, we know that "r1 r2 u1 u2" is the same path as "r2 r1 u2 u1". We can shuffle the r's and u's in their own subgroups and the path will stay the same.

• How many ways can we shuffle all 10? 10! = 3,628,800
• How many ways can we shuffle 6 r's? 6! = 720
• How many ways can we shuffle 4 u's? 4! = 24

So, we start with the total number of possibilities (10! = 3,628,800) and divide out the cases where we shuffle the r's (6! = 720) and the u's (4! = 24):

$\displaystyle{10! / 6! / 4! = 10! / (6! \cdot 4!) = 210}$

Neat! It's cool seeing the same set of multiplications and divisions in different ways, just by regrouping them.

## Why is this useful?

One goal is to learn how problems can be transformed. Remember that painting of the old lady & young woman?

Do you see both? Can you switch between them? Isn't that cool?

Part of the fun of the grid-path puzzle is seeing how to look at a problem using a visual or text metaphor. The more math you learn, the more models you have available, and you can turn problems into each other.

This doesn't have to be "practical" -- it's fun to see how listing out paths can be be done simply using letters on paper.

In math lingo, problems which can be converted to each other are *isomorphic". Mathematically, they may be the same -- but from a human perspective, one may be easier than the other (like seeing the old woman or young woman first).

For the grid puzzle, we used each perspective where comfortable:

• Visualizing the grid to understand the general problem and see a single path.
• Write the paths as text to see the general format of all paths & an easy method to enumerate them

And that's the key lesson: It's completely fine to use one model to understand the idea, and another to work out the details. Math becomes difficult when we think there's only one way to approach it.

## Variations and Extensions

Now that we've been building our mental models, let's tackle some harder problems.

Imagine your "grid" is actually in 3 dimensions. This is harder to draw, but the text representation keeps on working. Let's say we have a cube (x, y and z dimensions) that is 5 units long on each side. How many paths are there from one corner to its opposite?

Hrm. In this case, I might try the second approach, where we listed out all the possibilities. Assume we label each move differently: we have 5 uniquely-labeled moves of each type (x1-x5, y1-y5, z1-z5). We can arrange these in 15! ways (it's a huge: 1.3 trillion). But, we need to remember to divide out the redundancies for each dimension.

There are 5! ways to rearrange the 5 identical motions in each direction, and we divide them out:

$\displaystyle{15! / 5! / 5! / 5! = 15!/(5!\cdot 5!\cdot 5!) = 756,756}$

Wow, that's huge number of paths on a small cube! Earlier today you'd have trouble with the question -- I know I would have. But starting with the grid example and converting it to text, we've beefed up our model to handle 3 dimensions. Paths in four, five or 10-d should be no problem.

## Redefining The Problem

Here's the fun part: instead of changing how we see the solution, why not change the problem? What else could "Find paths on a grid" represent?

• Trap platform: Let's say you're making a set of trapdoors 4 × 6, with only 1 real path through (the others drop you into a volcano). What are the chances someone randomly walks through? With a 4×6 it's 210, as before. With a 12×12 grid it's 24!/12!12! = 2.7 million paths, with only 1 correct one.

• Order of operations: Suppose you have 10 sets of exercises to do: 4 identical leg exercises, and 6 identical arm exercises. How many different routines can you pick? This is the same as navigating the path, except the axis labels are "legs" and "arms" instead of "right" and "up".

• Random walk. Suppose we know an object moves randomly up or right. What's the chance it hits our desired endpoint after 10 steps? Well, there are 2^10 = 1024 ways to move up or right (pick "u" or "r" 10 times), and 210 ways to get to our exact destination. Therefore, you can expect to hit our spot 210 / 1024 = 20.5% of the time!

Here's a calculator to play with a few variations:

## Onward and Upward

Puzzles are a fun way to learn new mental models, and deepen your understanding for the ones you're familiar with. While I might "know" combinations and permutations, it's not until I recognize them in the wild do I feel really comfortable. Ideas do no good sitting inside your head like artifacts in a museum -- they need to be taken out and played with. Happy math.

## Questions & Contributions

1. Null Pointer says:

Wonderful explanation. The variations section really helps ingraining the concepts underlying.

2. Nobody says:

That was a good idea for an article. I personally like your example with the arm/leg stretches. It links problems that one would never think to compare. (I’d have never thought thought that the solution to the number of combos for an arm/leg stretch routine compares with finding paths in a grid).

An additional extension (other than adding dimensions) is to make the grid have diagonals, with d = ur (together?). This would make the original problem allow 4 ups and 6 rights; or 3 ups, 5 rights, and 1 diagonal; etc. I think that for U ups and R rights (and a maximum of D diagonals <= min(U,R)), we have (U+R)!*sum_{k=0}^D 1/((U-k)!*(R-k)!*k!). So for the original problem of U = 4, R = 6, D = 4, there would be 43,050 combos.

This might correspond to having flashlights, where some are green, others are red, and the rest are yellow. How many combos will produce the exact same color.

3. Another most xlnt article from Kalid; thanks for alternative ways to view concepts we’ve seen before.

4. Kalid says:

@Null Pointer: Thanks!

@Nobody: Cool analysis! I like the diagonal / flashlight analogy, it’s a neat way to extend the problem.

@Bill: Thanks! I like going back and finding ways to link concepts I’ve ‘learned’.

5. Bushra says:

For the first time I have finally understood the grid problem!..I alwayz got bogged down by it!

Wonderful way to explain it all….

Thanks a ton!

6. Kalid says:

@Bushra: You’re welcome!

7. didxga says:

very impressive for the way you think! keep your awesome post up.

8. Kalid says:

@didxga: Thanks, glad you liked it!

9. Jordan says:

I nice continuation to our problem Kalid 😉

10. Guru says:

Hey been reading thru some of your posts on math..excellent work..keep it up.

But this was the post I found tough to understand..was totally stumped with the cube thing and could not quite get the total moves = 2^no.of steps thing. How?

Anyways..awesome work..

11. Guru says:

hmm ok..got the 2^no. of steps thing. But the cube still stumps me

12. Matt says:

In the random walk problem, is the number of possible up/right steps really 2^10? If we randomly pick either ‘up’ or ‘right’ ten times, then we will get some paths that take us beyond the boundaries of the grid like 10 consecutive up movements or 10 consecutive right movements. Since these are impossible, shouldn’t they be excluded from the denominator of the probability?

13. Dud says:

Another solution is using Pascal’s triangle (and by extension, the binomial theorem) If you consider the number of ways you can reach successive corners, Pascal’s forms from the start up toward the finish.

14. Kalid says:

@Dud: Thanks! Yes, Pascal’s Triangle is another cool way to see it.

15. Arief Mulya Utama says:

Kalid,

I dont know if u realize this or not, but what you’ve done here is a great rare thing that really contributes a lot to a lot of us.

I dont think a simple thanks is enough to express my gratitude, but, Thank you!

All the best.
-arief

16. Kalid says:

@Arief: Thank you for the heartfelt message! It really means a lot knowing these articles are helping people. I’d like us to avoid the frustration we all encounter in learning!

17. Gina says:

So what if it was a 2 x 5 grid. How many paths would there be?

18. Joy says:

thx Khalid ,we were doing Binomial Expansion in class and the teacher made it look like 2012. the internet wasn’t very helpful, because everyone seems to be just happy with what they have got, your explanation regarding permutation and combination and this post along with 3 days of sulking and thinking got me the intuition i needed for binominal expansion, when i finally figured it out i was like “this is how we are supposed to do this, i need to share it with the world”, but too busy(lazy) to do it myself :P, more importantly i learned a important trade in mathematics, figuring out things by myself. i hope you can expand your site to cover all topics in mathematics one day, your site is already on my chrome’s list of top visited website along with wikipedia and facebook:).

19. Kalid says:

@Joy: Thanks! I think a huge part of math is getting that confidence to figure things out for ourselves, but also sharing the insights that helped us along the way.

20. there are 3 eggs in a basket:1purple,1orang ,and 1green.two eggs are taken from the bag at the same time without looking. how many different ways could 2eggs be taken from the bag if the order in which the2 eggs are taken does not matter?

21. yg says:

Great article. Another way to approach the 3-d question is to do

(15c5)*(10c5)

22. Mahesh says:

Thakns…infinite times…this site is so useful…

23. kalid says:

@Mahesh: You’re welcome :).

24. Neevan says:

wow a nice explanation..thanks a lot mi8…

25. Prajwal nayak says:

Explanation for that Path problem is too good.. Thought to solve it using Backtracking algorithm… Permutation made it so simple Thanks a lot

26. I understand the math, but I’m overwhelmed by the numbers that I need, in groups of 5. Please show me a simply way to figure it out.

27. Anonymous says:

Nice…

28. ben says:

pls i would like to know how many ways i can arrange 6 numbers…the others matters. i want to use that in playing games..the other is very important. reply thanks. Ben

29. abhishek says:

what if we had to exclude two or more points in the first grid . how many ways then???

30. lurker says:

You got a type there:
“That is, go all the way right (6 r’s), then all the way up (4 r’s)”
that should be “[…] all the way up (4 u’s)”

31. Amir says:

Thank you.
I was wondering to see if there are any formal references (book or paper) addressing the same problem?
I am pretty sure there must be something, but couldn’t find yet.

Amir.

32. Amir says:

I will appreciate receiving any hints on my e-mail about the question I just wrote
my email: azarinmehr@yahoo.com.

Thanks

33. anna banana says:

thanks a lot, it was a real delight

34. Nemesis says:

Thank you so so much! The explanation is great. I am glad this was the first link that came up when I tried searching

35. Aseem Saxena says:

Dear Khalid,

Can you help me with the following:

I have 3 variables… each with different options:

1. Color: Red, Blue, Green and Orange (4 options)
2. Weight: Heavy, Light and Medium (3 option)
3. Price: Cheap and Expensive (2 options)

While I know that I have a total of 4 x 3 x 2 = 24 combinations, I am struggling to set a process to list all combinations….

Regards,

Aseem

36. kalid says:

Hi Aseem,

For this, imagine a tree. There are 4 branches from the root (Red, Blue, Green, Orange). Each of those branches has 3 branches (Heavy, Light, Medium). And each of those has 2 branches (Cheap, Expensive). If you draw it out it might help visualize every possibility.

37. Aseem Saxena says:

Dear Khalid,

That helped…. I am trying to come up with a process wherein I can populate a grid (say in Excel) … So I can repeat the max variable (Color with 4 option)

RBGORBGORBGORBGO

Then I listed Weight below them…

RBGORBGORBGORBGO
HMLHMLHMLHMLHML

But when I finished the sheet with this thought process, I had duplicates

Can you help?

Regards,

Aseem

38. kalid says:

If it’s just 24 options, I’d write them out like this:

[Color] [Weight] [Cost]

Note, you need to repeat color 6 times (3 weights * 2 cost for each color):

R H C
R H E
R M C
R M E
R L C
R L E

In my head I think “We have 6 R’s, let’s write them down. Then, we have 2 H’s for each R (since there are 2 costs), 2 M’s, and 2 L’s. Then we write in the colors.”

Then you repeat for the other colors (B, G, O). If it’s more than 24 I’d use a VBA program or add-in to generate the combinations (Excel doesn’t seem to make it easy on its own).

39. Aseem Saxena says:

Dear Kalid,

Thank you for taking out the time for replying…. If you put a PayPal button on your site, I will gladly press it

I teach matriculates in South Africa gratis to become manual software testers…. One of the techniques used in software testing is using a decision table… wherein the software must behave in a different manner for a given combination (like in the example above)…

While I can work out the combinations intuitively (I followed the same process as your), my students do not have the experience…. So I need a fool proof method for them…

I was able to nail the process for the first variable (each color must repeat 6 times (cover the option for color and multiply the options for other variables) and repeat each color option that many times … …. but I am not able to come up with a process for listing the other options below that…

Any thoughts?

R

A

40. kalid says:

Hi RA, glad to help. This is basically a “FOR” loop in programming, where you run through every possibility for the first item, every possibility for the second, and the next.

So, I might start like this:

R

Then add in the first weight, H

RH

And then add the first cost, C

RHC.

We have another cost to try (E), we use that too:

RHE

We’re done with cost, so we go to the next weight:

RM

and then fill in the cost:

RMC
RME

and then the next weight, and the colors for it:

RLC
RLE

Basically, you are “looping” through each option in term. You start with the color, loop through all the weights for each color, and for each weight, loop through all the colors. Does that help?

41. Jincy P says:

Wonderful. Thanks a million (THOUGH IT MAY NOT BE ENOUGH) .