# Thread: inclusion and exclusion principle

1. ## inclusion and exclusion principle

count the number of paths from A to B ? which you can just go right or up? (with inclusion and exclusion principle)

* plz write the solution for a foolish person : )

2. ## Re: inclusion and exclusion principle

Originally Posted by mshou
count the number of paths from A to B ?
This is not a question? It is a command? Therefore, no question mark is necessary?

Let's introduce a coordinate system with origin at A and the unit length equal to the grid size. Then A has coordinates (0, 0) and B has coordinates (8, 7).

There are two holes in the grid. A path goes through the first hole iff it goes through (3, 3). Let X be the set of such paths. A path goes through the second hole iff it goes through (5, 5) and (5, 6). Let Y be the set of such paths. You need to find |X ∪ Y| and subtract it from the number of paths from A to B in the grid without holes. By inclusion-exclusion principle, it is sufficient to find |X|, |Y| and |X ∩ Y|.