Transcript Chapter 8 The principle of Inclusion and Exclusion

Chapter 8 The principle of
Inclusion and Exclusion
Yen-Liang Chen
Dept of Information Management
National Central University
8.1 The principle of Inclusion and
Exclusion
N (c1 c2 )  N  [ N (c1 )  N (c2 )  N (c1c2 )]
N (c1c2 )  N (c1 c2 )
N (c1 c2 c3 )  N  [ N (c1 )  N (c2 )  N (c3 )]
 [ N (c1c2 )  N (c1c3 )  N (c2 c3 )]  N (c1c2 c3 )
Four sets
N ( c1 c2 c3 c4 )  N  [ N ( c1 )  N ( c2 )  N ( c3 )  N ( c4 )]
 [ N ( c1c2 )  N ( c1c3 )  N ( c1c4 )  N ( c2 c3 )  N ( c2 c4 )  N ( c3 c4 )]
 [ N ( c1c2 c3 )  N ( c1c2 c4 )  N ( c1c3c4 )  N ( c2 c3c4 )]  N ( c1c2 c3c4 )
For each element x, we have five cases: (0) x satisfies
none of the four conditions; (1) x satisfies only one of
the four conditions; (2) x satisfies exactly two of the four
conditions; (3) x satisfies exactly three of the four
conditions; (4) x satisfies all the four conditions.
Four sets
1.
2.
3.
4.
5.
Say x satisfies no condition. x is counted once on
the left side and once on the right side.
Say x satisfies c1. It is not counted on the left side. It
is counted once in N and once in N(c1).
Say x satisfies c2 and c4. It is not counted on the left
side. It is counted once in N, N(c2), N(c4) and
N(c2c4).
Say x satisfies c1, c2 and c4. It is not counted on the
left side. It is counted once in N, N(c1), N(c2), N(c4),
N(c1c2), N(c1c4), N(c2c4) and N(c1c2c4).
Say x satisfies all conditions. It is not counted on the
left side. It is counted once in all the subsets on the
right side.
N (c1 c2 c3 c4 )
Theorem 8.1.
Symbol Sk
Ex 8.4.
 Determine the number of positive integers n
where n100 and n is not divisible by 2, 3 or 5.
 Condition c1 if n is divisible by 2.
 Condition c2 if n is divisible by 2.
 Condition c3 if n is divisible by 2.
 Then the answer to this problem is
N (c1 c2 c3 ).
Ex 8.5.
 Determine the number of nonnegative integer
solutions to the equation x1+x2+x3+x4=18 and xi7 for
all i.
 We say that a solution x1, x2, x3, x4 satisfies condition
ci if xi>7.
 Then the answer to this problem is N (c c c c ).
1 2 3 4
Ex 8.6.
 For finite sets A, B, where A=mn=B, and
function f: AB, determine the number of
onto functions f.
 Let A={a1, a2,…, am} and B={b1, b2, …, bn}.
 Let ci be the condition that bi is not in the
range of f.
 Then the answer to this problem is
N (c1 c2 ......cn ).
Ex 8.8.
 Let (n) be the number of positive integers m,
where 1m<n and gcd(m, n)=1—that is, m
and n are relatively prime.
e
e
e
e
n

p
p
p
p
 Consider
.
1
2
3
4
 For 1i4, let ci denote that n is divisible by pi.
 Then the answer to this problem is
1
2
3
4
N (c1 c2 c3 c4 ).
Ex 8.9.
 Six married couples are to be seated at a
circular table. In how many ways can they
arrange themselves so that no wife sits next
to her husband?
 For 1i6, let ci denote the condition that
where a seating arrangement has couple i
seated next to each other.
 Then the answer to this problem is
N (c1 c2 ....c6 ).
8.2. Generalizations of the principle
 Em denotes the number of elements in S that
satisfy exactly m of the t conditions.
 E1=N(c1)+N(c2)+N(c3)-2[N(c1c2)+ N(c1c3)+
N(c2c3)]+3N(c1c2c3)
=S1-2S2+3S3
=S1-C(2,1)S2+C(3, 2)S3
 E2=N(c1c2)+N(c1c3)+N(c2c3)-3N(c1c2c3)
=S2-3S3=S2-C(3, 1)S3
 E3=S3
No of conditions =4
 E1=S1-C(2,1)S2+
