MATH 352 Assignment #2 Solutions
1. Use the Principle of Inclusion/Exclusion to solve each of the following problems:
(a) Find the probability that a permutation of a1 , a1 , a2 , a2 , . . . , an , an will have no identical
symbols consecutive. The first and last positions are not considered to be consecutive.
Solution: Let Ai be the event that the two ai are consecutive. The desired probability
is the probability that none of the events occur, ie.
n
[ n
X
1 − P( Ai ) = 1 − (−1)k−1 Sk .
k=1 k=1
For any i, to calculate P (Ai ), ‘glue’ together the two ai , then permute the object ai ai
m
together with the other 2n − 2 objects: (2n − 1)!/(2!)n−1 ways. Therefore
er as
co
(2n − 1)! (2n)! 2 · (2n − 1)!
eH w
P (Ai ) = n−1
/ n = .
2 2 (2n)!
o.
This gives
rs e 2 · (2n − 1)!
ou urc
S1 = n · .
(2n)!
Using this same method, for any choice of k events,
o
aC s
(2n − k)! (2n)! 2k · (2n − k)!
P (Ai1 Ai2 . . . Aik ) = / = ,
vi y re
2n−k 2n (2n)!
and k
n 2 · (2n − k)!
Sk = · .
ed d
k (2n)!
ar stu
The desired probability is 1 − S1 + S2 − · · · ± Sn .
(b) Suppose each of n sticks is broken into one long and one short part. The 2n parts are
is
then shuffled and rearranged into n pairs from which new sticks are formed. Find the
Th
probabilitiy that
i. the parts will be joined into their original form.
Solution: Label the short parts of the sticks s1 , s2 , . . . , sn , and their corresponding
sh
long parts l1 , l2 , . . . , ln .
There is only one way that all sticks get put back together in their original form,
(2n)!
and the number of different ways to create n pairs from the 2n parts is (2!) n n! , since
This study source was downloaded by 100000827039679 from CourseHero.com on 08-09-2021 13:17:58 GMT -05:00
https://www.coursehero.com/file/5696611/Ass2solns/
1. Use the Principle of Inclusion/Exclusion to solve each of the following problems:
(a) Find the probability that a permutation of a1 , a1 , a2 , a2 , . . . , an , an will have no identical
symbols consecutive. The first and last positions are not considered to be consecutive.
Solution: Let Ai be the event that the two ai are consecutive. The desired probability
is the probability that none of the events occur, ie.
n
[ n
X
1 − P( Ai ) = 1 − (−1)k−1 Sk .
k=1 k=1
For any i, to calculate P (Ai ), ‘glue’ together the two ai , then permute the object ai ai
m
together with the other 2n − 2 objects: (2n − 1)!/(2!)n−1 ways. Therefore
er as
co
(2n − 1)! (2n)! 2 · (2n − 1)!
eH w
P (Ai ) = n−1
/ n = .
2 2 (2n)!
o.
This gives
rs e 2 · (2n − 1)!
ou urc
S1 = n · .
(2n)!
Using this same method, for any choice of k events,
o
aC s
(2n − k)! (2n)! 2k · (2n − k)!
P (Ai1 Ai2 . . . Aik ) = / = ,
vi y re
2n−k 2n (2n)!
and k
n 2 · (2n − k)!
Sk = · .
ed d
k (2n)!
ar stu
The desired probability is 1 − S1 + S2 − · · · ± Sn .
(b) Suppose each of n sticks is broken into one long and one short part. The 2n parts are
is
then shuffled and rearranged into n pairs from which new sticks are formed. Find the
Th
probabilitiy that
i. the parts will be joined into their original form.
Solution: Label the short parts of the sticks s1 , s2 , . . . , sn , and their corresponding
sh
long parts l1 , l2 , . . . , ln .
There is only one way that all sticks get put back together in their original form,
(2n)!
and the number of different ways to create n pairs from the 2n parts is (2!) n n! , since
This study source was downloaded by 100000827039679 from CourseHero.com on 08-09-2021 13:17:58 GMT -05:00
https://www.coursehero.com/file/5696611/Ass2solns/
