Transcript Introduction to Coding Theory

Chap 2 Combinatorial Methods
Ghahramani 3rd edition
Outline
2.1 Introduction
2.2 Counting principle
2.3 Permutations
2.4 Combinations
2.5 Stirling’s formula
p2.
2.1 Introduction
•
If the sample space is finite and furthermore
sample points are all equally likely, then
P(A)=N(A)/N(S)
So we study combinatorial analysis here,
which deals with methods of counting.
p3.
2.2 Counting principle


Ex 2.1 How many outcomes are there if we throw 5
dice?
Ex 2.2 In tossing 4 fair dice,
P(at least one 3 among these 4 dice)=?


Ex 2.3 Virginia wants to give her son, Brian, 14
different baseball cards within a 7-day period. If
Virginia gives Brian cards no more than once a day,
in how many way can this be done?
Ex 2.6 (Standard Birthday Problem)
P(at least two among n people have the same
Bday)=?
p4.
Counting principle


Thm 2.3 A set with n elements has 2n subsets.
Ex 2.9 Mark has $4. He decides to bet $1 on the
flip of a fair coin 4 times. What is the probability
that (a) he breaks even; (b) he wins money?(use
tree diagram)
p5.
2.3 Permutations


Ex 2.10 3 people, Brown, Smith, and Jones, must
be scheduled for job interviews. In how many
different orders can this be done?
Ex 2.11 2 anthropology, 4 computer science, 3
statistics, 3 biology, and 5 music books are put on
a bookshelf with a random arrangement. What is
the probability that the books of the same subject
are together?
p6.
Permutations


Ex 2.12 If 5 boys and 5 girls sit in a row in a
random order, P(no two children of the same sex
sit together)=?
Thm 2.4 The number of distinguishable
permutations of n objects of k different types,
where n1 are alike, n2 are alike, …, nk are alike
and n=n1+n2+…+nk is
n!
n1! n2!...nk !
p7.
Permutations


Ex 2.13 How many different 10-letter codes can
be made using 3 a’s, 4 b’s, and 3 c’s?
Ex 2.14 In how many ways can we paint 11
offices so that 4 of them will be painted green,
3 yellow, 2 white, and the remaining 2 pink?

Ex 2.15 A fair coin is flipped 10 times.
P(exactly 3 heads)=?
p8.
2.4 Combinations


Ex 2.16 In how many ways can 2 math and 3
biology books be selected from 8 math and 6
biology books?
Ex 2.17 45 instructors were selected randomly to
ask whether they are happy with their teaching
loads. The response of 32 were negative. If Drs.
Smith, Brown, and Jones were among those
questioned. P(all 3 gave negative responses)=?
p9.
Combinations


Ex 2.18 In a small town, 11 of the 25
schoolteachers are against abortion, 8 are for
abortion, and the rest are indifferent. A random
sample of 5 schoolteachers is selected for an
interview. (a)P(all 5 are for abortion)=? (b)P(all 5
have the same opinion)=?
Ex 2.19 In Maryland’s lottery, player pick 6
integers between 1 and 49, order of selection being
irrelevant.
P(grand prize)=? P(2nd prize)=? P(3rd prize)=?
p10.
Combinations



Ex 2.20 7 cards are drawn from 52 without
replacement.
P(at least one of the cards is a king)=?
Ex 2.21 5 cards are drawn from 52. P(full house)=?
Ex 2.24 A professor wrote n letters and sealed
them in envelopes. P(at least one letter was
addressed correctly)=?
Hint: Let Ei be the event that ith letter is addressed
correctly. Compute P(E1U…UEn) by inclusionexclusion principle.
p11.
Combinations

Thm 2.5 (Binomial expansion)
( x  y )n 


n
 n  n i i
y
 x
i

i 0

Ex 2.25 What is the coefficient of x2y3 in the
expansion of (2x+3y)5?
Ex 2.26 Evaluate the sum
n n n n
n
               .
 0  1   2   3
n
p12.
Combinations

Ex 2.27 Evaluate the sum
n n n
n
   2   3     n .
 1   2  3
n

Ex 2.28 Prove that
n
2
 2n 
n


 n 

i
 .


i 0  

p13.
Combinations

Ex 2.29 Prove the inclusion-exclusion principle.
P( A1  A2  ...  An ) 



 P( Ai )   P( Ai A j )
P( Ai A j Ak )  ...  ( 1)n 1 P( A1A2 ... An )
Ex 2.30 Distribute n distinguishable balls into k
distinguishable cells so that n1 balls are
distributed into the first cell, n2 balls into the
second cell, …, nk balls into the kth cell, where
n1+n2+…+nk=n. How many possible ways?
Sol:
n!
n1! n2!... nk !
p14.
Combinations

Thm 2.6 (Multinomial expansion).
( x1  x2    xk )n 

n1  n2 ... nk n
n!
n
n n
x1 1 x2 2  xk k
n1! n2!...  nk !
p15.
2.5 Stirling’s formula
n! 
n

n
2nn e
p16.