Willy lives at the origin and is trying to go to school at Maya Angelou Elementary, which is located at ( 6 , 4 ) . He needs to get to school by making successive movements one unit to the right or one unit up.
Unfortunately, the evil businessman Rockefeller Tycoon has put up fences between ( 1 , 1 ) and ( 2 , 1 ) and between ( 3 , 4 ) and ( 4 , 4 ) . Willy can no longer move along those paths.
In how many ways can Willy get to school?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Problem statement updated, thanks!
There are ( 6 1 0 ) = 2 1 0 ways for Willy to get from ( 0 , 0 ) to ( 6 , 4 ) that go through either wall (possibly both , possibly neither ).
There are ( 1 2 ) ⋅ ( 3 7 ) = 2 ⋅ 3 5 ways for Willy to get from ( 0 , 0 ) to ( 6 , 4 ) that go through the first wall.
There are ( 3 7 ) ⋅ ( 0 2 ) = 3 5 ⋅ 1 ways for Willy to get from ( 0 , 0 ) to ( 6 , 4 ) that go through the second wall.
There are ( 1 2 ) ⋅ ( 1 4 ) ⋅ ( 0 2 ) = 2 ⋅ 4 ⋅ 1 ways for Willy to get from ( 0 , 0 ) to ( 6 , 4 ) that go through both walls.
Therefore, there are 2 1 0 − 2 ⋅ 3 5 − 3 5 ⋅ 1 + 2 ⋅ 4 ⋅ 1 = 2 1 0 − 7 0 − 3 5 + 8 = 1 1 3 ways for Willy to get from ( 0 , 0 ) to ( 6 , 4 ) that go through neither walls.
What is the formula used to calculate the paths that go through both walls. I've checked the wiki, and no general formula is stated.
Log in to reply
The principle is called The principle of inclusion and exclusion
Problem Loading...
Note Loading...
Set Loading...
The problem statement itself has one major error I guess.
He needs to get to school by making successive movements one unit to the left or one unit up.
It should be one unit to the right or one unit up , because otherwise,it's impossible to go to the topmost right corner of the grid from the origin.
And the rest is simple. First count the number of ways from (0,0) to (6,4) . It should be 10C4 = 210. Then,count the number of ways from (0,0) to (1,1) and (2,1) to (6,4) . It should be 2C1 7C3 = 70. Then,count the number of ways from (0,0) to (3,4) and (4,4) to (6,4) . It should be 7C3 2C0 = 35. Then,count the number of ways from (0,0) to (1,1) and (2,1) to (3,4) and (4,4) to (6,4) . It should be 2C1 4C1 2C0 = 8,which should be subtracted.
Hence,the final count is = 210-(70+35-8) = 113