Principle of Inclusion and Exclusion

This note has been used to help create the Principle of Inclusion and Exclusion (PIE) wiki

The Principle of Inclusion and Exclusion (PIE) is a way to calculate the number of elements that satisfy at least one of several given properties. If there are two sets, the principle of inclusion and exclusion states

AB=A+BAB. |A \cup B| = |A|+|B| - |A\cap B|.

If there are three sets, the principle of inclusion and exclusion states
ABC=A+B+CABACBC+ABC. |A\cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.

We can verify these statements for ourselves by considering the Venn Diagram of events.

More generally, if A1,A2,An A_1, A_2, \ldots A_n are finite sets, then the principle of inclusion and exclusion states

i=1nAi=i=1nAi1i<jnAiAj+1i<j<knAiAjAk  +(1)n1A1An. \displaystyle \left|\bigcup_{i=1}^n A_i\right| =\sum_{i=1}^n\left|A_i\right| -\sum_{1 \leq i < j \leq n}\left|A_i\cap A_j\right| +\sum_{1\leq i < j < k \leq n}\left|A_i\cap A_j\cap A_k\right| \\-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.

Worked Examples

1. How many integers from 1 to 100 are multiples of 2 or 3?

Solution: Let A A be the set of integers from 1 to 100 that are multiples of 2 (A=50)( \lvert A \rvert = 50). Let B B be the set of integers from 1 to 100 that are multiples of 3 (B=33)( \lvert B \rvert = 33). Now, AB A \cap B is the set of integers from 1 to 100 that are multiples of both 2 and 3, hence are multiples of 6 (AB=16)( \vert A \cap B \rvert = 16 ). By PIE, AB=A+BAB=50+3316=67. | A\cup B| = |A|+|B|-|A\cap B| = 50 + 33 - 16 = 67.

 

2. What is the sum of all integers from 1 to 100 that are multiples of 2 or 3?

Solution: While PIE is often used to count the elements of a set, if we remove the | \cdot | symbols, the statement is still true. For example, in two variables, AB=ABAB A \cup B = A \cup B - A \cap B . The same proof using Venn diagrams works to show that each element is included once. As such, the sum of elements in AB A \cup B is equal to the sum of elements in A A plus the sum of elements in B B minus the sum of elements in AB A\cap B. Letting A A be the set of multiples of 2, and B B be the set of multiples of 3, then AB A \cap B is the set of multiples of 6, hence the sum of AB A \cup B is (2+100)×502+(3+99)×332(6+96)×162=3417. \frac {(2+100)\times 50}{2} + \frac {(3 +99)\times 33}{2} - \frac {(6+96)\times 16}{2} = 3417.

 

3. [Derangements] There are eight guests at a Secret Santa party. Each guest brings a gift and each receives another gift in return. No one is allowed to receive the gift they brought. How many ways are there to distribute the gifts?

Let A A denote the set of ways to distribute gifts such that everyone receives a gift, possibly their own. Let Ai A_i denote the set of ways to distribute gifts such that person i i receives his or her own gift. Then we would like to find

AA1A2A8. |A| - |A_1 \cup A_2 \cup \ldots \cup A_8|.

Since Ai A_i is the set of ways for person ii to receive his/her own gift, there are 7 choices of gifts for the next person, 6 choices of gifts for the following person, and so on. By the rule of product,

Ai=7×6××2×1=7! |A_i|=7\times 6 \times \ldots \times 2 \times 1 = 7!

Since AiAj A_i \cap A_j is the set of ways person ii and person jj both receive their own gifts, there are 6 choices of gifts for the next person, 5 choices of gifts for the following person, and so on. Again by the rule of product,

AiAj=6×4××2×1=6! |A_i \cap A_j| = 6 \times 4 \times \ldots \times 2 \times 1| = 6!

By continuing this argument, if k k people receive their own gifts, then there are (8k)! (8-k)! possible ways. Applying PIE, we obtain

AA1A2A8=8!(81)×7!+(82)×6!+(88)×1!=14833. |A| - |A_1 \cup A_2 \cup \ldots \cup A_8| = 8! - {8 \choose 1} \times 7! + {8\choose 2} \times 6! - \ldots + {8 \choose 8} \times 1! = 14833.

Note: A derangement of n n objects is a permutation of the objects such that none of them stay in the same place. The number of ways this can be done is denoted Dn D_n, and this calculation shows D8=14833 D_8 = 14833.

 

4. We have 7 balls each of different colors (red, orange, yellow, green, blue, indigo, violet) and 3 boxes each of different shapes (tetrahedron, cube, dodecahedron). How many ways are there to place these 7 balls into the 3 boxes such that each box contains at least 1 ball?

Solution: Let X X be the total number of ways we can distribute the balls if there are no restriction. Each ball can be placed into any one of the 3 boxes, so X=37 |X|=3^7. Let T T be the set of ways such that the tetrahedron box has no balls, C C be the set of ways such that the cube box has no balls and D D be the set of ways such that the dodecahedron box has no balls. We would like to find

XTCD. |X| - |T \cup C \cup D|.

We have T=C=D=27 |T| = |C| = |D| = 2^7, since the balls can be placed into one of the two other boxes, and TC=CD=DT=17 |T\cap C | = |C \cap D| = |D \cap T| = 1^7, since all the balls must be placed in the remaining box, and TCD=0 |T\cap C \cap D| = 0. Hence, PIE implies

XTCD=373×27+3×170=1806. |X| - |T \cup C \cup D| = 3^7 - 3 \times 2^7 + 3 \times 1^7 - 0 = 1806.

Note by Arron Kau
5 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

And we write the number of derangements in a closed form as: Dn=n!(111!+12!(1)n1n!)D_n = \displaystyle n! \displaystyle (1 - \displaystyle \frac{1}{1!} + \displaystyle \frac{1}{2!} - \cdots \displaystyle (-1)^n \frac{1}{n!}). Nice post!

A Brilliant Member - 5 years, 4 months ago

Log in to reply

Question-4 is Wrong.............Ans is 15............. a+b+c=7 a+1+b+1+c+1=7 a+b+c=4 so,6C2=15

Ajit Panada - 5 years, 2 months ago

Log in to reply

why is the intersections of A,B,C added at the end?

Nothando Khuzwayo - 5 years, 2 months ago

Log in to reply

To compensate for overcounting.

Shashank Rammoorthy - 4 years, 3 months ago

Log in to reply

There are 4 bins and 20 distinct balls. What is the probability that there is at least one bin that is empty?

Charles N - 5 years ago

Log in to reply

in part 3 Derangements, applying PIE we obtain ...is there something not right with the signs after you open up the bracket?

Venture HI - 5 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...