- Answers to Exercises 253
1.5.3. 313.
1.5.4. 6 ·6 = 36.
1.5.5. 1220.
1.5.6. (2^20 )^12.
1.6 Permutations
1.6.1. n!.
1.6.2. (a) 7· 5 · 3 ·1 = 105. (b) (2n−1)·(2n−3)··· 3 ·1.
1.7 The Number of Ordered Subsets
1.7.1. (We don’t think you could really draw the whole tree; it has almost
1020 leaves. It has 11 levels of nodes.)
1.7.2. (a) 100!. (b) 90!. (c) 100!/90! = 100· 99 ···91.
1.7.3. (n−n!k)!=n(n−1)·(n−k+ 1).
1.7.4. In one case, repetition is not allowed, while in the other case, it is
allowed.
1.8 The Number of Subsets of a Given Size
1.8.1. Handshakes; lottery; hands in bridge.
1.8.2. See Pascal’s Triangle in Chapter 3.
1.8.3.
(n
0)
=
(n
n)
=1,
(n
1)
=
(n
n− 1)
=n.1.8.4. An algebraic proof of (1.7) is straightforward. In (1.8), the right-
hand side countsk-subsets of ann-element set by separately counting those
that contain a given element and those that do not.
1.8.5.An algebraic proof is easy. A combinatorial interpretation:n^2 is the
number of all ordered pairs (a, b) witha, b∈{ 1 , 2 ,...,n}, and
(n
2)
is the
number of ordered pairs (a, b) among these witha<b(why?). To count the
remaining ordered pairs (a, b) (those witha≥b), add 1 to their first entry.
Then we get a pair (a′,b) with 1≤a′,b≤n+1,a′>b, and conversely,
every such pair is obtained this way. Hence the number of these pairs is(
n+1
2
)
.
1.8.6. Again, an algebraic proof is easy. A combinatorial interpretation:
We can choose ak-element set by first choosing one element (npossibilities)
and then choosing a (k−1)-element subset of the remainingn−1 elements
(
(n− 1
k− 1)
possibilities). But we get everyk-element subset exactlyktimes
(depending on which of its elements was chosen first), so we have to divide
the result byk.