PART 1 MODULE 5
FACTORIALS, PERMUTATIONS AND COMBINATIONS
n! "n factorial"
If nis a positive integer, then n!is nmultiplied by all of the smaller positive integers.
Also, 0! = 1
0! = 1
1! = 1
2! = (2)(1) = 2
3! = (3)(2)(1) = 6
4! = (4)(3)(2)(1) = 24
5! = (5)(4)(3)(2)(1) = 120
6! = (6)(5)(4)(3)(2)(1) = 720
7! = (7)(6)(5)(4)(3)(2)(1) = 5,040
8! = (8)(7)(6)(5)(4)(3)(2)(1) = 40,320
9! = (9)(8)(7)(6)(5)(4)(3)(2)(1) = 362,880
10! = (10)(9)(8)(7)(6)(5)(4)(3)(2)(1) = 3,628,800
n! is n multiplied by all of the positive integers smaller than n.
FACT:
n! is the number of different ways to arrange (permutations of) n objects.
EXAMPLE 1.5.1
There are four candidates for a job. The members of the search committee will rank the
four candidates from strongest to weakest. How many different outcomes are possible?
EXAMPLE 1.5.1 SOLUTION
If you were to use the Fundamental Counting Principle, you would need to make four
dependent decisions.
1. Choose strongest candidate: 4 options
2. Choose second-strongest candidate: 3 options
3. Choose third-strongest candidate: 2 options
4. Choose weakest candidate: 1 option
(4)(3)(2)(1) = 24
A shorter way to get this answer is to recognize that the problem is asking us to find the
number of ways to arrange (according to relative sutability for the job) four people. By
definition, the number of ways to arrange 4 things is 4!
4! = 24
,EXAMPLE 1.5.2
In how many ways is it possible for 15 students to arrange themselves among 15 seats in
the front row of an auditorium?
EXAMPLE 1.5.3
There are 8 greyhounds in a race. How many different orders of finish (first place through
eighth place) are possible?
EXAMPLE 1.5.4
1. The password for Gomer's e-mail account consists of 5 characters chosen from the set
{g, o, m, e, r} . How many arrangements are possible, if the password has no repeated
characters?
2. How many 5-character passwords are possible if a password may have repeated
characters?
, EXAMPLE 1.5.5
Gomer has a 20 volume set of World Book Encyclopedia. The 20 volumes are arranged
in numerical order. His uncle Aristotle has challenged him to write down every possible
arrangement of the 20 books. Aristotle will pay Gomer $10,000 if he can compete the job
within 30 days. The only proviso is that if Gomer doesn't complete the job within 30
days, he will have to pay Aristotle 1 penny for every permutation that he has failed to list.
1. How many different arrangements are there?
2. Gomer is a fast worker. Assuming that he can write down 1 million arrangements per
second, how long will it take for him to complete the job?
EXAMPLE 1.5.6
Refer to the situation in the previous example.
Use the fundamental counting principle to answer this question:
If Gomer is going to choose 9 of the 20 books, and arrange them on a shelf, how many
arrangements are possible?
EXAMPLE 1.5.6 SOLUTION
We can't directly use n! to solve this problem, because in this case he is not arranging the
entire set of 20 books. At this point, we must use the Fundamental Counting Principle.
Gomer has to make 9 dependent decisions:
1. Choose first book: 20 options
2. Choose second book: 19 options
3. Choose third book: 18 options
4. Choose fourth book: 17 options
5. Choose fifth book: 16 options
6. Choose sixth book : 15 options
7. Choose seventh book: 14 options
8. Choose eighth book: 13 options
8. Choose ninth book: 12 options
According to the Fundamental Counting Principle, the number of different outcomes
possible is
(20)(19)(18)(17)(16)(15)(14)(13)(12) = 60,949,324,800 arrangements
There is another way to get the answer to this question, without having to enter nine
numbers into the calculator. It refers to a special formula involving n!:
FACTORIALS, PERMUTATIONS AND COMBINATIONS
n! "n factorial"
If nis a positive integer, then n!is nmultiplied by all of the smaller positive integers.
Also, 0! = 1
0! = 1
1! = 1
2! = (2)(1) = 2
3! = (3)(2)(1) = 6
4! = (4)(3)(2)(1) = 24
5! = (5)(4)(3)(2)(1) = 120
6! = (6)(5)(4)(3)(2)(1) = 720
7! = (7)(6)(5)(4)(3)(2)(1) = 5,040
8! = (8)(7)(6)(5)(4)(3)(2)(1) = 40,320
9! = (9)(8)(7)(6)(5)(4)(3)(2)(1) = 362,880
10! = (10)(9)(8)(7)(6)(5)(4)(3)(2)(1) = 3,628,800
n! is n multiplied by all of the positive integers smaller than n.
FACT:
n! is the number of different ways to arrange (permutations of) n objects.
EXAMPLE 1.5.1
There are four candidates for a job. The members of the search committee will rank the
four candidates from strongest to weakest. How many different outcomes are possible?
EXAMPLE 1.5.1 SOLUTION
If you were to use the Fundamental Counting Principle, you would need to make four
dependent decisions.
1. Choose strongest candidate: 4 options
2. Choose second-strongest candidate: 3 options
3. Choose third-strongest candidate: 2 options
4. Choose weakest candidate: 1 option
(4)(3)(2)(1) = 24
A shorter way to get this answer is to recognize that the problem is asking us to find the
number of ways to arrange (according to relative sutability for the job) four people. By
definition, the number of ways to arrange 4 things is 4!
4! = 24
,EXAMPLE 1.5.2
In how many ways is it possible for 15 students to arrange themselves among 15 seats in
the front row of an auditorium?
EXAMPLE 1.5.3
There are 8 greyhounds in a race. How many different orders of finish (first place through
eighth place) are possible?
EXAMPLE 1.5.4
1. The password for Gomer's e-mail account consists of 5 characters chosen from the set
{g, o, m, e, r} . How many arrangements are possible, if the password has no repeated
characters?
2. How many 5-character passwords are possible if a password may have repeated
characters?
, EXAMPLE 1.5.5
Gomer has a 20 volume set of World Book Encyclopedia. The 20 volumes are arranged
in numerical order. His uncle Aristotle has challenged him to write down every possible
arrangement of the 20 books. Aristotle will pay Gomer $10,000 if he can compete the job
within 30 days. The only proviso is that if Gomer doesn't complete the job within 30
days, he will have to pay Aristotle 1 penny for every permutation that he has failed to list.
1. How many different arrangements are there?
2. Gomer is a fast worker. Assuming that he can write down 1 million arrangements per
second, how long will it take for him to complete the job?
EXAMPLE 1.5.6
Refer to the situation in the previous example.
Use the fundamental counting principle to answer this question:
If Gomer is going to choose 9 of the 20 books, and arrange them on a shelf, how many
arrangements are possible?
EXAMPLE 1.5.6 SOLUTION
We can't directly use n! to solve this problem, because in this case he is not arranging the
entire set of 20 books. At this point, we must use the Fundamental Counting Principle.
Gomer has to make 9 dependent decisions:
1. Choose first book: 20 options
2. Choose second book: 19 options
3. Choose third book: 18 options
4. Choose fourth book: 17 options
5. Choose fifth book: 16 options
6. Choose sixth book : 15 options
7. Choose seventh book: 14 options
8. Choose eighth book: 13 options
8. Choose ninth book: 12 options
According to the Fundamental Counting Principle, the number of different outcomes
possible is
(20)(19)(18)(17)(16)(15)(14)(13)(12) = 60,949,324,800 arrangements
There is another way to get the answer to this question, without having to enter nine
numbers into the calculator. It refers to a special formula involving n!:
