Transcript Counting Techniques

Advanced Mathematics
Counting Techniques
Addition Rule
Events (tasks) A and B are mutually exclusive
(no common elements/outcomes) and
n(A) = a, n(B) = b

n(A or B) = a + b
In other words there are a + b ways to do A or B.
Example 1
If you are going to have ice cream or pie for dessert,
there are two choices (vanilla or butter pecan) if you
have ice cream, and three choices (apple, cherry, or
blueberry) if you have pie.
Therefore there are 2 + 3 = 5 choices for dessert.
If you are going to choose from one category or
anther category, then you add the number of choices
in each category.
Multiplication Rule
If there are 'a' ways to do event A and then 'b' ways
to do event B, then there are a×b ways to do A and
B.
n(A) = a, n(B) = b

n(A and B) = a  b
Example 2
Let’s entail pie with ice cream on top, i.e., one must
choose a flavour of pie and a flavour of ice cream.
Note that one must first choose a flavour of pie and
then choose a flavour of ice-cream.
Therefore there are 3 × 2 = 6.
When one must make a choice from one category and
a choice from another category, one multiplies the
numbers of choices in the two categories.
Example 3
Customers now have a choice of cheesecake
(chocolate, lemon, raspberry, and strawberry) or pie
(with ice-cream). How many possible desserts are
available to customers (they cannot have both)?
4 + (3 × 2) = 10 possible desserts.
Factorial Notation (n!)
For n as a positive integer, n factorial is
defined by
n! = n(n – 1)(n – 2) … 21
0! = 1
Note that n! can also be written as
n! = n(n – 1)! = n(n – 1)(n – 2)! and so on
Example 4
Find the value of each of the following:
(a) 6!
(b) 1!
(c) 12!/(10!)(2!)
Example 4 (cont'd)
(a) 6! = 654321 = 720
(b) 1! = 1
(c) 12!/(10!)(2!) = 121110!/(10!)(2!) = 66
Exercise 1: 2, 13, 20, 22, 35, 44
Permutations
Permutations refer to the number of ways to
select and arrange r objects from n objects.
Notation: nPr or nPr
There are n choices to select the first object,
(n – 1) choices to select the second object,
and so n(n – 1) to select and arrange the
first two objects, and so on.
n
Pr = n(n – 1)(n – 2) … (n – r + 1)
Permutation (cont'd)
n
Pr  n  (n  1)  ...  (n  r  2)( n  r  1)
n  (n  1)  ...  (n  r  1)  (n  r )  ...  2 1

(n  r )  (n  r  1)  ...  2 1
n!

(n  r )!
Permutation (cont'd)
Note that the order in which the objects appear is
important in permutations.
That means
ABC
ACB
BAC
BCA
CAB
CBA
are all different arrangements for the three objects
Example 5
Find each of the following:
(a)5P0 = 1 (There is only 1 way to select and
arrange 0 object --- do nothing)
(b)5P5 = 5! = 120
(c)5P2 = 5  4 = 20
Example 6
In how many ways can 3 students out of a group of 5
students be seated in a straight line?
The first seat can be filled in 5 ways (any one of 5
students). The second and third seats can be filled in 4
and 3 ways respectively. Using multiplication rule, the
3 seats can be filled in 5  4  3 = 60 ways.
Or using formula: P3 = 5  4  3 = 60
5
Example 7
In how many ways can 4 students out of a group of
15 students be seated in a straight line?
The first seat can be filled in 15 ways (any one of 15
students).The second, third and fourth seats can be
filled in 14, 13 and 12 ways respectively.
So the 4 seats can be filled in
15x14x13x12 = 32760
Or using the formula
15
P4 = 32760
Example 8
(Example 7) Amy and Bob are two students in the
group. What is the probability that they sit next to each
other?
P(Amy and Bob together)
= 213123 / 32760
(why?)
= 1/35
Exercise 2A: 1, 4, 8, 10
Exercise 2B: 3, 7, 10, 15, 18, 20
Combinations
Combinations refer to the number of ways
to select (no arrangements) r objects from n
objects.
n
n
Notation: Cr , nCr, or  
r 
There are n choices to select the first object,
(n – 1) choices to select the second object,
and so
n(n – 1)/2! to choose the first two objects,
and so on.
n
Cr = n(n – 1)(n – 2) … (n – r + 1)/r!
Combination (cont'd)
n
n
C r     n  (n  1)  ...  (n  r  2)( n  r  1) / r!
r 
n!

(n  r )! r!
Combination (cont'd)
Note that the order in which the objects appear is
not important in combinations.
That means
ABC
ACB
BAC
BCA
CAB
CBA
are all considered to be the same.
Example 9
Find each of the following:
(a)5C0 = 1 (There is only 1 way to choose 0 object -- do nothing)
(b)5C5 = 1 (There is only 1 way to choose all
objects)
(c)5C2 = 5  4 / 2! = 10
(d)5C3 = 5  4  3 / 3! = 10
Example 10
Prove that nCr = nCn-r
n
Cn-r = n! / [(n-r)!(n-(n-r))!] = n! / [(n-r)! r!] = nCr
Choose r objects leaves (n – r) objects behind. So
the number of ways to choose r objects from n
unlike objects is the same as the number of ways to
choose (n – r) objects from n.
Example 11
Consider 5 different objects: A, B, C, D and E.
How many ways are there of choosing 2 objects
from these 5 objects.
Example 11 (cont'd)
Listing
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
number of ways = 10
(Note that AB and BA refer to the same combination.)
By formula 5C2 = 5!/(2!3!) = 10
Exercise 3A: 2, 9, 18, 20, 34
Example 12
In the game of Lotto, players are required to selected
6 numbers out of 45 numbers. How many different
groups of 6 numbers can be chosen from 45 numbers?
What is the probability of winning the first division if
the player just plays one game?
Repeat the above calculations for Power Ball Lotto.
(Players select 5 numbers out of 45 and then one
power ball (number) from another set of 45 numbers.)
Example 12 (cont'd)
Tuesday Lotto
45!
45
n  C6 
 8145060
6! 39!
1
P(winning 1st division) 
 1.23 10 7
8145060
Power Ball Lotto :
45!
45
n  C5  45 
 45  54979155
5! 40!
1
8
P(winning 1st division) 
 1.82 10
54979155
Example 13
In a common form of the card game poker, a hand of 5
cards is dealt to each player from a deck of 52 cards.
(a) What is the total number of possible hands?
(b) How many different flush hands (5 cards, all from
1 suit)?
(c) How many full house hands (3 cards of one kind, 2
of another)?
Try some other hands.
Example 13 (cont'd)
 52 
52 !
n ( total )    
 2 598 960
 5  5! 47 !
13 
13!
n (flush )  4     4 
 5148
5! 8!
 5
( why ?)
 4
 4
n (full house )  13    12     3744
3
 2
( why ?)
Note that the above flush hands include royal
flush and straight flush.
Example 14
A committee of 4 is to be formed from a nominated
list of 5 men and 6 women. How many committees
can be formed where there are more women than
men?
Example 14 (cont'd)
more women than men
 (3 women and 1 man) or (4 women)
n(3 W and 1 M) = 6C3  5C1 = 20  5 = 100
n(4 W) = 6C4 = 15
n(more women than men) = 100 + 15 = 115
Example 15
How many 4 digit even numbers greater than 4000
can be formed using the digits 0 to 8 if repetition of
digits is not permitted?
Example 15 (cont'd)
The two requirements that must be looked at first are:
--- numbers greater than 4000 (first digit: 4 to 8) and
--- even numbers (last digit: 0, 2, 4, 6, 8)
So the tasks of choosing the first digit and the last digit
are not mutually exclusive.
Split up the possible numbers into disjoint cases:
--- first digit = 5 or 7 and last digit = 0, 2, 4, 6, 8
--- first digit = 4, 6 or 8 and last digit = remaining 4 even
Example 15 (cont'd)
first digit = 5 or 7 and last digit = 0, 2, 4, 6 or 8
There are 2 ways to choose the first digit and 5 ways
to choose the last digit. So in this case the possible
numbers formed = 2  7  6  5 = 420.
first digit = 4, 6 or 8 and last digit = remaining 4 even
There are 3 ways to choose the first digit and 4 ways
to choose the last digit. So in this case the possible
numbers formed = 3  7  6  4 = 504.
Using addition rule, the required numbers can be
formed in 420 + 504 = 924 ways.
Example 16
In how many ways can the letters of the word
HISTORY be arranged
(a) without restrictions
(b) With the letters I and S together in the order IS
(c) with the letters I and S together
(d) with the letters I and S apart
(e) with the letters T, O and R together?
Example 16 (cont'd)
7
(a) n(without restrictions) = P7 = 7! = 5040
(b) Consider I and S as a single object “IS”. Hence
there are 6 objects to be arranged.
n(“IS” together in this order) = 6! = 720
(c) Now “IS” can be “SI” and there are 2! ways to
arrange the two objects within the group.
n(“IS” together) = 2  720 = 1440
(d) n(I and S apart) = 5040 – 1440 = 3600
(e) 3! ways to arrange T, O and R within the group.
n(“TOR” together) = 3!  5! = 720
Example 17
Three letters are chosen from the word COUNT and
two digits are chosen from the digits 1 to 6. The
chosen letters and digits are then arranged to form 5
character passwords. No letter or digit is used more
than once. Find the total number of passwords that
can be formed.
Example 17 (cont'd)
n(3 letters) = 5C3 = 10
n(2 digits) = 6C2 = 15
There are 10  15 combinations of 3 letters and 2 digits.
These 5 characters can be arranged in 5! ways. Hence
n(possible passwords) = 5!  10  15 = 18000
Example 18
Suppose a group of 5 people is in a room. Find the
probability that at least 2 of the people have the same
birthday.
Same birthday refers to the month and the day, not
necessarily the same year. Also, ignore leap year and
assume that each day in the year is equally likely as a
birthday.
Example 18 (cont'd)
First consider the probability that no 2 people among
5 people have the same birthday.
P(none of the 5 people have the same birthday)
= 365P5 / (365)5
(why?)
 0.973
P(at least 2 of the 5 people do have the same birthday)
= 1 – 0.973
(why?)
= 0.027
Extend the above method for more than 5 people.
How many people is required to make the above
probability at least 0.5?
Exercise 2C: 4, 13, 21, 25, 31
Exercise 2D: 2, 12, 14
Exercise 3B: 2, 10, 15, 21, 37, 39