Problem:
Let be a positive integer. Determine the number of ways to walk from to using only up and right unit steps such that the path does not meet the lines or except at the start and at the end.
Solution
Solution:
Answer:
Consider the first point of the path that lies on . There are two possibilities for this point: and , and there is exactly one valid way of getting to each point from the origin. Similarly, consider the last point of the path that lies on . There are two possibilities: and , and there is exactly one valid way of getting to the destination from each of the two points. Now we count the number of valid paths from each of and , to each of and , and the answer will be the sum.
- From to : there are no forbidden points along the way, so there are ways.
- From to : the path must not pass through , and there is exactly one invalid path. So there are ways.
- From to : the path must not pass through , and there is exactly one invalid path. So there are ways.
- From to : the path must not pass through and , and there are exactly two invalid paths. So there are ways.
Summing, we obtain the answer: