(C,A,B,D), (C,A,D,B), (C,B,A,D), (C,B,D,A), (C,D,A,B), (C,D,B,A)
24
(D,A,B,C), (D,A,C,B), (D,B,A,C), (D,B,C,A), (D,C,A,B), (D,C,B,A)
..
.
.
.
.
..
..
..
For n > 0, the number that appears in the last column can be computed
using the multiplication principle. The number of non-repetitive lists of
length n that can be made from n symbols is n(n−1)(n−2) · · · 3·2·1. Thus, for
instance, the number in the last column of the row for n = 4 is 4·3·2·1 = 24.
The number that appears in the last column of Row n is called the
factorial of n. It is denoted as n! (read “n factorial”). Here is the definition:
Definition 3.1
If n is a non-negative integer, then the factorial of n,
denoted n!, is the number of non-repetitive lists of length n that can
be made from n symbols.
Thus 0! = 1 and 1! = 1.
If n > 1, then n! =
n(n − 1)(n − 2)···3 · 2 · 1.
Factorials
71
It follows that
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, and so on.
Students are often tempted to say 0! = 0, but this is wrong. The correct
value is 0! = 1, as the above definition and table tell us. Here is another
way to see that 0! must equal 1: Notice that 5! = 5 · 4 · 3 · 2 · 1 = 5 · (4 · 3 · 2 · 1) =
5 · 4!. Also 4! = 4 · 3 · 2 · 1 = 4 · (3 · 2 · 1) = 4 · 3!. Generalizing this reasoning, we
have the following formula.
n! = n · (n − 1)!
(3.1)
Plugging in n = 1 gives 1! = 1·(1−1)! = 1·0!, that is, 1! = 1·0!. If we mistakenly
thought 0! were 0, this would give the incorrect result 1! = 0.
We round out our discussion of factorials with an example.
Example 3.3
This problem involves making lists of length seven from
the symbols 0, 1, 2, 3, 4, 5 and 6.
(a) How many such lists are there if repetition is not allowed?
(b) How many such lists are there if repetition is not allowed and the
first three entries must be odd?
(c) How many such lists are there in which repetition is allowed, and
the list must contain at least one repeated number?
To answer the first question, note that there are seven symbols, so the
number of lists is 7! = 5040. To answer the second question, notice that
©
the set 0, 1, 2, 3, 4, 5, 6ª contains three odd numbers and four even numbers.
Thus in making the list the first three entries must be filled by odd numbers
and the final four must be filled with even numbers. By the multiplication
principle, the number of such lists is 3 · 2 · 1 · 4 · 3 · 2 · 1 = 3!4! = 144.
To answer the third question, notice that there are 77 = 823, 543 lists
in which repetition is allowed. The set of all such lists includes lists
that are non-repetitive (e.g., (0, 6, 1, 2, 4, 3, 5)) as well as lists that have
some repetition (e.g., (6, 3, 6, 2, 0, 0, 0)). We want to compute the number of
lists that have at least one repeated number. To find the answer we can
subtract the number of non-repetitive lists of length seven from the total
number of possible lists of length seven. Therefore the answer is 77 − 7! =
823, 543 − 5040 = 818, 503.
72
Counting
We close this section with a formula that combines the ideas of the first
and second sections of the present chapter. One of the main problems of
Section 3.1 was as follows: Given n symbols, how many non-repetitive lists
of length k can be made from the n symbols? We learned how to apply the
multiplication principle to obtain the answer
n(n − 1)(n − 2)···(n − k + 1).
Notice that by cancellation this value can also be written as
n(n − 1)(n − 2)···(n − k + 1)(n − k)(n − k − 1)···3 · 2 · 1
n!
=
.
(n − k)(n − k − 1)···3 · 2 · 1
(n − k)!
We summarize this as follows:
Fact 3.2
The number of non-repetitive lists of length k whose entries
n!
are chosen from a set of n possible entries is (n−k)! .
For example, consider finding the number of non-repetitive lists of
length five that can be made from the symbols 1, 2, 3, 4, 5, 6, 7, 8. We will do
this two ways. By the multiplication principle, the answer is 8 · 7 · 6 · 5 · 4 =
6720.
8!
40,320
Using the formula from Fact 3.2, the answer is (8−5)! = 8!
3! =
6
=
6720.
The new formula isn’t really necessary, but it is a nice repackaging of
an old idea and will prove convenient in the next section.
Exercises for Section 3.2
1. What is the smallest n for which n! has more than 10 digits?
2. For which values of n does n! have n or fewer digits?
3. How many 5-digit positive integers are there in which there are no repeated
digits and all digits are odd?
4.
100!
Using only pencil and paper, find the value of 95! .
5.
120!
Using only pencil and paper, find the value of 118! .
6. There are two 0’s at the end of 10! = 3,628,800. Using only pencil and paper,
determine how many 0’s are at the end of the number 100!.
7. Compute how many 9-digit numbers can be made from the digits 1,2,3,4,5,6,7,8,9
if repetition is not allowed and all the odd digits occur first (on the left) followed
by all the even digits (i.e. as in 137598264, but not 123456789).
8. Compute how many 7-digit numbers can be made from the digits 1,2,3,4,5,6,7 if
there is no repetition and the odd digits must appear in an unbroken sequence.
(Examples: 3571264 or 2413576 or 2467531, etc., but not 7234615.)
Counting Subsets
73
9. There is a very interesting function Γ : [0,∞) → R called the gamma function.
It is defined as Γ(x) = R ∞ tx−1 e−t dt
0
. It has the remarkable property that if x ∈ N,
then Γ(x) = (x − 1)!. Check that this is true for x = 1, 2, 3, 4.
Notice that this function provides a way of extending factorials to numbers other
than integers. Since Γ(n) = (n − 1)! for all n ∈ N, we have the formula n! = Γ(n + 1).
But Γ can be evaluated at any number in [0, ∞), not just at integers, so we
have a formula for n! for any n ∈ [0, ∞). Extra credit: Compute π!.
10. There is another significant function called Stirling’s formula that provides an
p
¢n
approximation to factorials. It states that n! ≈
2 π n ¡ ne . It is an approximation
n!
to n! in the sense that p2 π n¡ n ¢n approaches 1 as n approaches ∞. Use Stirling’s
e
formula to find approximations to 5!, 10!, 20! and 50!
.
3.3 Counting Subsets
The previous two sections were concerned with counting the number of
lists that can be made by selecting k entries from a set of n possible entries.
We turn now to a related question: How many subsets can be made by
selecting k elements from a set with n elements?
To highlight the differences between these two problems, look at the set
A = ©a, b, c, d, eª. First, think of the non-repetitive lists that can be made
from selecting two entries from A. By Fact 3.2 (on the previous page),
5!
there are (5−2)! = 5!
3! = 120
6
= 20 such lists. They are as follows.
(a, b),
(a, c),
(a, d),
(a, e),
(b, c),
(b, d),
(b, e),
(c, d),
(c, e)
(d, e)
(b, a),
(c, a),
(d, a),
(e, a),
(c, b),
(d, b),
(e, b),
(d, c),
(e, c)
(e, d)
Next consider the subsets of A that can made from selecting two ele-
ments from A. There are only ten such subsets, as follows.
©a, bª, ©a, cª, ©a, dª, ©a, eª, ©b, cª, ©b, dª, ©b, eª, ©c, dª, ©c, eª, ©d, eª.
The reason that there are more lists than subsets is that changing the
order of the entries of a list produces a different list, but changing the
order of the elements of a set does not change the set. Using elements
a, b ∈ A
©
, we can make two lists (a, b) and (b, a), but only one subset a, bª.
In this section we are concerned not with counting lists, but with
counting subsets. As was noted above, the basic question is this: How
many subsets can be made by choosing k elements from an n-element
set? We begin with some notation that gives a name to the answer to this
question.
74
Counting
Definition 3.2
¡n¢
If n and k are integers, then
k
denotes the number
of subsets that can be made by choosing k elements from a set with n
¡n¢
elements. The symbol k is read “n choose k.” (Some textbooks write
C(n, k)
¡n¢
instead of k .)
To illustrate this definition, the following table computes the values of
¡4¢
k for various values of k by actually listing all the subsets of the 4-element
set A = ©a, b, c, dª that have cardinality k. The values of k appear in the
far-left column. To the right of each k are all of the subsets (if any) of A of
size k. For example, when k = 1, set A has four subsets of size k, namely
©aª ©
©
©
¡4¢
, bª, cª and dª. Therefore 1 = 4. Similarly, when k = 2 there are six
¡4¢
subsets of size k so 2 = 6.
k
k
©
¢
-element subsets of a, b, c, dª
¡4
k
−1
¡ 4 ¢ = 0
−1
0
;
¡4¢
0 = 1
1
©aª,©bª,©cª,©dª
¡4¢
1 = 4
2
©a, bª,©a, cª,©a, dª,©b, cª,©b, dª,©c, dª
¡4¢
2 = 6
3
©a, b, cª,©a, b, dª,©a, c, dª,©b, c, dª
¡4¢
3 = 4
4
©a, b, c, dª
¡4¢
4 = 1
5
¡4¢
5 = 0
6
¡4¢
6 = 0
When k = 0, there is only one subset of A that has cardinality k, namely
¡4¢
the empty set, ;. Therefore 0 = 1.
Notice that if k is negative or greater than |A|, then A has no subsets
¡4¢
¡n¢
of cardinality k, so k = 0 in these cases. In general k = 0 whenever k < 0
¡n¢
or k > n. In particular this means k = 0 if n is negative.
¡4¢
Although it was not hard to work out the values of k by writing out
subsets in the above table, this method of actually listing sets would not
¡n¢
be practical for computing k when n and k are large. We need a formula.
¡5¢
To find one, we will now carefully work out the value of 3 in such a way
¡n¢
that a pattern will emerge that points the way to a formula for any k .
Counting Subsets
75
¡5¢
©
To begin, note that
a, b, c, d, eª
3 is the number of 3-element subsets of
.
¡5¢
These are listed in the following table. We see that in fact 3 = 10.
¡5¢
3
©
3!
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ª
The formula will emerge when we expand this table as follows. Taking
any one of the ten 3-element sets above, we can make 3! different non-
©
repetitive lists from its elements. For example, consider the first set a, b, cª.
The first column of the following table tallies the 3! = 6 different lists that
©
can be the letters a, b, cª. The second column tallies the lists that can be
©
made from a, b, dª, and so on.
¡5¢
3
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
acb
adb
aeb
adc
aec
aed
bdc
bec
bed
ced
bac
bad
bae
cad
cae
dae
cbd
cbe
dbe
dce
3!
bca
bda
bea
cda
cea
dea
cdb
ceb
deb
dec
cba
dba
eba
dca
eca
eda
dcb
ecb
edb
edc
cab
dab
eab
dac
eac
ead
dbc
ebc
ebd
ecd
¡5¢
¢
This table has 3 columns and 3! rows, so it has a total of 3!¡53 lists.
But notice also that the table consists of every non-repetitive length-3 list
©
that can be made from the symbols a, b, c, d, eª. We know from Fact 3.2
5!
that there are (5−3)! such lists. Thus the total number of lists in the table
¢
is 3!¡53 =
5!
(5−3)! . Dividing b
oth sides of this equation by 3!, we get
Ã
!
5
5!
=
.
3
3!(5 − 3)!
Working this out, you will find that it does give the correct value of 10.
But there was nothing special about the values 5 and 3. We could
¡n¢
¡5¢
¡n¢
do the above analysis for any k instead of 3 . The table would have k
columns and k! rows. We would get
Ã
!
n
n!
=
.
k
k!(n − k)!
We summarize this as follows:
76
Counting
Ã
!
Ã
!
n
n!
n
Fact 3.3 If n, k ∈ Z and 0 ≤ k ≤ n, then
=
. Otherwise
= 0.
k
k!(n − k)!
k
Let’s now use our new knowledge to work some exercises.
Example 3.4
©
How many 4-element subsets does 1, 2, 3, 4, 5, 6, 7, 8, 9ª have?
¡9¢
The answer is 4 =
9!
4!(9−4)! = 9!
4!5! = 9·8·7·6·5!
4!5!
= 9·8·7·6
4!
= 9·8·7·6
24
= 126.
Example 3.5
A single 5-card hand is dealt off of a standard 52-card deck.
How many different 5-card hands are possible?
To answer this, think of the deck as being a set D of 52 cards. Then a
5-card hand is just a 5-element subset of D. For example, here is one of
many different 5-card hands that might be dealt from the deck.
½
7
2
3
A
5 ¾
,
,
,
,
♣
♣
♥
♠
♦
The total number of possible hands equals the number of 5-element
subsets of D, that is
Ã
!
52
52!
52 · 51 · 50 · 49 · 48 · 47!
52 · 51 · 50 · 49 · 48
=
=
=
= 2, 598, 960.
5
5! · 47!
5! · 47!
5!
Thus the answer to our question is that there are 2,598,960 different
five-card hands that can be dealt from a deck of 52 cards.
Example 3.6
This problem concerns 5-card hands that can be dealt off
of a 52-card deck. How many such hands are there in which two of the
cards are clubs and three are hearts?
Solution: Think of such a hand as being described by a list of length
two of the form
µ ½
∗
∗ ¾ ½
∗
∗
∗ ¾ ¶
,
,
,
,
Book of Proof Page 11