,
♣
♣
♥
♥
♥
where the first entry is a 2-element subset of the set of 13 club cards, and
the second entry is a 3-element subset of the set of 13 heart cards. There
¡13¢
¡13¢
are
2
choices for the first entry and
3
choices for the second entry, so
¡13¢¡13¢
13!
by the multiplication principle there are
2
3
= 13!
2!11! 3!10! = 22, 308 such
lists. Answer: There are 22, 308 possible 5-card hands with two clubs
and three hearts.
Example 3.7
Imagine a lottery that works as follows. A bucket contains
36 balls numbered 1,2,3,4,...,36. Six of these balls will be drawn randomly.
For $1 you buy a ticket that has six blanks: ä ä ä ä ä ä . You fill in the
blanks with six different numbers between 1 and 36. You win $1, 000, 000
Counting Subsets
77
if you chose the same numbers that are drawn, regardless of order. What
are your chances of winning?
Solution: In filling out the ticket you are choosing six numbers from
¡36¢
a set of 36 numbers. Thus there are
6
=
36!
6!(36−6)! = 1, 947, 792 different
combinations of numbers you might write. Only one of these will be a
winner. Your chances of winning are one in 1, 947, 792.
Exercises for Section 3.3
1. Suppose a set A has 37 elements. How many subsets of A have 10 elements?
How many subsets have 30 elements? How many have 0 elements?
2. Suppose A is a set for which |A| = 100. How many subsets of A have 5 elements?
How many subsets have 10 elements? How many have 99 elements?
3. A set X has exactly 56 subsets with 3 elements. What is the cardinality of X ?
4.
¯©
Suppose a set B has the property that ¯ X : X ∈ P(B), |X | = 6ª¯¯ = 28. Find |B|.
5. How many 16-digit binary strings contain exactly seven 1’s? (Examples of such
strings include 0111000011110000 and 0011001100110010, etc.)
6. ¯©
¯
X ∈ P(©0,1,2,3,4,5,6,7,8,9ª) : |X | = 4ª¯¯ =
7. ¯©
¯
X ∈ P(©0,1,2,3,4,5,6,7,8,9ª) : |X | < 4ª¯¯ =
8. This problem concerns lists made from the symbols A,B,C,D,E,F,G,H,I.
(a) How many length-5 lists can be made if repetition is not allowed and the
list is in alphabetical order? (Example: BDEFI or ABCGH, but not BACGH.)
(b) How many length-5 lists can be made if repetition is not allowed and the
list is not in alphabetical order?
9. This problem concerns lists of length 6 made from the letters A,B,C,D,E,F,
without repetition. How many such lists have the property that the D occurs
before the A?
10. A department consists of 5 men and 7 women. From this department you select
a committee with 3 men and 2 women. In how many ways can you do this?
11. How many positive 10-digit integers contain no 0’s and exactly three 6’s?
12. Twenty-one people are to be divided into two teams, the Red Team and the
Blue Team. There will be 10 people on Red Team and 11 people on Blue Team.
In how many ways can this be done?
13.
¡n¢
Suppose n and k are integers for which 0 ≤ k ≤ n. Use the formula k =
n!
k!(n−k)!
¡n¢
¢
to show that k = ¡ n
n−k .
14. Suppose n, k ∈ Z, and 0 ≤ k ≤ n. Use Definition 3.2 alone (without using Fact 3.3)
¡n¢
¢
to show that k = ¡ n
n−k .
78
Counting
3.4 Pascal’s Triangle and the Binomial Theorem
¡n¢
There are some beautiful and significant patterns among the numbers k .
This section investigates a pattern based on one equation in particular. It
happens that
Ã
!
Ã
!
Ã
!
n + 1
n
n
=
+
(3.2)
k
k − 1
k
for any integers n and k with 1 ≤ k ≤ n.
¡n+1¢
To see why this is true, recall that
k
equals the number of k-element
subsets of a set with n + 1 elements. Now, the set A = ©0, 1, 2, 3, . . . , nª has
n + 1
¡n+1¢
elements, so
k
equals the number of k-element subsets of A. Such
subsets can be divided into two types: those that contain 0 and those that
do not contain 0. To make a k-element subset that contains 0 we can start
©
with 0ª and then append to this set an additional k − 1 numbers selected
©
¡
n ¢
from 1, 2, 3, . . . , nª. There are k−1 ways to make this selection, so there
¡
n ¢
are
k
k−1
-element subsets of A that contain 0. Concerning the k-element
¡n¢
subsets of A that do not contain 0, there are k of these sets, for we can
©
form them by selecting k elements from the n-element set 1, 2, 3, . . . , nª. In
light of all this, Equation (3.2) just expresses the obvious fact that the
number of k-element subsets of A equals the number of k-element subsets
that contain 0 plus the number of k-element subsets that do not contain 0.
¡0¢
0
1
¡1¢
¡1¢
0
1
1
1
¡2¢
¡2¢
¡2¢
0
1
2
1
2
1
¡3¢
¡3¢
¡3¢
¡3¢
0
1
2
3
1
3
3
1
¡4¢
¡4¢
¡4¢
¡4¢
¡4¢
0
1
2
3
4
1
4
6
4
1
¡5¢
¡5¢
¡5¢
¡5¢
¡5¢
¡5¢
0
1
2
3
4
5
1
5
10
10
5
1
¡6¢
¡6¢
¡6¢
¡6¢
¡6¢
¡6¢
¡6¢
0
1
2
3
4
5
6
1
6
15
20
15
6
1
¡7¢
¡7¢
¡7¢
¡7¢
¡7¢
¡7¢
¡7¢
¡7¢
0
1
2
3
.
. 4
5
6
7 .
1
7
21
35
35
21
7
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Figure 3.2. Pascal’s triangle
Now that we have seen why Equation (3.2) is true, we are going to
¡n¢
arrange the numbers k in a triangular pattern that highlights various
relationships among them. The left-hand side of Figure 3.2 shows numbers
¡n¢
¡0¢
k
arranged in a pyramid with 0 at the apex, just above a row containing
¡1¢
¡2¢
k
with k = 0 and k = 1. Below this is a row listing the values of k for
k = 0,1,2
¡n¢
. In general, each row listing the numbers k is just above a row
¡n+1¢
listing the numbers
k
.
Pascal’s Triangle and the Binomial Theorem
79
¡n+1¢
Any number
k
for 0 < k < n in this pyramid is immediately below
¡
n ¢
¡n¢
and between the the two numbers k−1 and k in the previous row. But
¡n+1¢
¢
¢
Equation 3.2 says
k
= ¡ n
k
+¡n
−1
k , and therefore any number (other than 1)
in the pyramid is the sum of the two numbers immediately above it.
This pattern is especially evident on the right of Figure 3.2, where
¡n¢
each k is worked out. Notice how 21 is the sum of the numbers 6 and 15
above it. Similarly, 5 is the sum of the 1 and 4 above it and so on.
The arrangement on the right of Figure 3.2 is called Pascal’s triangle.
(It is named after Blaise Pascal, 1623–1662, a French mathematician and
philosopher who discovered many of its properties.) Although we have
written only the first eight rows of Pascal’s triangle (beginning with Row 0
at the apex), it obviously could be extended downward indefinitely. We
could add an additional row at the bottom by placing a 1 at each end and
obtaining each remaining number by adding the two numbers above its
position. Doing this would give the following row:
1
8
28
56
70
56
28
8
1
¡8¢
This row consists of the numbers k for 0 ≤ k ≤ 8, and we have computed
¡8¢
¡n¢
them without the formula k =
8!
k!(8−k)! . Any k can be computed this way.
The very top row (containing only 1) is called Row 0. Row 1 is the
next down, followed by Row 2, then Row 3, etc. With this labeling, Row n
¡n¢
consists of the numbers k for 0 ≤ k ≤ n.
Notice that Row n appears to be a list of the coefficients of (x + y)n.
For example (x + y)2 = 1x2 + 2x y + 1 y2, and Row 2 lists the coefficients 1 2 1.
Similarly (x + y)3 = 1x3 + 3x2 y + 3x y2 + 1 y3, and Row 3 is 1 3 3 1. Pascal’s
triangle is shown on the left of Figure 3.3 and on the right are the
expansions of (x + y)n for 0 ≤ n ≤ 5. In every case (at least as far as you care
to check) the numbers in Row n match up with the coefficients of (x + y)n.
1
1
1
1
1x
+ 1y
1
2
1
1x2 + 2x y + 1 y2
1
3
3
1
1x3 + 3x2 y + 3x y2 + 1 y3
1
4
6
4
1
1x4 + 4x3 y + 6x2 y2 + 4x y3 + 1 y4
1
5
10
10
5
1
1x5 + 5x4 y +10x3 y2 +10x2 y3 + 5x y4 + 1 y5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Figure 3.3. The nth row of Pascal’s triangle lists the coefficients of (x+ y)n
80
Counting
In fact this turns out to be true for every n. This result is known as
the binomial theorem, and it is worth mentioning here. It tells how to
raise a binomial x + y to a non-negative integer power n.
Theorem 3.1
(Binomial Theorem) If n is a non-negative integer, then
(x + y)n = ¡n¢xn
¢xn−1 y
¢xn−2 y2
¢xn−3 y3
¢x yn−1
¢ yn
0
+ ¡n1
+ ¡n2
+ ¡n3
+ · · · + ¡ n
n
+ ¡n
−1
n
.
For now we will be content to accept the binomial theorem without
proof. (You will be asked to prove it in an exercise in Chapter 10.) You
may find it useful from time to time. For instance, you can apply it if you
ever need to expand an expression such as (x + y)7. To do this, look at Row
7 of Pascal’s triangle in Figure 3.2 and apply the binomial theorem to get
(x + y)7 = x7 + 7x6 y + 21x5 y2 + 35x4 y3 + 35x3 y4 + 21x2 y5 + 7xy6 + y7.
For another example,
(2a − b)4 = ((2a) + (−b))4
= (2a)4 + 4(2a)3(−b) + 6(2a)2(−b)2 + 4(2a)(−b)3 + (−b)4
= 16a4 − 32a3b + 24a2b2 − 8ab3 + b4.
Exercises for Section 3.4
1. Write out Row 11 of Pascal’s triangle.
2. Use the binomial theorem to find the coefficient of x8 y5 in (x + y)13.
3. Use the binomial theorem to find the coefficient of x8 in (x + 2)13.
4. Use the binomial theorem to find the coefficient of x6 y3 in (3x − 2y)9.
5.
Pn
¡n¢
Use the binomial theorem to show
= 2n
k=0 k
.
6.
Pn
¡n¢
Use Definition 3.2 (page 74) and Fact 1.3 (page 12) to show
= 2n
k=0 k
.
7.
Pn
¢
Use the binomial theorem to show
3k¡n = 4n
k=0
k
.
8. Use Fact 3.3 (page 76) to derive Equation 3.2 (page 78).
9.
¡n¢
¢
¢
¢
¢
¢
Use the binomial the
orem to show 0 − ¡n1 + ¡n2 − ¡n3 + ¡n4 − · · · + (−1)n¡nn = 0.
10.
¢
¢
Show that the formula k¡n
k = n¡n−1
k−1 is true for all integers n, k with 0 ≤ k ≤ n.
11.
¢
Use the binomial theorem to show 9n = Pn
(−1)k¡n 10n−k
k=0
k
.
12.
¡n¢¡ k ¢
¢¡n−m¢
Show that k m = ¡ n
m
k−m .
13.
¡n¢
¢
¢
¢
¢
¢
Show that 3 = ¡22 + ¡32 + ¡42 + ¡52 + · · · + ¡n−1
2
.
14. The first five rows of Pascal’s triangle appear in the digits of powers of 11:
110 = 1, 111 = 11, 112 = 121, 113 = 1331 and 114 = 14641. Why is this so? Why
does the pattern not continue with 115?
Inclusion-Exclusion
81
3.5 Inclusion-Exclusion
Many counting problems involve computing the cardinality of a union A ∪B
of two finite sets. We examine this kind of problem now.
First we develop a formula for |A ∪ B|. It is tempting to say that |A ∪ B|
must equal |A| + |B|, but that is not quite right. If we count the elements
of A and then count the elements of B and add the two figures together,
we get |A| + |B|. But if A and B have some elements in common, then we
have counted each element in A ∩ B twice.
A
B
Therefore |A| + |B| exceeds |A ∪ B| by |A ∩ B|, and consequently |A ∪ B| =
|A| + |B| − |A ∩ B|. This can be a useful equation.
|A ∪ B| = |A| + |B| − |A ∩ B|
(3.3)
Notice that the sets A, B and A ∩ B are all generally smaller than A ∪ B, so
Equation (3.3) has the potential of reducing the problem of determining
|A ∪ B| to three simpler counting problems. It is sometimes called an
inclusion-exclusion formula because elements in A ∩ B are included (twice)
in |A|+|B|, then excluded when |A ∩B| is subtracted. Notice that if A ∩B = ;,
then we do in fact get |A ∪ B| = |A| + |B|; conversely if |A ∪ B| = |A| + |B|, then
it must be that A ∩ B = ;.
Example 3.8
A 3-card hand is dealt off of a standard 52-card deck. How
many different such hands are there for which all 3 cards are red or all
three cards are face cards?
Solution: Let A be the set of 3-card hands where all three cards are
red (i.e., either ♥ or ♦). Let B be the set of 3-card hands in which all three
cards are face cards (i.e., J,K or Q of any suit). These sets are illustrated
below.
((
)
(
)
(
)
)
5
K
2
K
J
Q
A
6
6
A
=
,
,
,
,
,
,
,
,
, . . .
(Red cards)
♥
♦
♥
♥
♥
♥
♦
♦
♥
Book of Proof Page 12
