[set theory] inclusion exclusion principle (complex example)

Principle of tolerance and exclusion Example

---

24

24

24 personal

Speak English , Japanese , German , French The number of people

13

,

5

,

10

,

9

13, 5, 10, 9

13,5,10,9

At the same time said English Japanese The number of

2

2

2

At the same time said English German The number of

4

4

4

At the same time said English French The number of

4

4

4

At the same time said French German The number of

4

4

4

Japanese speakers Can't French German ;

seek People who speak only one language ? At the same time, I will say English German French People who ?

A single language set :

A

A

A Set means a collection of people who can speak English ,

∣

A

∣

=

13

|A| = 13

∣A∣=13 ;

B

B

B Set represents a collection of people who can speak Japanese ,

∣

B

∣

=

5

|B| = 5

∣B∣=5 ;

C

C

C Set means a collection of people who can speak German ,

∣

C

∣

=

10

|C| = 10

∣C∣=10 ;

D

D

D Set means a collection of people who can speak French ,

∣

D

∣

=

9

|D| = 9

∣D∣=9 ;

Two intersecting sets :

A

∩

B

A \cap B

A∩B The set representation will say English Japanese A collection of people ,

∣

A

∩

B

∣

=

2

|A \cap B| = 2

∣A∩B∣=2 ;

A

∩

C

A \cap C

A∩C The set representation will say English German A collection of people ,

∣

A

∩

C

∣

=

4

|A \cap C| = 4

∣A∩C∣=4 ;

A

∩

D

A \cap D

A∩D The set representation will say English French A collection of people ,

∣

A

∩

D

∣

=

4

|A \cap D| = 4

∣A∩D∣=4 ;

C

∩

D

C \cap D

C∩D The set representation will say German French A collection of people ,

∣

C

∩

D

∣

=

4

|C \cap D| = 4

∣C∩D∣=4 ;

People who can speak Japanese , Neither can speak French , I can't speak German , Description set

B

B

B And assemble

C

,

D

C, D

C,D They don't intersect ;

∣

B

∩

C

∣

=

∣

B

∩

D

∣

=

∣

A

∩

B

∩

C

∣

=

∣

A

∩

B

∩

D

∣

=

∣

B

∩

C

∩

D

∣

=

∣

A

∩

B

∩

C

∩

D

∣

=

0

|B \cap C| = |B \cap D| = |A \cap B \cap C| = |A \cap B \cap D| = |B \cap C \cap D| = |A \cap B \cap C \cap D| = 0

∣B∩C∣=∣B∩D∣=∣A∩B∩C∣=∣A∩B∩D∣=∣B∩C∩D∣=∣A∩B∩C∩D∣=0

The total number is

24

24

24 people :

∣

A

∪

B

∪

C

∪

D

∣

=

24

|A \cup B \cup C \cup D| = 24

∣A∪B∪C∪D∣=24

According to the principle of inclusion and exclusion :

∣

A

∪

B

∪

C

∪

D

∣

=

|A \cup B \cup C \cup D| =

∣A∪B∪C∪D∣=

∣

A

∣

+

∣

B

∣

+

∣

C

∣

+

∣

D

∣

| A | + | B | + | C | + | D |

∣A∣+∣B∣+∣C∣+∣D∣ First add the number of individual sets

−

(

∣

A

∩

B

∣

+

∣

A

∩

C

∣

+

∣

A

∩

D

∣

+

∣

B

∩

C

∣

+

∣

B

∩

D

∣

+

∣

C

∩

D

∣

)

- ( | A \cap B | + | A \cap C | + | A \cap D | + | B \cap C | + | B \cap D | + | C \cap D |)

−(∣A∩B∣+∣A∩C∣+∣A∩D∣+∣B∩C∣+∣B∩D∣+∣C∩D∣) Subtract the number of intersecting elements

+

(

∣

A

∩

B

∩

C

∣

+

∣

A

∩

B

∩

D

∣

+

∣

A

∩

C

∩

D

∣

+

∣

B

∩

C

∩

D

∣

)

+ ( | A \cap B \cap C | + | A \cap B \cap D | + | A \cap C \cap D | + | B \cap C \cap D |)

+(∣A∩B∩C∣+∣A∩B∩D∣+∣A∩C∩D∣+∣B∩C∩D∣) Add the number of three intersecting elements

−

∣

A

∩

B

∩

C

∩

D

∣

- |A \cap B \cap C \cap D|

−∣A∩B∩C∩D∣ subtract The number of elements intersected by four sets

