How many different paths from origin to $(4,4)$ if you can't cross $y = x$? Assuming you can only go right 1 step or up 1 step, and you're trying to get from the origin to $(4,4)$ or any $(n,n)$ or $(m,n)$, what is an algorithm to help you determine the number of paths possible without crossing $y=x$?
I can do it just by experimenting and drawing, but I was told it's better to use an inductive proof.
I'm not sure how I'd do that.
Intuitively, I know that it's the number of paths from the origin to $(n,n)$, which is $\binom{2n}{n}$ minus the number of paths that cross the $y=x$ line.
The base case is, for example, $(1,1)$. Theres two possible paths, and one crosses $y=x$. But what next?
In prinziple you always have two choices, going up or going to the right. But obviously you have two limitations.
Depending on your first step, you are either under or above the line. You can view the sqauare with the corner points (0,0) and (4,4). The line y=x divides it into two.
W.l.o.g you can assume, that your first step is one to the right, so you have to stay under the line. Whatever you do, u have to go 4 steps to the right and 4 steps to the top in total.
The question is, how many choices do you have? Assume you are still on heigth 0, so your y=0. Than you have 4 choices to go one step up. On (0,1) to (1,1), from (0,2) to (1,2), from (0,3) to (1,3) and from (0,4) to (1,4).
The same goes for y=1, there u have three possibilities to go one step up. For y=2 you have two choices and for y=3 only one.
In total you have 4+3+2+1 = 10 possiblities.
Since you can only go right and up, you have to chose one way up for each y. For y=0 you have to take one of your 4 choices. For y=1 one of your three choices and so on.
In total you have 4 * 3 * 2 * 1 = 4! choices to go up. You can mirror this explanation to the triangle above the line y=x.
So in total you have 2 * 4! = 48 possible ways to get from (0,0) to (4,4).
You can easy generalize this problem on (n,n) or even (n,m).
In prinziple you always have two choices, going up or going to the right. But obviously you have two limitations.
Depending on your first step, you are either under or above the line. You can view the sqauare with the corner points (0,0) and (4,4). The line y=x divides it into two.
W.l.o.g you can assume, that your first step is one to the right, so you have to stay under the line. Whatever you do, u have to go 4 steps to the right and 4 steps to the top in total.
The question is, how many choices do you have? Assume you are still on heigth 0, so your y=0. Than you have 4 choices to go one step up. On (0,1) to (1,1), from (0,2) to (1,2), from (0,3) to (1,3) and from (0,4) to (1,4).
The same goes for y=1, there u have three possibilities to go one step up. For y=2 you have two choices and for y=3 only one.
In total you have 4+3+2+1 = 10 possiblities.
Since you can only go right and up, you have to chose one way up for each y. For y=0 you have to take one of your 4 choices. For y=1 one of your three choices and so on.
In total you have 4 * 3 * 2 * 1 = 4! choices to go up. You can mirror this explanation to the triangle above the line y=x.
So in total you have 2 * 4! = 48 possible ways to get from (0,0) to (4,4).
You can easy generalize this problem on (n,n) or even (n,m).