# inclusion and exclusion principle

• Mar 9th 2013, 09:24 AM
mshou
inclusion and exclusion principle
Attachment 27457

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 : )
• Mar 9th 2013, 01:27 PM
emakarov
Re: inclusion and exclusion principle
Quote:

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|.