WACEhub

INCLUSION- EXCLUSION PRINCIPLE

ACARA

The inclusion-exclusion principle for the union of two sets and three sets:

determine and use the formulas for finding the number of elements in the union of two and the union of three sets. (ACMSM005)

Given n(A) = 12, n(B) = 10 and n(AB) = 3, then n(AB) = ?

AB

NB The overlap = the intersection of the two sets, notated ABIt can be seen that the overlap is counted twice.

n(AB) = n(A) + n(B) – n(AB)

n(AB) = 12 + 10 – 3

= 19

Similarly, given three intersecting sets, A, B and C we have

n(ABC) = n(A) + n(B) + n(C) – n(AB) – n(AC) – n(BC) + n(ABC)

The overlaps containing two elements each need to be subtracted (three subtractions), but then the overlap that contains all three elements has been subtracted three times and is now not included…so it needs to be added again.

.

This can be seen better using different coloured stripes.

BA

C

If 10 people have a yellow pencil case, 15 people have a red Maths text book, and 20 people are wearing maroon socks, what other information would you need to know to find how many people are in each section of the diagram?

3 people have a yellow pencil case and a red maths text and are wearing maroon socks.

2 people have a yellow pencil case and are wearing maroon socks, 6 people have a yellow pencil case and a red text book and 8 people have a red text book and are wearing maroon socks.

How many people have a yellow pencil case or a red text book or are wearing maroon socks?

ie determine n(ABC).

HINT: n(ABC) = n(A) + n(B) + n(C) – n(AB) – n(AC) – n(BC) + n(ABC)

If 120 people were in the group, how many people do not have either a yellow pencil case, a red text book or are wearing maroon socks?

i.e n() = ?

Solution:

n(ABC) = 10 + 15 + 20 – 2 – 6 – 8 +3 = 32

n() = n(U) – n(ABC) = 120 – 32 = 88

21Label each of the shaded regions in terms of A and B or A, B and C.

BAAB

3

4AB

Solutions:

1. AB 2.

C3. 4.

1. Before you begin the inclusion-exclusion problems, ensure you can identify each of the

following on Venn Diagrams.

(a) A

(b)

(c) AC

(d)

(e) ABC

(f)

2. Shade on the Venn diagrams below

(a) “Belongs to one set only” (b) “Belongs to two sets only”

(c) “Belongs to all three sets” (d) “Belongs to no set”

Solutions :

B AC A A1. (a) (b) (c) (d)

AC

B A B A (e) (f)

C C

ABC

(g) (h)

2 (a) “Belongs to one set only” (b) “Belongs to two sets only”

(c) “Belongs to all three sets” (d) “Belongs to no set”

i.e. Neither A nor B includedn(AB)A and B includedINCLUSION- EXCLUSION PRINCIPLE

Example 1

1. Consider the counting numbers from 1 to 20. n(U) = 20.

Let E be the set of even numbers.

Let M be the set of numbers that are multiples of 5.

(a) How many of the 20 numbers are even or are multiples of 5?

(b) How many of the numbers are neither even nor multiples of 5?

Solution:

(a) Want n(EM)

n(EM) = n(E) + n(M) – n(EM)

n(E) = 10 as E = {2,4,6,8,10,12,14,16,18,20}

n(M) = 4 as M = {5,10,15,20}

n(EM) = 2 as EM = {10,20}

n(EM) = n(E) + n(M) – n(EM)

= 10 + 4 – 2

n(EM) = 12

(b) Want

= n(U) - n(EM)

= 20 – 12

= 8

Example 2

Consider the counting numbers from 1 to 20. n(U) = 20.

Let E be the set of even numbers.

Let T be the set of numbers that are multiples of 3.

Let M be the set of numbers that are multiples of 5.

(a) How many of the 20 numbers are even, or multiples of 3 or are multiples of 5?

(b) How many of the numbers are neither even, nor multiples of 3 nor multiples of 5?

Solution:

(a) Need n(ETM)

n(ETM) = n(E) + n(T) + n(M) – n(ET) – n(EM) – n(TM) + n(ETM)

n(E) = 10, n(T) = 6, n(M) = 4 T = {3, 6, 9, 12, 15, 18}

n(ET) = 3 ET={6,12,18}

n(EM) = 2 EM = {10,20}

n(TM) = 1 TM = {15}

n(ETM) = 0 ETM = (Null set) or { }

n(ETM) = n(E) + n(T) + n(M) – n(ET) – n(EM) – n(TM) + n(ETM)

= 10 + 6 + 4 – 3 – 2 – 1 + 0

= 14

There are 14 numbers that are even or a multiple of 3 or a multiple of 5.