C(3, 2)S3-C(4, 3)S4
 E2=S2-C(3,1)S3+
C(4, 2)S4
 E3=S3-C(4,1)S4
 E4=S4
Theorem 8.2.
Corollary 8.2.
 Let Lm denotes the number of elements in S that
satisfy at least m of the t conditions.
8.3. Derangements: nothing is in its
right place
 Derangement means that all numbers are in the
wrong positions.
 e-1=1-1+(1/2!)-(1/3!)+(1/4!)-(1/5!)+….. =0.36788
 Ex 8.12. Determine the number of derangements of
1,2,…, 10. Let ci be the condition that integer i is in
the i-th position. d10 can be computed as follows.
The general formula
1 1 1
1
d n  n![1  1     .... ]
2! 3! 4!
n!
d n  n!e
1
Examples
 Ex 8.14. We have seven books and seven
reviewers. Each book needs to be reviewed
by two persons. How many ways can we
assign the referees?



The first week has 7! ways to assign referees.
The second week has d7 ways to assign
referees.
Totally, we have 7!d7 ways of possible
assignments.
8.4. Rook polynomials
 In Fig. 8.6, we want to determine the number
of ways in which k rooks can be placed on
the unshaded squares of this chessboard so
that no two of them can take each other—that
is, no two of them are in the same row or
column of the chessboard. This number is
denoted as rk(C).
3
2
1
5
6
4
Rook polynomials
 In Fig. 8.6, we have r0=1, r1=6, r2=8, r3=2 and
rk=0 for k4.
 r(C, x)=1+6x+8x2+2x3. For each k0, the
coefficient of xk is the number of ways we can
place k nontaking rooks on chessboard C.
disjoint subboards
 In Fig. 8.7, the chessboard contains two disjoint
subboards that have no squares in the same column
or row of C.
 r(C, x)=r(C1, x). r(C2, x).
Multiple disjoint subboards
 In general, if C is a chessboard made up of
pairwise disjoint subboards C1, C2,…, Cn,
then r(C, x)= r(C1, x). r(C2, x)…. r(Cn, x).
Recursive formula
 For a given designated square, (1) we either place
one root here, or (2) we do not use this square.
 rk(C)=rk-1(Cs)+rk(Ce)
 rk(C) xk =rk-1(Cs) xk +rk(Ce) xk for 1kn.
Recursive formula
Apply the recursive formula
8.5. Arrangements with forbidden
positions
 Ex 8.15. The shaded square of RiTj means Ri will not
sit at Tj.
 Determine the number of ways that we can seat
these four relatives on unshaded squares.
 Let S be the total number of ways we can place these
four relatives, one to a table.
 Let ci be the condition that Ri is seated in a forbidden
position but at different tables.
T
T
T
T
T
1
R1
R2
R3
R4
2
3
4
5
Ex 8.15
 Let ri be the number of ways in which it is
possible to place i nontaking rooks on the
shaded chessboard.
 For all 0i4, Si=ri(5-i)!
 R(C, x)=(1+3x+x2)(1+4x+3x2)
=1+7x+16x2+13x3+3x4
N ( c1 c2 c3 c4 )  S 0  S1  S 2  S 3  S 4
 5!7( 4! )  16(3! )  13( 2! )  3(1! )
4
  ( 1) i ri (5  i )!
i 0
Ex 8.16.
 We roll two dice six times, where one is red die and





the other green die.
We know the following pairs did not occur: (1, 2), (2,
1), (2, 5), (3, 4), (4, 1), (4, 5) and (6, 6).
What is the probability that we obtain all six values
both on red die and green die?
One of solutions is like (1, 1), (2, 3), (4, 4), (3, 2), (5,
6), (6, 5).
r(C, x)=(1+4x+2x2)(1+x)3=1+7x+17x2+19x3+10x4+2x5
ci denotes that all six values occur on both the red
and green dies, but i on the red die is paired with one
of the forbidden numbers on the green die
1
2
3
4
5
6
1
1
1
2
2
3
4
4
3
5
5
6
6
5
3
4
2
6
Ex 8.17.
 How many one-to-one
functions from A to B
satisfy none of the
following conditions
shown in Fig. 8.11.
 r(C, x)=
(1+2x)(1+6x+9x2+2x3)
=1+8x+21x2+20x3+4x4
u
1
2
3
4
v
w
x
y
z