Probability
1.2 More Counting
Alex Tsun
Matthew Taing
Agenda
Mini-Rainbows
How many 3-Color Mini-Rainbows can be made out of 7 available colors?
Mini-Rainbows
How many 3-Color Mini-Rainbows can be made out of 7 available colors?
=
x
x
# possible
Outer Colors
# possible MinI-Rainbows
# possible
Middle Colors
# possible
Inner Colors
Mini-Rainbows
How many 3-Color Mini-Rainbows can be made out of 7 available colors?
7
=
x
x
# possible
Outer Colors
# possible MinI-Rainbows
# possible
Middle Colors
# possible
Inner Colors
Mini-Rainbows
How many 3-Color Mini-Rainbows can be made out of 7 available colors?
7
=
x
x
# possible
Outer Colors
# possible MinI-Rainbows
6
# possible
Middle Colors
# possible
Inner Colors
Mini-Rainbows
How many 3-Color Mini-Rainbows can be made out of 7 available colors?
7
=
x
x
# possible
Outer Colors
# possible MinI-Rainbows
6
5
# possible
Middle Colors
# possible
Inner Colors
Mini-Rainbows
How many 3-Color Mini-Rainbows can be made out of 7 available colors?
7
=
x
x
# possible
Outer Colors
# possible MinI-Rainbows
6
5
210
# possible
Middle Colors
# possible
Inner Colors
A Clever Trick
7 x 6 x 5 =
We are “Picking” 3 out of the 7 available Colors.
A Clever Trick
7 x 6 x 5 =
7 x 6 x 5
We are “Picking” 3 out of the 7 available Colors.
A Clever Trick
7 x 6 x 5 =
7 x 6 x 5 x 4 x 3 x 2 x 1
4 x 3 x 2 x 1
We are “Picking” 3 out of the 7 available Colors.
A Clever Trick
7 x 6 x 5 =
7 x 6 x 5 x 4 x 3 x 2 x 1
4 x 3 x 2 x 1
We are “Picking” 3 out of the 7 available Colors.
= 7!
4!
A Clever Trick
7 x 6 x 5 =
7 x 6 x 5 x 4 x 3 x 2 x 1
4 x 3 x 2 x 1
We are “Picking” 3 out of the 7 available Colors.
= 7!
4!
= 7!
(7-3)!
k-Permutations
If we want to arrange only k out of n distinct objects, the number of ways to do so is
P(n,k) = n x (n-1) x (n-2) x ...x (n-k+1) =
Read as “N pick K”
N!
(n-K)!
Mini-Rainbows Again
A kindergartener smears 3 different colors out of 7 to make a new color. How many smeared colors can she create?
Mini-Rainbows Again
Recall there were 210 mini-rainbows. Look at these particular 3! = 6 mini-rainbows with Blue, Orange, and Red.
Mini-Rainbows Again
Recall there were 210 mini-rainbows. Look at these particular 3! = 6 mini-rainbows with Blue, Orange, and Red.
They all produce the SAME “smeared” color!
Mini-Rainbows Again
Each “smeared” color is counted exactly 3! = 6 times, so we can take our 210 mini-rainbows and divide by 6 to get the answer!
Mini-Rainbows Again
Each “smeared” color is counted exactly 3! = 6 times, so we can take our 210 mini-rainbows and divide by 6 to get the answer!
P(7,3)
3!
=
7!
3!(7-3)!
Combinations/Binomial Coefficients
If we want to select (order doesn’t matter) only k out of n distinct objects, the number of ways to do so is
Read as “N choose K”
P(n,k)
k!
N
k
( )
=
=
n!
k!(N-k)!
C(n,k)
=
Both Acceptable
Symmetry in Binomial Coefficient
Notice
N
k
( )
=
n!
k!(N-k)!
n!
(N-k)!K!
=
( )
N
N- k
=
Symmetry in Binomial Coefficient
Notice
Why??
How??
N
k
( )
=
n!
k!(N-k)!
n!
(N-k)!K!
=
( )
N
N- k
=
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
C(4,1)=4
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
C(4,1)=4
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
C(4,1)=4
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
C(4,1)=4
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
C(4,1)=4
Symmetry in Binomial Coefficient
Consider n=4, K=1. We want to show C(4,1)=C(4,3) intuitively.
C(4,1)=4
C(4,3)=4
Random Picture
anagrams
How many ways can you arrange the letters in “math”?
MATH
anagrams
How many ways can you arrange the letters in “math”?
4! = 24 since they are distinct objects!
MATH
anagrams
How many ways can you arrange the letters in “Poopoo”?
anagrams
How many ways can you arrange the letters in “Poopoo”?
anagrams
How many ways can you arrange the letters in “Poopoo”?
Choose where the 2 P’s go, and then the o’s are set.
anagrams
How many ways can you arrange the letters in “Poopoo”?
Choose where the 2 P’s go, and then the o’s are set. Or
Choose where the 4 O’s go, and then the P’s are set.
anagrams
How many ways can you arrange the letters in “Poopoo”?
Choose where the 2 P’s go, and then the o’s are set. Or
Choose where the 4 O’s go, and then the P’s are set.
Either way, we get C(6,2) x C(4,4) = C(6,4) x C(2,2) =
6!
2!4!
anagrams
How many ways can you arrange the letters in “Poopoo”?
Either way, we get C(6,2) x C(4,4) = C(6,4) x C(2,2) =
Another interpretation:
6!
2!4!
anagrams
How many ways can you arrange the letters in “Poopoo”?
Either way, we get C(6,2) x C(4,4) = C(6,4) x C(2,2) =
Another interpretation:
Arrange the 6 letters as if they were distinct. Then divide by 4! and 2! to account for 4 duplicate O’s and 2 duplicate P’s.
6!
2!4!
Multinomial Coefficients
If we have k types of objects (n total), with n1 of the first type, n2 of the second, …, and nk of the kth, then the number of arrangements possible is
N
n1 , n2 , …, nK
( )
=
N!
n1! n2 ! … nK!
anagrams
How many ways can you arrange the letters in “Godoggy”?
anagrams
How many ways can you arrange the letters in “Godoggy”?
N=7 Letters, K=4 Types {G, O, D, Y}
anagrams
How many ways can you arrange the letters in “Godoggy”?
N=7 Letters, K=4 Types {G, O, D, Y}
n1 = 3, n2 = 2, n3 = 1, n4 = 1
anagrams
How many ways can you arrange the letters in “Godoggy”?
N=7 Letters, K=4 Types {G, O, D, Y}
n1 = 3, n2 = 2, n3 = 1, n4 = 1
7
3, 2, 1, 1
( )
=
7!
3! 2! 1! 1!
Kids + Candies
How many ways can we give 5 (Indistinguishable) candies to These 3 kids?
Kids + Candies
Kids + Candies
Kids + Candies
Kids + Candies
Idea: Count something equivalent.
Kids + Candies
Idea: Count something equivalent.
5 “Stars” for candies, 2 “bars” for dividers
Kids + Candies
Idea: Count something equivalent.
5 “Stars” for candies, 2 “bars” for dividers
Kids + Candies
Idea: Count something equivalent.
5 “Stars” for candies, 2 “bars” for dividers
Kids + Candies
Idea: Count something equivalent.
5 “Stars” for candies, 2 “bars” for dividers
Kids + Candies
for each candy distribution, there is exactly one corresponding way to arrange the stars and bars.
Kids + Candies
for each candy distribution, there is exactly one corresponding way to arrange the stars and bars.
Conversely, for each arrangement of stars and bars, there is exactly one candy distribution it represents.
Kids + Candies
Hence, the number of ways to distribute 5 candies to the 3 kids is the number of arrangements of 5 stars and 2 bars.
Kids + Candies
Hence, the number of ways to distribute 5 candies to the 3 kids is the number of arrangements of 5 stars and 2 bars.
This is simply
7
2
( )
7
5
( )
=
Stars and Bars/Divider method
The number of ways to distribute n indistinguishable balls into k distinguishable bins is
n+(k-1)
n
( )
n+(k-1)
k-1
( )
=
we’ll be counting stars (and bars)