(b)

= n(U) - n(ETM)

= 20 – 14

= 6

Example 3

Consider the counting numbers from 1 to 1 000 i.e. n(U) = 1 000.

(a) How many of the numbers are multiples of 2, multiples of 3 or are multiples of 5?

(b) How many of the numbers are neither multiples of 2, nor multiples of 3 nor multiples of 5?

Solution:

(a) Let A : multiples of 2; B : multiples of 3; and C : multiples of 5

Need n(ABC)

n(ABC)= n(A) + n(B) + n(C) – n(AB) – n(AC) – n(BC) + n(ABC)

n(A) = 500

n(B) = ? 3,6,9,….999 = 3(1,2,3,….333)

n(B) = 333

n(C) = ? 5,10,15,….1000 = 5(1,2,3,….200)

n(C) = 200

n(AB) = n(6) 6,12,18,…..996 = 6(1,2,3,….166)

n(AB) = 166

n(AC) = n(10)

n(AC) = 100

n(BC) = n(15) 15,30,45,……990 = 15(1,2,3,…..66)

n(BC) = 66

n(ABC) = n(30) 30,60,90,….990 = 30(1,2,3, …..33)

n(ABC) = 33

n(ABC) = n(A) + n(B) + n(C) – n(AB) – n(AC) – n(BC) + n(ABC)

= 500 + 333 + 200 – 166 – 100 – 66 + 33

= 734

There are 734 numbers that are a multiple of 2, a multiple of 3, or a multiple of 5.

(b) = n(U) – n(ABC)

= 1000 – 734

= 266

Extension of concept:

Given four sets, A, B, C and D then it follows that

n(ABCD) = n(A) + n(B) + n(C) + n(D)

– n(AB) – n(AC) – n(AD) – n(BC) – n(BD) – n(CD)

+ n(ABC)+ n(ABD)+ n(ACD) + n(BCD) – n(ABCD)

Notice that the number of single terms is 4C1 = 4, double terms is 4C2 = 6, triple terms is 4C3 = 4 and there is one term with 4 elements – 4C4. Explain!

This pattern continues for any number of intersecting sets.

Example 4

Consider the counting numbers from 1 to 1 000 i.e. n(U) = 1 000.

(a) How many of the numbers are multiples of 2, or 3, or 4 or are multiples of 5?

(b) How many of the numbers are neither multiples of 2, nor 3, nor 4 nor 5?

Solution:

Let A : multiples of 2; B : multiples of 3; C : multiples of 4 and D : multiples of 5

Since the set of numbers that are multiples of four are a direct subset of the set of numbers that are a multiple of two, this question has an identical solution to Example 3.

(a) There are 734 numbers that are a multiple of 2,3, 4 or 5 ...result from example 3.

(b) = n(U) - n(ABCD)

= n(U) - n(ABD) ....as 4 is a subset of 2

= 1000 – 734 ...result from example 3

= 266

Example 5

A group of 60 representatives were attending an United Nations meeting. Between them many languages were spoken, but the main three languages spoken were English, French and German.  A headphone that switched between English, French and German was available.

Out of a total of 60 representatives
    30 spoke English,
    18 spoke French,
    26 spoke German,
    9 spoke both English and French,
    16 spoke both English and German,
    8 spoke both French and German,
    1spoke all three languages.

(a) How many spoke at least one language?

(b) How many of the representatives would need a translator for other languages?

Solution:

(a) n(EFG) = n(E) + n(F) + n(G) – n(EF) – n(EG) – n(FG) + n(EFG)

= 30 + 18 + 26 – 9 – 16 – 8 + 1

= 42

(b) = n(U) - n(EFG)

= 60 – 42

= 18

Exercise

Among the 18 students in a lecture theatre, 7 study French, 10 study Italian, and 10 study Chinese. Also, 3 study French and Italian, 4 study French and Chinese, and 5 study Italian and Chinese. One student studied all three languages.

How many of these students study none of the three languages?

ANSWER:

= 18 – (7 + 10 + 10 – 3 – 4 – 5 + 1)

= 18 – 16

= 2

Challenge question

In a club with 40 members, members have different drink preferences: coffee (C), tea (T), coke (K), and lemonade (L).

It is known that 21 drink coffee, 26 drink tea, 19 drink coke, and 17 drink lemonade. Also, 15 drink both coffee and tea, 6 drink coffee and coke, 9 drink coffee and lemonade, 14 drink tea and coke, 10 drink tea and lemonade, and 11 drink coke and lemonade.

