• M0★ M1 M2 M3 M4 M5

    Still a little confused about this formula... is there like a visual?

  • MOD M0 M1 M2 M3 M4 M5★

    When I try to think about Inclusion-Exclusion, I find it hard to think about it purely in terms of the sets and the numbers. I tend to try to use a visual metaphor: painting.

    Imagine if, every time we add a set's size to the total, we're painting over it in the Venn diagram. Similarly, subtracting a set's size is like removing one layer of paint. Our goal is to paint the entire Venn diagram with a single layer of paint. I'm going to borrow Professor Loh's visuals here for an example:

    alt text

    Here, we have 15 people who've been to Argentina, so $$|A| = 15$$

    We also have 10 people who've been to Bangladesh, so $$|B| = 10$$
    However, as the above diagram shows, if we add these two numbers together (painting both A and B in our Venn diagram), we've painted over the center twice. If we have more than one layer of paint on our diagram, we're overcounting!

    We can fix this by removing a layer of paint from the center. We're told that 5 people have been to both Argentina and Bangladesh, so $$|A \cap B| = 5$$

    Removing this layer of paint means subtracting it from the total, so our total is \(15 + 10 - 5 = 20\) people total. In symbolic notation, we get the following:

    alt text

    But that's with only two sets! It gets a lot more complicated when there are three or more sets. So let's talk about what happens when we add in the 6 people who've been to China. We now have the following sets:
    $$|A| = 15, |B| = 10, |C| = 6$$
    We can start just like we did when there were two sets - painting over everything. If we paint over A, B, and C, we sum up \(15 + 10 + 6\).

    However, just like with only two sets, we have too many layers of paint.

    alt text

    The orange, gray, and blue areas have each only been painted once, like we want. However, just like the previous example, our intersections (the white areas) have been painted over twice, and now there's a third area, at the center of the intersections (the green area) that has a full 3 layers of paint!

    We start fixing this just like we did in the previous example: removing the extra layer of paint from the intersections. There are 5 people who've been to Argentina and Bangladesh, 2 who've been to both Bangladesh and China, and 3 to both China and Argentina. Symbolically, we have these three sets:
    $$|A \cap B| = 5, |B \cap C| = 2, |C \cap A| = 3$$

    Subtracting them out leaves only one layer of paint on the above diagram. Are we done?

    Not quite! We painted over the green area in the center 3 times, when we painted over A, B, and C, but now we've removed 3 layers of paint from the intersections, and each of them contain the green area as well! So the rest of our Venn diagram has one layer of paint, but right now the green area has no paint at all. We're given that 1 person has been to all three countries:
    $$|A \cap B \cap C| = 1$$

    So all we need to do to paint back over the center is add 1. Then we have a single layer of paint over everything. Summing it all up, we have \(15 + 10 + 6 - 5 - 2 - 3 + 1 = 22\) total people, which is the correct answer. We found it using the Inclusion-Exclusion formula shown below:

    alt text

    You can think of this as a formula, or you can try to remember it as a guide to proper painting. 🙂

Log in to reply