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.

This is a companion discussion topic for the original entry at

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

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.

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

@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’.

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! :slight_smile:

@Bushra: You’re welcome!

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

@didxga: Thanks, glad you liked it!

I nice continuation to our problem Kalid :wink:

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…

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

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?

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.

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


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: 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!

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

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:).

@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.