文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-tzu Juan
Chapter 8 The Principle of Inclusion
and Exclusion
§ Arrangement with Forbidden
Positions
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
§ Arrangement with Forbidden Positions
Ex :T1 T2 T3 T4 T5 (a) R1 will not sit at T1 or T2.
R1 (b) R2 will not sit at T2.
(c) R will not sit at T or T .
R2 3 3 4
(d) R4 will not sit at T4 or T5.
R3
Sol. (1/2) R4
Let condition ci: Ri in forbidden position.
S = 5!
S1 = N(c1) + N(c2) + N(c3) + N(c4)
= (4! + 4!) + 4! + (4! + 4!) + (4! + 4!) = 7 (4!)
S2: N(c1c2) = 3! N(c1c3) = 3! + 3! + 3! + 3!
: :
S2 = 16 (3!)
(c) Spring 2007, Justie Su-tzu Juan 2
§ Arrangement with Forbidden Positions
T1 T2 T3 T4 T5
Ex : (a) R will not sit at T or T .
R1 1 1 2
(b) R2 will not sit at T2.
R2
(c) R3 will not sit at T3 or T4.
R3
(d) R4 will not sit at T4 or T5.
R4
Sol. (2/2)
7 = r(C, 1)
16 = r(C, 2) C:
0 i 4, Si = ri(5 i)! = r(C, i) (5 i)!
∵ r(C, x) = (1 + 3x + x2)(1 + 4x + 3x2)
= 1 + 7x + 16x2 + 13x3 + 3x4
∴ N(c1c2c3c4) = S0 S1 + S2 S3 + S4
= 5!4 7(4!) + 16(3!) 13(2!) + 3(1!)
i
=(1) ri(5 i)! = 25
i 0
(c) Spring 2007, Justie Su-tzu Juan 3
§ Arrangement with Forbidden Positions
red green
Ex : two dice: one red; other green. (a, b)
row six times.
If (1, 2), (2,1), (2, 5), (3, 4), (4, 1), (4, 5), (6, 6) did not occur,
what’s the probability that we obtain all six values on both dices?
Sol. (1/2)
green
1 2 3 4 5 6 1 5 3 4 2 6
1 1
s(c1) = {2}
2 2
s(c2) = {1, 5}
3 4
s(c3) = {4}
4 3 s(c ) = {1, 5}
5 5 4
6 6 s(c6) = {6}
red
r(C, x) = (1 + 4x + 2x2)(1 + x)3 = 1 + 7x + 17x2 + 19x3 + 10x4 + 2x5
(c) Spring 2007, Justie Su-tzu Juan 4
§ Arrangement with Forbidden P