--- Slide 1 ---
STA257: Probability and Statistics I
Lecture 2
--- Slide 2: Probability ---
Definitions:
Sample points: elementary results of experiment
Sample Space S: collection of all sample points
Event: arbitrary subset of sample space
Probability function P: assing prob to events
1. P(
A
)≥0
2. P(
S
)=1
3. If
A
1
,
A
2
,
A
3
,… are mutually exclusive events
(i.e.
A
i
∩
A
j
=∅ if i≠j), then P(
∪
i=1
∞
A
i
)=
∑
i=1
∞
P(
A
i
)
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaGaaeymaiaab6cacaqGGaGaamiuamaabmaabaGaamyqaaGaayjkaiaawMcaaiabgwMiZkaaicdaaeaacaqGYaGaaeOlaiaabccacaWGqbWaaeWaaeaacaWGtbaacaGLOaGaayzkaaGaeyypa0JaaGymaaqaaiaabodacaqGUaGaaeiiaiaabMeacaqGMbGaaeiiaiaadgeadaWgaaWcbaGaaGymaaqabaGccaGGSaGaamyqamaaBaaaleaacaaIYaaabeaakiaacYcacaWGbbWaaSbaaSqaaiaaiodaaeqaaOGaaiilaiablAciljaabccacaqGHbGaaeOCaiaabwgacaqGGaGaaeyBaiaabwhacaqG0bGaaeyDaiaabggacaqGSbGaaeiBaiaabMhacaqGGaGaaeyzaiaabIhacaqGJbGaaeiBaiaabwhacaqGZbGaaeyAaiaabAhacaqGLbGaaeiiaiaabwgacaqG2bGaaeyzaiaab6gacaqG0bGaae4CaiaabccaaeaacaqGOaGaaeyAaiaab6cacaqGLbGaaeOlaiaabccacaWGbbWaaSbaaSqaaiaadMgaaeqaaOGaeyykICSaamyqamaaBaaaleaacaWGQbaabeaakiabg2da9iabgwGiglaabccacaqGPbGaaeOzaiaabccacaWGPbGaeyiyIKRaamOAaiaabMcacaqGSaGaaeiiaiaabshacaqGObGaaeyzaiaab6gacaqGGaGaamiuamaabmaabaGaeSOkIu1aa0baaSqaaiaadMgacqGH9aqpcaaIXaaabaGaeyOhIukaaOGaamyqamaaBaaaleaacaWGPbaabeaaaOGaayjkaiaawMcaaiabg2da9maaqadabaGaamiuamaabmaabaGaamyqamaaBaaaleaacaWGPbaabeaaaOGaayjkaiaawMcaaaWcbaGaamyAaiabg2da9iaaigdaaeaacqGHEisPa0GaeyyeIuoakiaabccaaaaa@9E8A@
--- Slide 3: Sample Spaces ---
Discrete Sample Space: distinct sample points
Finite {E1,E2,...,En} or countably infinite {E1,E2,E3,...}
Sample point method:
Just assign probs of sample points P(Ei), such that
P(
E
i
)≥0, ∀i &
∑
i
P(
E
i
)
=1
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadcfacaGGOaGaamyramaaBaaaleaacaWGPbaabeaakiaacMcacqGHLjYScaaIWaGaaiilaiaaysW7cqGHaiIicaWGPbGaaGzbVlaacAcacaaMf8+aaabeaeaacaWGqbGaaiikaiaadweadaWgaaWcbaGaamyAaaqabaGccaGGPaaaleaacaWGPbaabeqdcqGHris5aOGaeyypa0JaaGymaaaa@4F10@
Equiprobable sample space: Every sample point has equal prob
(only for finite S)
If S={E1,E2,...,En}, then P(Ei)=1/n for all i=1,...,n
--- Slide 4: Multiplication Rule ---
Multiplication rule: With m elements {a1,...,am} and n
elements {b1,...,bn}, there are m×n possible pairs containing one element from
each group
Example: Sample space for rolling two dice
|
2nd Roll
|
−, 1
|
−, 2
|
−, 3
|
−, 4
|
−, 5
|
−, 6
|
1st Roll
|
1, −
|
1,1
|
1,2
|
1,3
|
1,4
|
1,5
|
1,6
|
2, −
|
2,1
|
2,2
|
2,3
|
2,4
|
2,5
|
2,6
|
3, −
|
3,1
|
3,2
|
3,3
|
3,4
|
3,5
|
3,6
|
4, −
|
4,1
|
4,2
|
4,3
|
4,4
|
4,5
|
4,6
|
5, −
|
5,1
|
5,2
|
5,3
|
5,4
|
5,5
|
5,6
|
6, −
|
6,1
|
6,2
|
6,3
|
6,4
|
6,5
|
6,6
|
--- Slide 5: Example ---
You have 3 shorts, 4 t-shirts, and 2 hats.
How many different outfits can you have?
Solution:
3×4×2=24
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaiodacqGHxdaTcaaI0aGaey41aqRaaGOmaiabg2da9iaaikdacaaI0aaaaa@40E1@
If all outfits are equally likely, what is the probability
of wearing a specific hat tomorrow?
Solution:
Number of outfits for specific hat
3×4=12
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaiodacqGHxdaTcaaI0aGaeyypa0JaaGymaiaaikdaaaa@3E0B@
Probability
12/24=1/2
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaigdacaaIYaGaai4laiaaikdacaaI0aGaeyypa0JaaGymaiaac+cacaaIYaaaaa@3ED0@
--- Slide 6: Example ---
What is the number of sample points for #n coin flips?
Solution:
2×…×2=
2
n
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaikdacqGHxdaTcqWIMaYscqGHxdaTcaaIYaGaeyypa0JaaGOmamaaCaaaleqabaGaamOBaaaaaaa@41A6@
What is the number of sample points for #n die rolls?
Solution:
6×…×6=
6
n
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaiAdacqGHxdaTcqWIMaYscqGHxdaTcaaI2aGaeyypa0JaaGOnamaaCaaaleqabaGaamOBaaaaaaa@41B2@
If S has #n elements, how many different subsets can we
have?
Solution:
Each element can be included or excluded in the subset, so
there are 2 options for each element
2×…×2=
2
n
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaikdacqGHxdaTcqWIMaYscqGHxdaTcaaIYaGaeyypa0JaaGOmamaaCaaaleqabaGaamOBaaaaaaa@41A6@
--- Slide 7: Permutations ---
How many different 4-digit PIN’s are there?
Solution:
10×10×10×10=
10
4
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaigdacaaIWaGaey41aqRaaGymaiaaicdacqGHxdaTcaaIXaGaaGimaiabgEna0kaaigdacaaIWaGaeyypa0JaaGymaiaaicdadaahaaWcbeqaaiaaisdaaaaaaa@477B@
How many different 4-digit PIN’s with unique (non repeated)
digits are there?
Need to use permutations.
Permutation: An ordered arrangement or r objects, chosen
(without repetition) from n possible objects.
--- Slide 8: Permutation Rule ---
Number of permutations (orderings) of r objects, selected
w/o repeats from n objects:
P
r
n
=n⋅(
n−1
)⋅(
n−2
)⋅…⋅(
n−r+1
)
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadcfadaqhaaWcbaGaamOCaaqaaiaad6gaaaGccqGH9aqpcaWGUbGaeyyXIC9aaeWaaeaacaWGUbGaeyOeI0IaaGymaaGaayjkaiaawMcaaiabgwSixpaabmaabaGaamOBaiabgkHiTiaaikdaaiaawIcacaGLPaaacqGHflY1cqWIMaYscqGHflY1daqadaqaaiaad6gacqGHsislcaWGYbGaey4kaSIaaGymaaGaayjkaiaawMcaaaaa@557A@
Ex. Number of 4-digit PIN’s with unique digits
10×9×8×7=5040
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaigdacaaIWaGaey41aqRaaGyoaiabgEna0kaaiIdacqGHxdaTcaaI3aGaeyypa0JaaGynaiaaicdacaaI0aGaaGimaaaa@45F3@
--- Slide 9: Permutation
Rule ---
Factorial function:
n!=n⋅(
n−1
)⋅(
n−2
)⋅…⋅2⋅1
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaad6gacaGGHaGaeyypa0JaamOBaiabgwSixpaabmaabaGaamOBaiabgkHiTiaaigdaaiaawIcacaGLPaaacqGHflY1daqadaqaaiaad6gacqGHsislcaaIYaaacaGLOaGaayzkaaGaeyyXICTaeSOjGSKaeyyXICTaaGOmaiabgwSixlaaigdaaaa@51E0@
Ex.
4!=4×3×2×1=24
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaaisdacaGGHaGaeyypa0JaaGinaiabgEna0kaaiodacqGHxdaTcaaIYaGaey41aqRaaGymaiabg2da9iaaikdacaaI0aaaaa@461C@
Defined for any n≥0, by convention 0!=1
Permutation formula with factorials:
P
r
n
=
n!
(
n−r
)!
, where 0≤r≤n
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadcfadaqhaaWcbaGaamOCaaqaaiaad6gaaaGccqGH9aqpdaWcaaqaaiaad6gacaGGHaaabaWaaeWaaeaacaWGUbGaeyOeI0IaamOCaaGaayjkaiaawMcaaiaacgcaaaGaaiilaiaaywW7caqG3bGaaeiAaiaabwgacaqGYbGaaeyzaiaabccacaaIWaGaeyizImQaamOCaiabgsMiJkaad6gaaaa@503D@
--- Slide 10: Example ---
In Scrabble you get 7 (different) letters
What is the max # of 4-letter words can you make?
Solution:
P
4
7
=
7!
(
7−4
)!
=
7!
3!
=
7×6×⋯×2×1
3×2×1
=7×6×5×4=840
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadcfadaqhaaWcbaGaaGinaaqaaiaaiEdaaaGccqGH9aqpdaWcaaqaaiaaiEdacaGGHaaabaWaaeWaaeaacaaI3aGaeyOeI0IaaGinaaGaayjkaiaawMcaaiaacgcaaaGaeyypa0ZaaSaaaeaacaaI3aGaaiyiaaqaaiaaiodacaGGHaaaaiabg2da9maalaaabaGaaG4naiabgEna0kaaiAdacqGHxdaTcqWIVlctcqGHxdaTcaaIYaGaey41aqRaaGymaaqaaiaaiodacqGHxdaTcaaIYaGaey41aqRaaGymaaaacqGH9aqpcaaI3aGaey41aqRaaGOnaiabgEna0kaaiwdacqGHxdaTcaaI0aGaeyypa0JaaGioaiaaisdacaaIWaaaaa@67BE@
What is the max # of 7-letter words can you make?
Solution:
P
7
7
=
7!
(
7−7
)!
=
7!
0!
=7!=7×6×⋯×2×1=5040
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadcfadaqhaaWcbaGaaG4naaqaaiaaiEdaaaGccqGH9aqpdaWcaaqaaiaaiEdacaGGHaaabaWaaeWaaeaacaaI3aGaeyOeI0IaaG4naaGaayjkaiaawMcaaiaacgcaaaGaeyypa0ZaaSaaaeaacaaI3aGaaiyiaaqaaiaaicdacaGGHaaaaiabg2da9iaaiEdacaGGHaGaeyypa0JaaG4naiabgEna0kaaiAdacqGHxdaTcqWIVlctcqGHxdaTcaaIYaGaey41aqRaaGymaiabg2da9iaaiwdacaaIWaGaaGinaiaaicdaaaa@5A28@
What is the max # of 7-letter words can you create using the
English alphabet?
Solution:
there are 26 letters ⇒
26
7
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaabshacaqGObGaaeyzaiaabkhacaqGLbGaaeiiaiaabggacaqGYbGaaeyzaiaabccacaaIYaGaaGOnaiaabccacaqGSbGaaeyzaiaabshacaqG0bGaaeyzaiaabkhacaqGZbGaaeiiaiabgkDiElaaikdacaaI2aWaaWbaaSqabeaacaaI3aaaaaaa@4ECB@
--- Slide 11: Example ---
You have 2 physics, 3 math, and 4 stats books that you
randomly arrange on your shelf. What is the probability that books of the same
subject are all in a row?
Solution:
number of ways to arrange 9 books=
P
9
9
=9!=362880
number of ways to arrange 3 subject blocks of books =
P
3
3
=3!=6
number of ways to arrange 3 math books within math block=
P
3
3
=3!=6
number of ways to arrange 2 physics books within physics block=
P
2
2
=2!=2
number of ways to arrange 4 stat books within stat block=
P
4
4
=4!=24
Probability that books of same subject are all in row =
6×6×2×24
362880
=
1728
362880
=0.00476
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeiDaiaab+gacaqGGaGaaeyyaiaabkhacaqGYbGaaeyyaiaab6gacaqGNbGaaeyzaiaabccacaqG5aGaaeiiaiaabkgacaqGVbGaae4BaiaabUgacaqGZbGaeyypa0JaamiuamaaDaaaleaacaaI5aaabaGaaGyoaaaakiabg2da9iaaiMdacaGGHaGaeyypa0JaaG4maiaaiAdacaaIYaGaaGioaiaaiIdacaaIWaaabaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeiDaiaab+gacaqGGaGaaeyyaiaabkhacaqGYbGaaeyyaiaab6gacaqGNbGaaeyzaiaabccacaqGZaGaaeiiaiaabohacaqG1bGaaeOyaiaabQgacaqGLbGaae4yaiaabshacaqGGaGaaeOyaiaabYgacaqGVbGaae4yaiaabUgacaqGZbGaaeiiaiaab+gacaqGMbGaaeiiaiaabkgacaqGVbGaae4BaiaabUgacaqGZbGaaeiiaiabg2da9iaabccacaWGqbWaa0baaSqaaiaaiodaaeaacaaIZaaaaOGaeyypa0JaaG4maiaacgcacqGH9aqpcaaI2aaabaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeiDaiaab+gacaqGGaGaaeyyaiaabkhacaqGYbGaaeyyaiaab6gacaqGNbGaaeyzaiaabccacaqGZaGaaeiiaiaab2gacaqGHbGaaeiDaiaabIgacaqGGaGaaeOyaiaab+gacaqGVbGaae4AaiaabohacaqGGaGaae4DaiaabMgacaqG0bGaaeiAaiaabMgacaqGUbGaaeiiaiaab2gacaqGHbGaaeiDaiaabIgacaqGGaGaaeOyaiaabYgacaqGVbGaae4yaiaabUgacqGH9aqpcaqGGaGaamiuamaaDaaaleaacaaIZaaabaGaaG4maaaakiabg2da9iaaiodacaGGHaGaeyypa0JaaGOnaaqaaiaab6gacaqG1bGaaeyBaiaabkgacaqGLbGaaeOCaiaabccacaqGVbGaaeOzaiaabccacaqG3bGaaeyyaiaabMhacaqGZbGaaeiiaiaabshacaqGVbGaaeiiaiaabggacaqGYbGaaeOCaiaabggacaqGUbGaae4zaiaabwgacaqGGaGaaeOmaiaabccacaqGWbGaaeiAaiaabMhacaqGZbGaaeyAaiaabogacaqGZbGaaeiiaiaabkgacaqGVbGaae4BaiaabUgacaqGZbGaaeiiaiaabEhacaqGPbGaaeiDaiaabIgacaqGPbGaaeOBaiaabccacaqGWbGaaeiAaiaabMhacaqGZbGaaeyAaiaabogacaqGZbGaaeiiaiaabkgacaqGSbGaae4BaiaabogacaqGRbGaeyypa0JaaeiiaiaadcfadaqhaaWcbaGaaGOmaaqaaiaaikdaaaGccqGH9aqpcaaIYaGaaiyiaiabg2da9iaaikdaaeaacaqGUbGaaeyDaiaab2gacaqGIbGaaeyzaiaabkhacaqGGaGaae4BaiaabAgacaqGGaGaae4DaiaabggacaqG5bGaae4CaiaabccacaqG0bGaae4BaiaabccacaqGHbGaaeOCaiaabkhacaqGHbGaaeOBaiaabEgacaqGLbGaaeiiaiaabsdacaqGGaGaae4CaiaabshacaqGHbGaaeiDaiaabccacaqGIbGaae4Baiaab+gacaqGRbGaae4CaiaabccacaqG3bGaaeyAaiaabshacaqGObGaaeyAaiaab6gacaqGGaGaae4CaiaabshacaqGHbGaaeiDaiaabccacaqGIbGaaeiBaiaab+gacaqGJbGaae4Aaiabg2da9iaabccacaWGqbWaa0baaSqaaiaaisdaaeaacaaI0aaaaOGaeyypa0JaaGinaiaacgcacqGH9aqpcaaIYaGaaGinaaqaaiaabcfacaqGYbGaae4BaiaabkgacaqGHbGaaeOyaiaabMgacaqGSbGaaeyAaiaabshacaqG5bGaaeiiaiaabshacaqGObGaaeyyaiaabshacaqGGaGaaeOyaiaab+gacaqGVbGaae4AaiaabohacaqGGaGaae4BaiaabAgacaqGGaGaae4CaiaabggacaqGTbGaaeyzaiaabccacaqGZbGaaeyDaiaabkgacaqGQbGaaeyzaiaabogacaqG0bGaaeiiaiaabggacaqGYbGaaeyzaiaabccacaqGHbGaaeiBaiaabYgacaqGGaGaaeyAaiaab6gacaqGGaGaaeOCaiaab+gacaqG3bGaaeiiaiabg2da9maalaaabaGaaGOnaiabgEna0kaaiAdacqGHxdaTcaaIYaGaey41aqRaaGOmaiaaisdaaeaacaaIZaGaaGOnaiaaikdacaaI4aGaaGioaiaaicdaaaGaeyypa0ZaaSaaaeaacaaIXaGaaG4naiaaikdacaaI4aaabaGaaG4maiaaiAdacaaIYaGaaGioaiaaiIdacaaIWaaaaiabg2da9iaaicdacaGGUaGaaGimaiaaicdacaaI0aGaaG4naiaaiAdaaaaa@9670@
--- Slide 12: Combination Rule ---
In Lotto you pick 6 numbers from 1-49. How many different
tickets are there?
In this case order does not matter
Combination: Collection of r objects chosen (without
repetition) from n possible objects
Number of combinations of r objects, selected w/o repeats
from n objects:
C
r
n
=(
n
r
)=
P
r
n
r!
=
n!
r!(
n−r
)!
, where 0≤r≤n
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadoeadaqhaaWcbaGaamOCaaqaaiaad6gaaaGccqGH9aqpdaqadaqaauaabeqaceaaaeaacaWGUbaabaGaamOCaaaaaiaawIcacaGLPaaacqGH9aqpdaWcaaqaaiaadcfadaqhaaWcbaGaamOCaaqaaiaad6gaaaaakeaacaWGYbGaaiyiaaaacqGH9aqpdaWcaaqaaiaad6gacaGGHaaabaGaamOCaiaacgcadaqadaqaaiaad6gacqGHsislcaWGYbaacaGLOaGaayzkaaGaaiyiaaaacaGGSaGaaGzbVlaabEhacaqGObGaaeyzaiaabkhacaqGLbGaaeiiaiaaicdacqGHKjYOcaWGYbGaeyizImQaamOBaaaa@5BFA@
--- Slide 13: Example ---
Proof of
P
r
n
=
C
r
n
⋅r!
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadcfadaqhaaWcbaGaamOCaaqaaiaad6gaaaGccqGH9aqpcaWGdbWaa0baaSqaaiaadkhaaeaacaWGUbaaaOGaeyyXICTaamOCaiaacgcaaaa@42C6@
number of ways to select r out of n=
C
r
n
number of ways to arrange these r=r!
number of ways to arrange r out of n=
P
r
n
⇒
P
r
n
=
C
r
n
×r!
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeiDaiaab+gacaqGGaGaae4CaiaabwgacaqGSbGaaeyzaiaabogacaqG0bGaaeiiaiaadkhacaqGGaGaae4BaiaabwhacaqG0bGaaeiiaiaab+gacaqGMbGaaeiiaiaad6gacqGH9aqpcaWGdbWaa0baaSqaaiaadkhaaeaacaWGUbaaaaGcbaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeiDaiaab+gacaqGGaGaaeyyaiaabkhacaqGYbGaaeyyaiaab6gacaqGNbGaaeyzaiaabccacaqG0bGaaeiAaiaabwgacaqGZbGaaeyzaiaabccacaWGYbGaeyypa0JaamOCaiaacgcaaeaacaqGUbGaaeyDaiaab2gacaqGIbGaaeyzaiaabkhacaqGGaGaae4BaiaabAgacaqGGaGaae4DaiaabggacaqG5bGaae4CaiaabccacaqG0bGaae4BaiaabccacaqGHbGaaeOCaiaabkhacaqGHbGaaeOBaiaabEgacaqGLbGaaeiiaiaadkhacaqGGaGaae4BaiaabwhacaqG0bGaaeiiaiaab+gacaqGMbGaaeiiaiaad6gacqGH9aqpcaWGqbWaa0baaSqaaiaadkhaaeaacaWGUbaaaaGcbaGaeyO0H4TaamiuamaaDaaaleaacaWGYbaabaGaamOBaaaakiabg2da9iaadoeadaqhaaWcbaGaamOCaaqaaiaad6gaaaGccqGHxdaTcaWGYbGaaiyiaaaaaa@AA7D@
Number of Lotto tickets (49 choose 6)
C
6
49
=
49!
6!(
49−6
)!
=
49!
6!43!
=…=13,983,816
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadoeadaqhaaWcbaGaaGOnaaqaaiaaisdacaaI5aaaaOGaeyypa0ZaaSaaaeaacaaI0aGaaGyoaiaacgcaaeaacaaI2aGaaiyiamaabmaabaGaaGinaiaaiMdacqGHsislcaaI2aaacaGLOaGaayzkaaGaaiyiaaaacqGH9aqpdaWcaaqaaiaaisdacaaI5aGaaiyiaaqaaiaaiAdacaGGHaGaaGinaiaaiodacaGGHaaaaiabg2da9iablAciljabg2da9iaaigdacaaIZaGaaiilaiaaiMdacaaI4aGaaG4maiaacYcacaaI4aGaaGymaiaaiAdaaaa@567F@
--- Slide 14: Example ---
A standard deck has 52 cards: 4 suits (♠, ♣, ♥,
�
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaKqzagaeaaaaaaaaa8qacqWI9=VBaaa@3C06@
) × 13 ranks
(A,2,3,...,9,10,J,Q,K)
How many poker hands (5-card comb.) are there?
Solution:
C
5
52
=
52!
5!47!
=2,598,960
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaaiaadoeadaqhaaWcbaGaaGynaaqaaiaaiwdacaaIYaaaaOGaeyypa0ZaaSaaaeaacaaI1aGaaGOmaiaacgcaaeaacaaI1aGaaiyiaiaaisdacaaI3aGaaiyiaaaacqGH9aqpcaaIYaGaaiilaiaaiwdacaaI5aGaaGioaiaacYcacaaI5aGaaGOnaiaaicdaaaa@4996@
What is the probability of being dealt a “full house” (i.e.
3 cards of one rank and 2 cards of another)?
Solution:
number of ways for triple =13×(
4
3
)
(13 ways for rank, and combinations of 3 out of 4 for suit)
number of ways for pair =12×(
4
2
)
(12 remaining ways for rank, and combinations of 2 out of 4 for suit)
number of ways for "full house" =13×(
4
3
)×12×(
4
2
)=3,744
Probability of "full house"=
3,744
2,598,960
=0.00144
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeOzaiaab+gacaqGYbGaaeiiaiaabshacaqGYbGaaeyAaiaabchacaqGSbGaaeyzaiaabccacqGH9aqpcaaIXaGaaG4maiabgEna0oaabmaabaqbaeqabiqaaaqaaiaaisdaaeaacaaIZaaaaaGaayjkaiaawMcaaaqaaiaabIcacaqGXaGaae4maiaabccacaqG3bGaaeyyaiaabMhacaqGZbGaaeiiaiaabAgacaqGVbGaaeOCaiaabccacaqGYbGaaeyyaiaab6gacaqGRbGaaeilaiaabccacaqGHbGaaeOBaiaabsgacaqGGaGaae4yaiaab+gacaqGTbGaaeOyaiaabMgacaqGUbGaaeyyaiaabshacaqGPbGaae4Baiaab6gacaqGZbGaaeiiaiaab+gacaqGMbGaaeiiaiaabodacaqGGaGaae4BaiaabwhacaqG0bGaaeiiaiaab+gacaqGMbGaaeiiaiaabsdacaqGGaGaaeOzaiaab+gacaqGYbGaaeiiaiaabohacaqG1bGaaeyAaiaabshacaqGPaaabaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeOzaiaab+gacaqGYbGaaeiiaiaabchacaqGHbGaaeyAaiaabkhacaqGGaGaeyypa0JaaGymaiaaikdacqGHxdaTdaqadaqaauaabeqaceaaaeaacaaI0aaabaGaaGOmaaaaaiaawIcacaGLPaaaaeaacaqGOaGaaeymaiaabkdacaqGGaGaaeOCaiaabwgacaqGTbGaaeyyaiaabMgacaqGUbGaaeyAaiaab6gacaqGNbGaaeiiaiaabEhacaqGHbGaaeyEaiaabohacaqGGaGaaeOzaiaab+gacaqGYbGaaeiiaiaabkhacaqGHbGaaeOBaiaabUgacaqGSaGaaeiiaiaabggacaqGUbGaaeizaiaabccacaqGJbGaae4Baiaab2gacaqGIbGaaeyAaiaab6gacaqGHbGaaeiDaiaabMgacaqGVbGaaeOBaiaabohacaqGGaGaae4BaiaabAgacaqGGaGaaeOmaiaabccacaqGVbGaaeyDaiaabshacaqGGaGaae4BaiaabAgacaqGGaGaaeinaiaabccacaqGMbGaae4BaiaabkhacaqGGaGaae4CaiaabwhacaqGPbGaaeiDaiaabMcaaeaacaqGUbGaaeyDaiaab2gacaqGIbGaaeyzaiaabkhacaqGGaGaae4BaiaabAgacaqGGaGaae4DaiaabggacaqG5bGaae4CaiaabccacaqGMbGaae4BaiaabkhacaqGGaGaaeOiaiaabAgacaqG1bGaaeiBaiaabYgacaqGGaGaaeiAaiaab+gacaqG1bGaae4CaiaabwgacaqGIaGaaeiiaiabg2da9iaaigdacaaIZaGaey41aq7aaeWaaeaafaqabeGabaaabaGaaGinaaqaaiaaiodaaaaacaGLOaGaayzkaaGaey41aqRaaGymaiaaikdacqGHxdaTdaqadaqaauaabeqaceaaaeaacaaI0aaabaGaaGOmaaaaaiaawIcacaGLPaaacqGH9aqpcaaIZaGaaiilaiaaiEdacaaI0aGaaeinaaqaaiaabcfacaqGYbGaae4BaiaabkgacaqGHbGaaeOyaiaabMgacaqGSbGaaeyAaiaabshacaqG5bGaaeiiaiaab+gacaqGMbGaaeiiaiaabkcacaqGMbGaaeyDaiaabYgacaqGSbGaaeiiaiaabIgacaqGVbGaaeyDaiaabohacaqGLbGaaeOiaiabg2da9maalaaabaGaaG4maiaacYcacaaI3aGaaGinaiaaisdaaeaacaaIYaGaaiilaiaaiwdacaaI5aGaaGioaiaacYcacaaI5aGaaGOnaiaaicdaaaGaeyypa0JaaGimaiaac6cacaaIWaGaaGimaiaaigdacaaI0aGaaGinaaaaaa@39DC@
--- Slide 15: Example ---
A committee of 5 is randomly selected from a group of 20
people, to vote on a proposal. If only 4 out of the 20 are in favor of the
proposal, what is the prob it will pass?
Solution:
total number of possible committees=(
20
5
)=15,504
Numebr of committees in favor:
3/5 in favor =(
4
3
)×(
16
2
)=480
4/5 in favor =(
4
4
)×(
16
1
)=1×16=16
Probability proposal will pass =
480+16
15,504
MathType@MTEF@5@5@+=feaaguart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaGaaeiDaiaab+gacaqG0bGaaeyyaiaabYgacaqGGaGaaeOBaiaabwhacaqGTbGaaeOyaiaabwgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabchacaqGVbGaae4CaiaabohacaqGPbGaaeOyaiaabYgacaqGLbGaaeiiaiaabogacaqGVbGaaeyBaiaab2gacaqGPbGaaeiDaiaabshacaqGLbGaaeyzaiaabohacqGH9aqpdaqadaqaauaabeqaceaaaeaacaaIYaGaaGimaaqaaiaaiwdaaaaacaGLOaGaayzkaaGaeyypa0JaaGymaiaaiwdacaGGSaGaaGynaiaaicdacaaI0aaabaGaaeOtaiaabwhacaqGTbGaaeyzaiaabkgacaqGYbGaaeiiaiaab+gacaqGMbGaaeiiaiaabogacaqGVbGaaeyBaiaab2gacaqGPbGaaeiDaiaabshacaqGLbGaaeyzaiaabohacaqGGaGaaeyAaiaab6gacaqGGaGaaeOzaiaabggacaqG2bGaae4BaiaabkhacaqG6aaabaGaae4maiaab+cacaqG1aGaaeiiaiaabMgacaqGUbGaaeiiaiaabAgacaqGHbGaaeODaiaab+gacaqGYbGaaeiiaiabg2da9maabmaabaqbaeqabiqaaaqaaiaaisdaaeaacaaIZaaaaaGaayjkaiaawMcaaiabgEna0oaabmaabaqbaeqabiqaaaqaaiaaigdacaaI2aaabaGaaGOmaaaaaiaawIcacaGLPaaacqGH9aqpcaaI0aGaaGioaiaaicdaaeaacaqG0aGaae4laiaabwdacaqGGaGaaeyAaiaab6gacaqGGaGaaeOzaiaabggacaqG2bGaae4BaiaabkhacaqGGaGaeyypa0ZaaeWaaeaafaqabeGabaaabaGaaGinaaqaaiaaisdaaaaacaGLOaGaayzkaaGaey41aq7aaeWaaeaafaqabeGabaaabaGaaGymaiaaiAdaaeaacaaIXaaaaaGaayjkaiaawMcaaiabg2da9iaaigdacqGHxdaTcaaIXaGaaGOnaiabg2da9iaaigdacaaI2aaabaGaaeiuaiaabkhacaqGVbGaaeOyaiaabggacaqGIbGaaeyAaiaabYgacaqGPbGaaeiDaiaabMhacaqGGaGaaeiCaiaabkhacaqGVbGaaeiCaiaab+gacaqGZbGaaeyyaiaabYgacaqGGaGaae4DaiaabMgacaqGSbGaaeiBaiaabccacaqGWbGaaeyyaiaabohacaqGZbGaaeiiaiabg2da9maalaaabaGaaGinaiaaiIdacaaIWaGaey4kaSIaaGymaiaaiAdaaeaacaaIXaGaaGynaiaacYcacaaI1aGaaGimaiaaisdaaaaaaaa@D641@
--- Slide 16: Binomial Theorem ---
(
x+y
)
n
=
∑
i=0
n
(
n
i
)⋅
x
i
⋅
y
n−i
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaamaabmaabaGaamiEaiabgUcaRiaadMhaaiaawIcacaGLPaaadaahaaWcbeqaaiaad6gaaaGccqGH9aqpdaaeWaqaamaabmaabaqbaeqabiqaaaqaaiaad6gaaeaacaWGPbaaaaGaayjkaiaawMcaaiabgwSixlaadIhadaahaaWcbeqaaiaadMgaaaGccqGHflY1caWG5bWaaWbaaSqabeaacaWGUbGaeyOeI0IaamyAaaaaaeaacaWGPbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoaaaa@524F@
Quick facts on binomial coefficients
(
n
0
)=(
n
n
)=1 and (
n
1
)=(
n
n−1
)=n
(
n
r
)=(
n
n−r
)
∑
r=0
n
(
n
r
)
=
2
n
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaWaaeWaaeaafaqabeGabaaabaGaamOBaaqaaiaaicdaaaaacaGLOaGaayzkaaGaeyypa0ZaaeWaaeaafaqabeGabaaabaGaamOBaaqaaiaad6gaaaaacaGLOaGaayzkaaGaeyypa0JaaGymaiaabccacaqGGaGaaeyyaiaab6gacaqGKbGaaeiiaiaabccacaqGGaWaaeWaaeaafaqabeGabaaabaGaamOBaaqaaiaaigdaaaaacaGLOaGaayzkaaGaeyypa0ZaaeWaaeaafaqabeGabaaabaGaamOBaaqaaiaad6gacqGHsislcaaIXaaaaaGaayjkaiaawMcaaiabg2da9iaad6gaaeaadaqadaqaauaabeqaceaaaeaacaWGUbaabaGaamOCaaaaaiaawIcacaGLPaaacqGH9aqpdaqadaqaauaabeqaceaaaeaacaWGUbaabaGaamOBaiabgkHiTiaadkhaaaaacaGLOaGaayzkaaaabaWaaabmaeaadaqadaqaauaabeqaceaaaeaacaWGUbaabaGaamOCaaaaaiaawIcacaGLPaaaaSqaaiaadkhacqGH9aqpcaaIWaaabaGaamOBaaqdcqGHris5aOGaeyypa0JaaGOmamaaCaaaleqabaGaamOBaaaaaaaa@68D9@
Proof of
∑
r=0
n
(
n
r
)
=
2
n
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOqaamaaqadabaWaaeWaaeaafaqabeGabaaabaGaamOBaaqaaiaadkhaaaaacaGLOaGaayzkaaaaleaacaWGYbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiabg2da9iaaikdadaahaaWcbeqaaiaad6gaaaaaaa@4413@
using binomial theorem
Let x=y=1
(
x+y
)
n
=
∑
r=0
n
(
n
r
)
x
r
y
n−r
⇒
(
1+1
)
n
=
∑
r=0
n
(
n
r
)
1
r
1
n−r
⇒
∑
r=0
n
(
n
r
)=
2
n
MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbbjxAHXgaruavP1wzZbItLDhis9wBH5garmWu51MyVXgaruWqVvNCPvMCG4uz3bqee0evGueE0jxyaibaieYlf9irVeeu0dXdh9vqqj=hEeeu0xXdbba9frFj0=OqFfea0dXdd9vqaq=JfrVkFHe9pgea0dXdar=Jb9hs0dXdbPYxe9vr0=vr0=vqpWqaaiaaciWacmaadaGabiaaeaGaauaaaOabaeqabaGaaeitaiaabwgacaqG0bGaaeiiaiaadIhacqGH9aqpcaWG5bGaeyypa0JaaGymaaqaamaabmaabaGaamiEaiabgUcaRiaadMhaaiaawIcacaGLPaaadaahaaWcbeqaaiaad6gaaaGccqGH9aqpdaaeWaqaamaabmaabaqbaeqabiqaaaqaaiaad6gaaeaacaWGYbaaaaGaayjkaiaawMcaaiaadIhadaahaaWcbeqaaiaadkhaaaGccaWG5bWaaWbaaSqabeaacaWGUbGaeyOeI0IaamOCaaaaaeaacaWGYbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiabgkDiEpaabmaabaGaaGymaiabgUcaRiaaigdaaiaawIcacaGLPaaadaahaaWcbeqaaiaad6gaaaGccqGH9aqpdaaeWaqaamaabmaabaqbaeqabiqaaaqaaiaad6gaaeaacaWGYbaaaaGaayjkaiaawMcaaiaaigdadaahaaWcbeqaaiaadkhaaaGccaaIXaWaaWbaaSqabeaacaWGUbGaeyOeI0IaamOCaaaaaeaacaWGYbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoakiabgkDiEpaaqadabaWaaeWaaeaafaqabeGabaaabaGaamOBaaqaaiaadkhaaaaacaGLOaGaayzkaaGaeyypa0JaaGOmamaaCaaaleqabaGaamOBaaaaaeaacaWGYbGaeyypa0JaaGimaaqaaiaad6gaa0GaeyyeIuoaaaaa@7BA4@