Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 109

For example,

s 1

∑

i

n(Ai), s 2 =

∑

i<j

n(Ai∩Aj), s 3 =

∑

i 1 <i 2 <i 3

n(Ai 1 ∩Ai 2 ∩Ai 3 )

The Inclusion–Exclusion Principle, which appears in Section 5.7, gave a formula for the number of elements in
the union of the sets. Specifically, (Theorem 5.9) we have

n(A 1 ∪A 2 ∪···∪Ar)=s 1 −s 2 +s 3 −···+(− 1 )r−^1 sr

On the other hand, using DeMorgan’s law,

n(AC 1 ∩AC 2 ∩...∩ACr)=n([A 1 ∪A 2 ∪...∪Ar]C)=|U|−n(A 1 ∪A 2 ∪...∪Ar)

Accordingly, we obtain an alternate form for Theorem 5.9:

Theorem (Inclusion–Exclusion Principle) 6.3: LetA 1 ,A 2 ,...,Arbe subsets of a universal setU. Then the
numbermof elements which do not appear in any of the subsetsA 1 ,A 2 ,...,ArofUis:

m=n(AC 1 ∩AC 2 ∩...∩ACr)=|U|−s 1 +s 2 −s 3 +···+(− 1 )rsr

EXAMPLE 6.3 LetUbe the set of positive integers not exceeding 1000. Then|U|=1000. Find|S|whereSis
the set of such integers which are not divisible by 3, 5, or 7.
LetAbe the subset of integers which are divisible by 3, B which are divisible by 5, andCwhich are divisible
by 7. ThenS=AC∩BC∩CCsince each element ofSis not divisible by 3, 5 or 7. By integer division,

|A|= 1000 / 3 = 33 , |B|= 1000 / 5 = 200 , |C|= 1000 / 7 = 142 ,

|A∩B|= 1000 / 15 = 66 , |A∩C|= 1000 / 21 = 47 , |B∩C|= 1000 / 35 = 28 ,

|A∩B∩C|= 1000 / 105 = 9

Thus, by the Inclusion–Exclusion Principle Theorem 6.3,

|S|= 1000 −( 333 + 200 + 142 )+( 66 + 47 + 28 )− 9 = 1000 − 675 + 141 − 9 = 457

NumberofOnto Functions

LetAandBbe sets such that|A|=6 and|B|=4. We want to find the number of surjective (onto) functions
fromAontoB.
Letb 1 ,b 2 ,b 3 ,b 4 be the four elements inB. LetUbe the set of all functions fromAintoB. Furthermore, let
F 1 be the set of functions which do not send any element ofAintob 1 that is,b 1 is not in the range of any function
inF 1. Similarly, letF 2 ,F 3 , andF 4 be the sets of functions which do not send any element ofAintob 2 ,b 3 , and
b 4 , respectively.
We are looking for the number of functions inS=F 1 C∩F 2 C∩F 3 C∩F 4 C, that is, those functions which do send
at least one element ofAintob 1 , at least one element ofAintob 2 , and so on. We will use the Inclusion–Exclusion
Principle Theorem 6.3 as follows.

(i) For each function inU, there are 4 choices for each of the 6 elements inA; hence|U|= 46 = 4096

(ii) There areC( 4 , 1 )=4 functionsFi. In each case, there are 3 choices for each of the 6 elements inA,

hence|Fi|= 36 =729.

(iii) There areC( 4 , 2 )=6 pairsFi∩Fj. In each case, there are 2 choices for each of the 6 elements inA,

hence|Fi∩Fj|= 26 =64.

(iv) There areC( 4 , 3 )=4 tripletsFi∩Fj∩Fk. In each case, there is only one choice for each of the

6 elements inA. Hence|Fi∩Fj∩Fk|= 16 =1.