Transcript Document

Counting Subsets of a
Set: Combinations
Lecture 33
Section 6.4
Tue, Mar 27, 2007
Lotto South
In Lotto South, a player chooses 6
numbers from 1 to 49.
 Then the state chooses at random 6
numbers from 1 to 49.
 The player wins according to how many of
his numbers match the ones the state
chooses.
 See the Lotto South web page.

Lotto South
There are C(49, 6) = 13,983,816 possible
choices.
 Match all 6 numbers

There is only 1 winning combination.
 Probability of winning is
1/13983816 = 0.00000007151.

Lotto South

Match 5 of 6 numbers
There are 6 winning numbers and 43 losing
numbers.
 Player chooses 5 winning numbers and 1
losing numbers.
 Number of ways is C(6, 5)  C(43, 1) = 258.
 Probability is 0.00001845.

Lotto South

Match 4 of 6 numbers
Player chooses 4 winning numbers and 2
losing numbers.
 Number of ways is C(6, 4)  C(43, 2) =
13545.
 Probability is 0.0009686.

Lotto South

Match 3 of 6 numbers
Player chooses 3 winning numbers and 3
losing numbers.
 Number of ways is C(6, 3)  C(43, 3) =
246820.
 Probability is 0.01765.

Lotto South

Match 2 of 6 numbers
Player chooses 2 winning numbers and 4
losing numbers.
 Number of ways is C(6, 2)  C(43, 4) =
1851150.
 Probability is 0.1324.

Lotto South

Match 1 of 6 numbers
Player chooses 1 winning numbers and 5
losing numbers.
 Number of ways is C(6, 1)  C(43, 5) =
3011652.
 Probability is 0.4130.

Lotto South

Match 0 of 6 numbers
Player chooses 6 losing numbers.
 Number of ways is C(43, 6) = 2760681.
 Probability is 0.4360.

Lotto South
Note also that the sum of these integers is
13983816.
 Note also that the lottery pays out a prize
only if the player matches 3 or more
numbers.

Match 3 – win $5.
 Match 4 – win $75.
 Match 5 – win $1000.
 Match 6 – win millions.

Lotto South
Given that a lottery player wins a prize,
what is the probability that he won the $5
prize?
 P(he won $5, given that he won)
= P(match 3)/P(match 3, 4, 5, or 6)
= 0.01765/0.01864
= 0.9469.

Example

Theorem (The Vandermonde convolution):
For all integers n  0 and for all integers r
with 0  r  n,
 r  n  r   n 
 
   

k  0  k  r  k 
r 
r

Proof: See p. 362, Sec. 6.6, Ex. 18.
Another Lottery
In the previous lottery, the probability of
winning a cash prize is 0.018637545.
 Suppose that the prize for matching 2
numbers is… another lottery ticket!
 Then what is the probability of winning a
cash prize?

Lotto South
What is the average prize value of a ticket?
 Multiply each prize value by its probability
and then add up the products:

$10,000,000  0.00000007151 = 0.7151
 $1000  0.00001845 = 0.0185
 $75  0.0009686 = 0.0726
 $5  0.01765 = 0.0883
 $0  0.9814 = 0.0000

Lotto South
The total is $0.8945, or 89.45 cents
(assuming that the big prize is ten million
dollars).
 A ticket costs $1.00.
 How large must the grand prize be to make
the average value of a ticket more than
$1.00?

Another Lottery

What is the average prize value if matching
2 numbers wins another lottery ticket?
Permutations of Sets with
Repeated Elements

Theorem: Suppose a set contains n1
indistinguishable elements of one type, n2
indistinguishable elements of another type,
and so on, through k types, where
n1 + n2 + … + nk = n.
Then the number of (distinguishable)
permutations of the n elements is
n!/(n1!n2!…nk!).
Proof of Theorem

Proof:
Rather than consider permutations per se,
consider the choices of where to put the
different types of element.
 There are C(n, n1) choices of where to
place the elements of the first type.

Proof of Theorem

Proof:
Then there are C(n – n1, n2) choices of
where to place the elements of the second
type.
 Then there are C(n – n1 – n2, n3) choices of
where to place the elements of the third
type.
 And so on.

Proof, continued

Therefore, the total number of choices, and
hence permutations, is
C(n, n1)  C(n – n1, n2)  C(n – n1 – n2, n3)
… C(n – n1 – n2 – … – nk – 1, nk)
= …(some algebra)…
= n!/(n1!n2!…nk!).
Example

How many different numbers can be formed
by permuting the digits of the number
444556?
6!
 60
3!2!1!
Example

How many permutations are there of the
letters in the word MISSISSIPPI?
11!
 34650
4!4!2!1!
How many for VIRGINIA?
 How many for INDIVISIBILITY?

Poker Hands









Two of a kind.
Two pairs.
Three of a kind.
Straight.
Flush.
Full house.
Four of a kind.
Straight flush.
Royal flush.