Transcript Combinations with Repetition: Distributions

2. Combinatorial Methods
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.
p2.
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)=?

p3.
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)
p4.
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?
p5.
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 !
p6.
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)=?
p7.
2.4 Combinations
Definition
An unordered arrangement of r objects from a set A containing n
objects (r  n) is called an r-element combination of A, or a
combination of the elements of A taken r at a time.
Notes：
 n
n!
n
C r    
 r  r!(n  r )!
P  r!C
n
r
n
r
 n  1  n   n 
       
 r   r   r  1
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)=?
p11.
Combinations with Repetition:
Distributions
E.g. 7個人買食物,有四種食物可選擇,有幾種買法?
10!  4  7  1


7!3! 
7

first
xxx
xx
second
third
fourth
for x
xxxx
x
xxxx
x
for
xxx
xxx
p12.
Combinations with Repetition:
Distributions
In general, the number of selections, with repetitions, of r
objects from n distinct objects are:
( n  r  1)!  n  r  1


r 
r !( n  1)! 
p13.
Combinations with Repetition:
Distributions
E.g. Determine all integer solutions to the equation
x1  x2  x3  x4  7, where xi  0 for all
1  i  4.
select with repetition from x1 , x 2 , x 3 , x 4 7 times
For example, if x1 is selected twice, then x1  2
in the final solution. Therefore, C(4+7-1,7)=120
p14.
Combinations with Repetition:
Distributions
Equivalence of the following:
(a) the number of integer solutions of the equation
x1  x2    xn  r , xi  0, 1  i  n
(b) the number of selections, with repetition, of size r from a collection
of size n
(c) the number of ways r identical objects can be distributed among
n distinct containers
p15.
Combinations with Repetition:
Distributions
E.g. How many nonnegative integer solutions are there to
the inequality x1  x 2  x 6  10 ?
It is equivalent to
x1  x2    x6  x7  10, 0  xi , 1  i  6, 0  x7
which can be transformed to y1  y 2  y 6  y 7  9,
where y i  x i fo 1  i  6
y 7  x 7  1r
an
C(7+9d
1,9)=5005
p16.
Combinations with Repetition:
Distributions
E.g. How many terms there are in the expansion of
( w  x  y  z) 10 ?
Each distinct term is of the form
10

 n1 n2 n3 n4

 w x y z , where 0  n i for
 n1 , n 2 , n 3 , n 4 
1  i  4, and n1  n 2  n 3  n 4  10.
Therefore, C(4+10-1,10)=286
p17.
For Theorem
any integer2.5
n ：
0, Binomial Expansion
 n  ni i
( x  y )    x y .
i 0  i 
n
Pf：
n
p18.
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
p19.
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 0  i 

p20.
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 !
p21.