OG11 - Question 195

[DavoodBeater]

Could anyone please give a general solution for this question? since as the vertical or horizontal lines increases, it is not possible to count the ways.

Question 195 (Problem Solving) from the OG11.
Here is the picture, and we need the number of way from X to Y without any backward steps

OA: 10

[Ian Stewart]

In the diagram, no matter how you go from X to Y, it's going to take you five steps, and every path will have two steps going East, and three steps going North. So you can think of a path as a 'word' containing 2 E's and 3 N's. That is, if you go east twice then north three times, we can think of that path as the 'word' EENNN. So the number of paths in the diagram is just equal to the number of 5-letter words you can make using 2 E's and 3 N's. That's just 5C2 = 10, and you can generalize this to any size grid.

[DavoodBeater]

exactly, that 's great. that 's worthy. concept matters rather than counting.
Thanks Ian.

[mrsmarthi]

So the number of paths in the diagram is just equal to the number of 5-letter words you can make using 2 E's and 3 N's. That's just 5C2 = 10, and you can generalize this to any size grid.

Shouldn't this be permutation with repitions of 2 and 3 ie 5!/(2! * 3!) because E and N are repeated 2 and 3 times respecitively?

I agree that answer is still 10.

[DavoodBeater]

the one that you wrote is combination.
permutation is used when the objects are distinguishable.

[Ian Stewart]

So the number of paths in the diagram is just equal to the number of 5-letter words you can make using 2 E's and 3 N's. That's just 5C2 = 10, and you can generalize this to any size grid.

Shouldn't this be permutation with repitions of 2 and 3 ie 5!/(2! * 3!) because E and N are repeated 2 and 3 times respecitively?

I agree that answer is still 10.

Yes, those are two equivalent ways of looking at the problem. We can say 'we have five letters in our word, and we need to choose two of them to be the letter 'E' (so the remaining three letters will be 'N'), so the answer is 5C2'. Or we can use the formula you quote above, for counting the number of arrangements we can make of a set of letters when some letters are repeated. Both approaches will always give the same answer if you only have two different types of letter.