Transcript Counting Subsets of a Set

Counting Subsets of a
Set: Combinations
Lecture 28
Section 6.4
Thu, Mar 30, 2006
r-Combinations
An r-combination of a set of n elements is a
subset of r of the n elements.
 The order of the elements does not matter.
 The 3-combinations of the set {a, b, c, d, e}
are
{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d},
{a, c, e}, {a, d, e}, {b, c, d}, {b, c, e},
{b, d, e}, {c, d, e}.

Counting r-Combinations

Theorem: The number of r-combinations of
a set of n elements is
n!
C (n, r ) 
r!(n  r )!

Examples:
C(4, 2) = (4  3)/(2  1) = 6.
 C(10, 3) = (10  9  8)/(3  2  1) = 120.
 C(1000, 2) = (1000  999)/(2  1) = 499500.

Some Useful Facts
C(n, 0) = 1 for all n  0.
 C(n, 1) = n for all n  1.
 Notice that C(n, r) = C(n, n – r).
 For example,



C(100, 99) = C(100, 1) = 100/1 = 100.
Therefore,
C(n, n) = 1 for all n  0.
 C(n, n – 1) = n for all n  1.

Another Useful Fact

The TI-83 will calculate C(n, r).
Enter n.
 Select MATH > PRB > nCr.
 Enter r.
 Press ENTER.
 The value of C(n, r) appears.

Counting r-Combinations
Proof (by induction on n).
 Base case:

Let n = 0. Then r = 0 and there is only one
0-combination, the null set.
 Also, 0!/(0!0!) = 1.
 So the statement is true when n = 0.

Counting r-Combinations

General case:
Suppose that the statement is true when n =
k, for some integer k  0.
 Consider a set of k + 1 elements.
 If r = 0, then there is only one 0-combination,
the null set, and (k + 1)!/(0!(k + 1)!) = 1.
 If r = k + 1, then there is only one kcombination, the entire set, and
(k + 1)!/((k + 1)!0!) = 1.

Counting r-Combinations
So let r be any number between 0 and k + 1
(0 < r < k + 1).
 Select an arbitrary element a from the set.
 For each r-combination of the k + 1
elements, a is either a member or not a
member.
 We will count the r-combinations for which
a is a member and then count the rcombinations for which a is not a member.

Counting r-Combinations

r-combinations for which a is not a member:
• The r elements come from the remaining k
elements.
• Therefore, by the inductive hypothesis, there
are k!/(r!(k – r)!) such sets.

r-combinations for which a is a member:
• The other r – 1 elements in the subset come
from the k remaining elements in the set.
• By the inductive hypothesis, there are
k!/((r – 1)!(k – (r – 1))!) such sets.
Counting r-Combinations

Therefore, the number of r-combinations of k
+ 1 elements is
n!
n!

r!(n  r )! (r  1)!(n  (r  1))!

A little algebra shows that this equals
(n  1)!
r!(( n  1)  r )!

Thus, the statement is true when n = k + 1,
etc.
Example: Counting rCombinations
In Math 121, I used to collect 48 daily
homework assignments.
 Some assignments count more than
others.
 I drop the “lowest” 4 homework grades.
 Which should be dropped: 0 out of 30 or
15 out of 40?
 I drop the 4 grades that hurt the student’s
average the most.

Example: Counting rCombinations
How can that be determined?
 Can a computer program make the
determination by brute force (exhaustive
checking) within a reasonable amount of
time?
 There are C(48, 4) = 194,580 possible
choices.
 A computer can do the math really fast, in
say one second.

Example: Counting rCombinations
What if I dropped 6 grades?
 There would be C(48, 6) = 12,271,512
possible choices.
 Over 60 times as many.
 This would require about 60 secs = 1 min.

Example: Counting rCombinations
What if I dropped 12 grades?
 There would be C(48, 12) = over 69 billion
choices!
 More than 350,000 as many!
 This would require almost 350,000 sec =
over 4 days.

Example: Counting rCombinations
What if I dropped 44 grades!!!???
 This must involve unimaginably many
possibilities!
 How many would it be?

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!/(3!2!1!) = 720/(6  2  1) = 60.

Example
How many permutations are there of the
letters in the word MISSISSIPPI?
 11!/(4!4!2!1!) = 34650.
 How many for VIRGINIA?
 How many for INDIVISIBILITY?
