Question

Morris Mouse can easily find his way through the maze from the entrance A to the exit B. However, he only receives food if he finds the exit without going west or south. (North is towards the top of the page.) How many different paths can he take through the maze to receive food?

Answer 1

Hmm, is there a photo of the maze? :)

Answer 2

https://angel.spcollege.edu/AngelUploads/QuestionData/2bfb73e4-236a-4599-bf10-af270b97f4c8/61324442322642544448.png#

Answer 3

I just need to figure the formula

Answer 4

Have you heard or read about Dyck paths? http://mathworld.wolfram.com/DyckPath.html

The number of Dyck paths is only a portion of the total number of paths the mouse can take in this case, however. The answer can definitely be written in terms of the Catalan numbers.

In this case, any path the mouse takes (in order to get the cheese, so in terms of north and east only) has length 10. This means you would consider the fifth Catalan number, \(C_5=42\).

These 42 paths count all those that don't cross the maze's central diagonal. Because of this, I think the total number of paths would be twice the number of Dyck paths, so 84.

Answer 5

Greatly appreciated......interesting the choices for this were A) 30,240 B) 15,120 C) 252 D ) none of these

Answer 6

Well I'm not suggesting that what I think is the answer is correct... Think of it more as a lower bound.

The Catalan numbers count all paths like this:

but not like this: