Transcript Counting - H-SC

Counting Subsets of a
Set: Combinations
Lecture 28
Section 6.4
Wed, Mar 2, 2005
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
C(n, r) = n!/[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.

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?

Example: Lotto South
In Lotto South (Loot the 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.

Example: Virginia Lottery
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
(it ain’t gonna happen)

Example: Virginia Lottery

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 (forget about it).

Example: Virginia Lottery

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 (nope).

Example: Virginia Lottery

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 (it just might
happen.)

Example: Virginia Lottery

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 (it will happen).

Example: Virginia Lottery

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 (it will happen).

Example: Virginia Lottery

Match 0 of 6 numbers
Player chooses 6 losing numbers.
 Number of ways is C(43, 6) = 2760681.
 Probability is 0.4360 (it will happen).

Example: Virginia Lottery
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.

Example: Virginia Lottery
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.
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.