=

24

= 24

=24

Substitute the number of set elements above into :

∣

A

∪

B

∪

C

∪

D

∣

=

|A \cup B \cup C \cup D| =

∣A∪B∪C∪D∣=

13

+

5

+

10

+

9

13 + 5 + 10 + 9

13+5+10+9 First add the number of individual sets

−

(

2

+

4

+

4

+

0

+

0

+

4

)

- ( 2 + 4 + 4 + 0 + 0 + 4 )

−(2+4+4+0+0+4) Subtract the number of intersecting elements

+

(

0

+

0

+

∣

A

∩

C

∩

D

∣

+

0

)

+ ( 0 + 0 + | A \cap C \cap D | + 0 )

+(0+0+∣A∩C∩D∣+0) Add the number of three intersecting elements

−

0

- 0

−0 subtract The number of elements intersected by four sets

=

24

= 24

=24

Obtained after calculation :

37

−

14

+

∣

A

∩

C

∩

D

∣

=

24

37 - 14 + | A \cap C \cap D | = 24

37−14+∣A∩C∩D∣=24

∣

A

∩

C

∩

D

∣

=

1

| A \cap C \cap D | = 1

∣A∩C∩D∣=1

People who can speak English, French and German at the same time

∣

A

∩

C

∩

D

∣

=

1

| A \cap C \cap D | = 1

∣A∩C∩D∣=1 Only

1

1

1 individual ;

Calculate people who only speak English :

∣

A

∣

−

∣

(

B

∪

C

∪

D

)

∩

A

∣

| A | - | ( B \cup C \cup D ) \cap A |

∣A∣−∣(B∪C∪D)∩A∣

=

∣

A

∣

−

∣

(

B

∩

A

)

∪

(

C

∩

A

)

∪

(

D

∩

A

)

∣

= |A| - | (B \cap A) \cup ( C \cap A ) \cup ( D \cap A ) |

=∣A∣−∣(B∩A)∪(C∩A)∪(D∩A)∣

Use the principle of inclusion and exclusion , Calculation

∣

(

B

∩

A

)

∪

(

C

∩

A

)

∪

(

D

∩

A

)

∣

| (B \cap A) \cup ( C \cap A ) \cup ( D \cap A ) |

∣(B∩A)∪(C∩A)∪(D∩A)∣

∣

(

B

∩

A

)

∪

(

C

∩

A

)

∪

(

D

∩

A

)

∣

| (B \cap A) \cup ( C \cap A ) \cup ( D \cap A ) |

∣(B∩A)∪(C∩A)∪(D∩A)∣

=

(

∣

B

∩

A

∣

+

∣

C

∩

A

∣

+

∣

D

∩

A

∣

)

= ( |B \cap A| + |C \cap A| + |D \cap A| )

=(∣B∩A∣+∣C∩A∣+∣D∩A∣)

−

(

∣

A

∩

B

∩

C

∣

+

∣

A

∩

B

∩

D

∣

+

∣

A

∩

C

∩

D

∣

)

- ( | A \cap B \cap C | + | A \cap B \cap D | + | A \cap C \cap D |)

−(∣A∩B∩C∣+∣A∩B∩D∣+∣A∩C∩D∣)

+

(

∣

A

∩

B

∩

C

∩

D

∣

)

+ ( |A \cap B \cap C \cap D| )

+(∣A∩B∩C∩D∣)

=

(

2

+

4

+

4

)

−

(

0

+

0

+

1

)

+

(

0

)

=

9

= ( 2 + 4 + 4) - ( 0 + 0 + 1 ) + ( 0 ) = 9

=(2+4+4)−(0+0+1)+(0)=9

∣

A

∣

−

∣

(

B

∪

C

∪

D

)

∩

A

∣

=

∣

A

∣

−

∣

(

B

∩

A

)

∪

(

C

∩

A

)

∪

(

D

∩

A

)

∣

=

13

−

9

=

4

| A | - | ( B \cup C \cup D ) \cap A |= |A| - | (B \cap A) \cup ( C \cap A ) \cup ( D \cap A ) | = 13 - 9 = 4

∣A∣−∣(B∪C∪D)∩A∣=∣A∣−∣(B∩A)∪(C∩A)∪(D∩A)∣=13−9=4

People who only speak English

4

4

4 individual ;

Follow these steps , To calculate the Other People who only speak Japanese

3

3

3 individual , Just say German People who 3 individual , People who only speak French

2

2

2 individual ;