It is also known that 6 drink coffee, tea and coke, 5 drink coffee tea and lemonade, 4 drink coffee, coke and lemonade, and 9 drink tea, coke and lemonade. It is also known that 4 people drink all four options.

How many club members drink none of the four drinks available?

HINT:

n(CTKL) = n(C) + n(T) + n(K) + n(L)

– n(CT) – n(CK) – n(CL) – n(TK) – n(TL) – n(KL)

+ n(CTK)+ n(CTL)+ n(CKL) + n(TKL) – n(CTKL)

ANSWER:

n(drink any of the 4)

= 21 + 26 + 19 + 17 – 15 – 6 – 9 – 14 – 10 – 11 + 6 + 5 + 4 + 9 – 4

= 88 – 50

= 38

n (drink none) = 40 – 38 = 2

Example 6

Consider the integers from 1 to 100. Some have repeated digits like 33.

Use the inclusion-exclusion principle to determine the number of integers that do not have repeated digits.

Solution:

Consider the integers 1 to 9 separately. Since there is only one digit, there are no repeats.

Consider the two digit numbers 10 to 99. There are 90 of these.

Let R stand for repeats.

n(R) = 9 as 11, 22, ….99

n(R) = 0 as you can’t have two repeats together with no repeats with only two digits.

n(R) = n(R) + n()– n(R)

90 = 9+ n() - 0

n() = 81

The number of integers from 1 to 100 that do not have repeated digits is: 9 + 81 = 90

(100 itself has a repeat of 00).

NB This problem simplifies down to n(U) – n(R) – 1 = n – 1, but you were asked to use the inclusion-exclusion principle!

Example 7

Consider the integers from 1 to 1000.

Use the inclusion-exclusion principle to determine the number of digits that do not have repeated digits.

Solution:

We have already seen there are 90 integers without repeats from 1 to 99.

Consider the 900 three digit integers from 100 to 999.

There are two digit repeats and three digit repeats.

n(2R3R) = n(2R) + n(3R) – n(2R3R)

NB n(2R3R) = as there can’t be 2 AND 3 digits the same.

n(3R) = 9 111,222,333,…..999 = 111(1,2,3……9)

n(2R) = 9C11 9 3! – 9 = 477

Think: Any non-zero digit, same, different, arrange them, subtract the 011,022, ….099

n(2R3R) = n(2R) + n(3R)– n(2R3R)

= 477 + 9 – 0

= 486 integers from 100 to 999 with repeating digits

the number of integers from 100 to 99 with non-repeating digits = 900 – 486 = 414

Therefore the total number of non repeating digits from 1 to 1000 is 90 + 414 i.e. 504

This is a special case involving mutually exclusive sets.

If A and B are mutually exclusive then n(AB) = n(A) + n(B)

Example 8

Three friends are going to a concert and each has a ticket A1, A2 and A3. They are happy to sit in any of their three allotted seats.

(a) In how many ways can they take their seats?

(b) In how many ways can they each be sitting in the seat not allotted to them?

Solution :

(a) 3! = 6

(b) Need

n(123) = n(1) + n(2) + n(3) – n(12) – n(13) – n(23) + n(123)

but n(12) = 0 n(13) = 0 n(23) = 0 n(123) = 0 WHY?

Two people cannot sit in the same seat

So in this case, n(123) = n(1) + n(2) + n(3)

Consider n(1)

If one person is in the right seat, this can be done in 3 ways. Of the remaining two seats,

they must sit in the wrong seat so there is only one way of doing this.

n(1) = 3

Consider n(2)

If two people are sitting in the right seat, the third one must be as well. There is no way

exactly two people can sit in the correct seat.

n(2) = 0

Consider n(3)

There is exactly one way that three people can sit in the correct seat.

n(1) = 1

n(123) = n(1) + n(2) + n(3)

= 3 + 0 + 1

= 4

There are only two ways that the three people are sitting in a seat not allocated to them.

The previous example can readily be checked using

but this is not using the inclusion-exclusion principle.

A derangement is an arrangement of the elements of a set such that none of the elements appear in their original position.

Challenge question

Four friends are going to a concert and each has a ticket A1, A2, A3 and A4.

(a) In how many ways can they take their seats?

(b) In how many ways can they each be sitting in the seat not allotted to them?

Example 9

There are a set of 3 cards labeled A, B and C. They are shuffled and laid out on the table in a line. The correct position of card A is first etc.

In how many ways can the cards be shuffled and laid out on the table so that at least one card is in the correct position?

Solution

This question is identical to the previous question so the answer is 4.

The number of cards can be extended to any number n for a challenge!

Kindly proofed and extra suggestions by Dr Dennis Ireland and his staff at MLC.

Venn diagrams: