文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-tzu Juan
Chapter 8 The Principle of Inclusion
and Exclusion
§ The Principle of Inclusion and
Exclusion (2)
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-tzu Juan 1
§ The Principle of Inclusion and Exclusion
Thm : The Principle of Inclusion and Exclusion
N = N(c1c2…ct)
= N [N(c1) + N(c2) + …+ N(ct)]
+ [N(c1c2) + N(c1c3) + …+ N(c1ct) + N(c2c3) + …+ N(ct1ct)]
[N(c1c2c3) + N(c1c2c4) + …+ N(c1c2ct) + N(c1c3c4) + …
+ N(c1c3ct) + …+ N(ct2ct1ct)]
+ …
t
+ (1) N(c1c2…ct) … Eq(1)
t
= N N(ci) +N(cicj) N(cicjck) + …+ (1) N(c1c2…ct)
1it 1ijt 1ijkt … Eq(2)
(c) Spring 2007, Justie Su-tzu Juan 2
§ The Principle of Inclusion and Exclusion
Corollary : The number of elements in S that satisfy at least
one of the condition ci, where 1 i t, is given by
N(c1 or c2 or … or ct) = N N.
Def: S0 = N; S1 =N(ci); S2 =N(cicj); …
1i t 1i jt
t
Sk =  N(ci ci …ci ), 1 k t. (共( k)項)
1i1 i2 ...ik t 1 2 k
Note: By Thm , N = S S + S …+ (1)tS
t 0 1 2 t
k
=(1) Sk
k 0
(c) Spring 2007, Justie Su-tzu Juan 3
§ The Principle of Inclusion and Exclusion
Ex : 1 n 100, n is not divisible by 2, 3, or 5. How many
such n ?
Sol.
Let S = {1, 2, …, 100}, N = 100.
Let condition c1: if n is divisible by 2;
Let condition c2: if n is divisible by 3;
Let condition c3: if n is divisible by 5.
By Thm , N = N(c1c2c3) = N [N(c1) + N(c2) + N(c3)]
+ [N(c1c2) + N(c1c3) + N(c2c3)] N(c1c2c3)
= 100 { 100/2+ 100/3+ 100/5}
+ { 100/6+ 100/10+ 100/15} 100/30
= 26
(c) Spring 2007, Justie Su-tzu Juan 4
§ The Principle of Inclusion and Exclusion
Ex : x1 + x2 + x3 + x4 = 18;
0 xi 7 and xi N; 1 i 4
Sol.
Let condition ci: xi >