CHAPTER 2
Combinatorics and Counting
1
THE MN RULE
Ifan experiment is performed in two stages, with
m ways to accomplish the first stage and n ways to
accomplish the second stage, then there are mn
ways to accomplish the experiment
This rule is easily extended to k stages, with the
number of ways equal to n1 n2 n3 … nk
Example: Flip two coins. The total number of
simple events is: 2×2=4
2
Example: Flip a coin and then Toss a die. The total number of simple events is:
3
EXAMPLES
Example: Toss three coins. The total number of
simple events is:
2×2×2=8
4
EXAMPLES
Example: Toss two dice. The total number of
simple events is: 6 × 6 = 36
5
EXAMPLES
Example: Two M&Ms® are drawn ONE AT A TIME from a dish
containing two red and two blue candies and their colors are
recorded. The total number of simple events is:
4 × 3 = 12
6
EXAMPLES
Example: A truck driver can take three routs from city A to city B, four
from city B to city C and three from city C to city D. When travelling
from City A to D the driver must drive from city A to B to C to D. How
many possible a to D routs are there?
3 × 4 × 3 = 36
7
PERMUTATIONS
Inhow many ways can two books be arranged on a
shelf from a set of 4 different books A, B, C, D .
8
PERMUTATIONS
In how many way can two books be arranged on
a shelf from a set of 4 different books A, B, C, D .
AB, AC, AD, BC, BD, CD
BA, CA, DA, CB, DB, DC
Hence, we can arrange them in 12 different ways
9
FACTORIALS
What is 𝑛! = 𝑟𝑒𝑎𝑑 𝑛 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙
𝒏! = 𝒏 𝒏 − 𝟏 𝒏 − 𝟐 … . (𝟑)(𝟐)(𝟏)
4! =4x3x2x1=24
𝟓! =5x4x3x2x1=120
2! = 𝟐𝒙𝟏 = 𝟐
𝟏! = 𝟏
0! = 𝟏
10
FACTORIALS
Compute
𝟔!
=
𝟑!
𝟏𝟓!
=
𝟏𝟑!
11
PERMUTATIONS
Thenumber of ways you can arrange n distinct
objects, taking them r items at a time is
n!
P =
r
n
( n − r )!
where n!= n( n − 1)( n − 2)...( 2)(1) and 0! 1
ORDER IS IMPORTANT
12
PERMUTATIONS
In how many way can two books be arranged on
a shelf from a set of 4 different books A, B, C, D .
𝟒! 𝟒! 𝟒 ∙ 𝟑 ∙ 𝟐!
𝒑𝟒𝟐 = = = = 𝟏𝟐
𝟒 − 𝟐 ! 𝟐! 𝟐!
13
EXAMPLE
Howmany 3-digit lock combinations can we
make from the numbers 1, 2, 3, and 4?
14
EXAMPLE
How many 3-digit lock combinations can we
make from the numbers 1, 2, 3, and 4?
4!
The order of the choice is P = = 4(3)(2) = 24
3
4
important! 1!
15
PERMUTATIONS
Inhow many ways can a CEO and a vice
president be selected from a group of 4
employees
16
COMBINATIONS
In how many ways can two employees be
selected from a group of 4 employees
17
COMBINATIONS
In how many ways can two employees be
selected from a group of 4 employees
AB, AC, AD, BC, BD, CD
Hence, we can arrange them in 6 different ways
18
COMBINATIONS
The number of distinct combinations of n
distinct objects that can be formed, taking them
r at a time is
n!
C =n
r
r!(n - r )!
ORDER IS NOT IMPORTANT
19
EXAMPLE
A printed circuit board may be purchased from
five suppliers. In how many ways can three
suppliers be chosen from the five?
5! 5(4)(3)(2)1 5(4)
C =
5
3 = = = 10
3!(5 - 3)! 3(2)(1)(2)1 (2)1
The order of the
choice is not
important!
20
EXAMPLE
A box contains six M&Ms®, four red and two green.
A child selects two M&Ms at random. What is the
probability that exactly one is red?
21
EXAMPLE
A box contains six M&Ms®, four red and two green.
A child selects two M&Ms at random. What is the
probability that exactly one is red?
The order of 2!
6! 6(5) C =
2
=2
the choice is C =
6
2 = = 15 1
1!1!
2!4! 2(1)
not important! ways to choose
ways to choose 2 M & Ms
1 green M & M
4!
C =4
1 =4 4 × 2 =8 ways to
1!3! choose 1 red and 1 P(exactly one
ways to choose green M&M red) = 8/15
1 red M & M
22
EXAMPLE
A box contains 5 Bulbs, 2 defective and 3 non-
defective. 3 bulbs are selected, what is the
probability that exactly 2 of the selected three bulbs
are not defective?
23
EXAMPLE
A box contains 5 Bulbs, 2 defective and 3 non-
defective. 3 bulbs are selected, what is the
probability that exactly 2 of the selected three bulbs
are not defective?
The order of 3!
5! (5)(4)(3!) C2 =
3
=3
the choice is C3 = 2!3! = 2(3!) = 10
5
1!2!
not important! ways to choose 3 bulbs from 5 bulbsways to choose
2 nondefective bulbs
2!
C =
1
2
=2 3 × 2 =6 ways to
1!1! choose 2 non- P(2 of the
ways to choose defective and 1 three is
defective nondefective)
1 defective bulb
= 6/10=3/5
24