Transcript Chapter 3 Combinatorics

Chapter 3b
Counting Rules
Permutations
 How
many ways can 5 students in a
class of 30 be assigned to the front
row in the seating chart?
 There are 30 ways to choose the
first. For each of the 30, there are
29 choices for the second. For each
of these pairs, there are 28 choices
for the third, and so on.
 Thus there are 30x29x28x27x26
permutations for the first row.
Permutations
In general, if there are n objects and you
want to select k of them, the number of
arrangements that are possible is
nPk=n(n-1)(n-2)…(n-k+1).
 This deceptively simple idea turns out to
be of great importance .
 First, note that if you constructed a tree
diagram for this problem, this process is
like counting the branches.
 But, constructing tree diagrams for n>5 or
so is not practical.

Permutations
Second, note how this is related to
conditional probability—the choices in the
second step depend on the first, etc.
 Although this rule is for counting
outcomes, it is easy to see that on a tree
diagram we would be labeling the first
generation probabilities 1/n, the second
generation 1/(n-1), etc.
 Thus the probability for any branch is
1
n(n  1)(n  2) (n  k  1)

Factorials
 Suppose
we wanted to find the total
number of ways of arranging 5
objects (5 out of 5).
 There would be 5x4x3x2x1 ways.
 There is a special symbol for this
kind of product:
n!, called n-factorial, is defined as
follows:
n !  n(n  1)(n  2)...(2)(1)
e.g. 5!  5  4  3  2 1  120
0!  1 by definition
Factorials
 Factorials
get huge, fast.
5! =120
10!=3,628,800
20!=2,432,902,008,176,640,000
 Thus we can easily get beyond the
capabilities of ordinary calculators to
deal with these numbers accurately.
 It is very helpful to learn a shortcut
for dividing factorials.
Factorials
 Say
you had 20!/17!.
 Recognize that
20! 20 19 18 17!

 20 19 18  6840
17!
17!
 Use this idea in reverse to find a new
way to write the permutations rule.
30  29  28  27  26  25! 30!
30  29  28  27  26 

25!
25!
n
Pk  n(n  1)(n  2)
n!
(n  k  1) 
(n  k )!
Combinations
 Suppose
now that you want to
choose 5 people from a class of 30 to
be on a committee.
 This is called a combination. In
contrast to a permutation, the order
of objects is not important. In a
permutation, we choose one person
for each distinct position. In a
combination, it is as though we
choose them all at once.
Combinations
For example:
{Bob, Jo, Ann, Judy, Carl} is the same as
{Ann, Judy, Carl, Jo, Bob}.
 The above example lists two of the
permutations of five people. We already
know how many permutations there are,
total. What we need to do is determine
how many permutations are the same,
when order is ignored, then divide by that
number.

Combinations
How many ways are there to order 5
objects? 5! ways. There are 30!/25!
permutations of 5 chosen from the class.
So there are (30!/25!)/5! combinations.
 The symbol for the number of
combinations of k items chosen from n is

n
 
k 
and is read “n choose k” It is also written
as nCk (often on calculators). It is defined
as follows:
n
n!
 
 k  k !(n  k )!
Combinations
 The
formula
n
n!
 
 k  k !(n  k )!
may look complicated, but it is easy
to remember if you think of it this
way: The total goes on top, and the
denominator splits the total into two
groups, number chosen and number
not chosen.
More on Combinations
Combinations can be used to calculate
probabilities for many common problems
like card games.
 Recall the probability definition that said

n( A)
P( A) 
n( S ) .

If we can find the number of combinations
of cards that fit our definition of a
particular “hand,” and divide by the total
number of combinations of cards, we can
calculate probabilities for “hands.”
number of ways of getting hand
P(hand ) 
total number of hands possible
Poker Hands
 First,
what is the total number of
hands possible in poker? (5-card
combinations)
 52  52! 52  51 50  49  48  47!
Totalhands    

5  4  3  2  47!
 5  5!47!
 52  5110  49  2  2,598,960
 This
will be our denominator.
number of ways of getting hand
P(hand ) 
2,598,960
Try a Flush


To figure out the numerator, we can think in
terms of the choices that have to be made to
build the hand.
For a flush, we first have to choose 1 suit out of
4. Given the suit (think tree), we have to choose
5 cards from the 13 in that suit.
 4 13  4! 13! 4 13 12 1110  9
allflushes     

5  4  3 2
 1  5  1!3! 5!8!
 4 13 11 9  5,148
5,148
P(anyflush) 
 .001981
2,598,960
Not All Flushes
 However,
we have to make sure we
have mutually exclusive definitions.
Not all “flushes,” are counted as
flushes. Some are straight flushes
and royal flushes.
 4
royalflushes     4
1
 49
straightflushes       4  9  36
11
Final Results for Flushes
 So
4
P(royalflush) 
 .000002
2,598,960
36
P( straightflush) 
 .000014
2,598,960
5,148  4  36
P( flush) 
 .001965
2,598,960
One Pair

To get one pair (and nothing else) we need to
select a number for the pair, then 3 other,
different numbers for the remaining cards (order
doesn’t matter). However, that is not all. We
must also select suits, two for the pair and 1 for
each of the other cards.
3
13  12   4   4  13 12  11 10  4  3  43
onepairs          
3 2  2
 1  3  21
 13 12  11 10  64  1, 098, 240
1, 098, 240
P(onepair ) 
 .422569
2,598,960
Full House

One more example: To get a full house, you
choose one number for the pair, then two suits
for it, then another number for the triple, and
three suits for it.
13  4 12  4  13 12  4  3  4
fullhouses       
2
 1  2  1  3 
 13 12  4  3  3, 744
3, 744
P( fullhouse) 
 .001441
2,598,960