7! 2!(7−2)!
=
7! 2!5!
and C (7, 5) =
7! 5!(7−5)!
=
7! 5!2! ;
8 7(b). C (6, 4) =
6! 4!(6−4)!
Answers to Selected Exercises =
6! 4!2!
and C (6, 2) =
6! 2!(6−2)!
=
6! 2!4! ;
n+1 2
× 3 × 10−9 . × 3 × 10−11 .
8(a). n × 3 × 10−11 . 8(b).
n+1 2
Section 2.5 . 1(a). 3 · 2; 1(b). 5 · 4 · 3; 1(c). 8 · 7 · 6 · 5 · 4; 1(d). 0; 2(a). 63 ; 2(b). 6 · 5 · 4; 2(c). 1 · 6 · 6; 2(d). 1 · 5 · 4; 3(a). 84 ; 3(b). 8 · 7 · 6 · 5; 3(c). 1 · 8 · 8 · 8;
8. 1 7 21 35 35 21 7 1; 9. C (5, 3) =
5! 3!2!
= 10, C (4, 2) =
4! 2!2!
= 6, C (4, 3) =
4! 3!1!
= 4, and 10 = 6 + 4; = 6, and 21 = 15 + 6;
10. C (7, 5) =
7! 5!2!
4
Answers to Selected Exercises
Applied Combinatorics
by Fred S. Roberts and Barry Tesman
Answers to Selected Exercises1
Chapter 2
Section 2.1 . 1. yes: 263 < 20, 000; 2. yes: 263 · 103 > 5, 000; 3(a). 31 + 32 + 33 ; 3(b). 31 + 32 + 33 + 34 ; 3(c). 2 · 33 ; 4. 83 × 105 ; 8 × 2 × 10 × 83 × 105 ; 5. n = 5 since 21 + 22 + 23 + 24 = 30 and 21 + 22 + 23 + 24 + 25 = 62. 6. 2mn ; 7. (2 · 2 · 2 · 2 · 3) − 1; 8. 106 − 96 ; 9. Bit string x S1 (x) S2 (x) S3 (x) S4 (x) 00 0 0 0 0 10 0 0 0 0 10 0 0 1 1 11 0 1 0 1 Bit string x S9 (x) S10 (x) S11 (x) S12 (x) 00 1 1 1 1 10 0 0 0 0 10 0 0 1 1 11 0 1 0 1 10. 22
2n
S 5 ( x) S 6 ( x) S 7 ( x) S 8 ( x) 0 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 S13 (x) S14 (x) S15 (x) S16 (x) 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1
1 More solutions to come. Comments/Corrections would be appreciated and should be sent to: Barry Tesman (tesman@) or Fred Roberts (froberts@).
6 9. 5! · 5! vs. 10!. Section 2.4 . 1. 25! · 2. 25! ·
1 109 1 1011
Answers to Selected Exercises
· ·
1 3.15×107 1 3.15×107
≈ 4.9 × 108 years. ≈ 4.9 × 106 years.
7
7(a). 28 . There are 23 = 8 subsets of A and each subset can be assigned a 0 or 1; 7(b). 22 ; 8(a). 22 ; 8(b). 22 . Section 2.7 . 1. C (10, 5); 2. C (50, 7); 3(a). 3(b). 3(c).
6! 3!(6−3)! 7! 4!3! 5! 1!4!
n 3 n
= 20;
= 35; = 5;
3(d). 0; 4. 5.
n! 1!(n−1)! 5! 2!3!
= n;
= 10; {a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e};
6! 6. 2!4! = 15; {a, b}, {a, c}, {a, d}, {a, e}, {a, f }, {b, c}, {b, d}, {b, e}, {b, f }, {c, d}, {c, e}, {c, f }, {d, e}, {d, f }, {e, f };
7(a). C (7, 2) =
Answers to Selected Exercises 3(d). 1 · 6 · 5 · 1; 4. P (20, 5); 5(a). 9 × 9 × 8 × 7; 5(b). 4088. There are 1 × 9 × 8 × 7 extensions if the first digit is 1 and there are 8 × 8 × 8 × 7 extensions if the first digit is 2 - 9; 6. 403 = 64, 000. Section 2.6 . 1. {}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}; 2. 235 ; 3. 27 ; 5. 210 −ted Exercises 11. 22
n−1
5
;
12. 2p ; 2p − 1; 13(a). 2m 2p−m ; 13(b). 2m−1 2p−m ; 13(c). (2m − 1) · 2p−m ; 14(a). 3 · 2 · 3; 14(b). 23·2·3 . Section 2.2 . 1. 23 + 24 + 25 ; 2. (8 · 7) + (8 · 12) + (7 · 12); 3. 55 + 45 ; 4. Yes: 1015 > 10, 000, 000; No: 215 < 10, 000, 000; 5. 264 + 255 ; 6. 2 + 3; 7. (7 · 3)30 ; 8. 33 + 3 · 43 . Section 2.3 . 1(a). 123, 132, 213, 231, 312, 321; 1(b). 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321; 2. 1 · 4 · 3 · 2 · 1; 3. 1 · n − 2 · n − 3 · · · · · 2 · 1 · 1; 4(b). s6 ≈ 710 vs. 6! = 720; 5. 2 · 3 · 2 · 1 = 12; 6(a). 4 · 1 · 3 · 2 · 1; 6(b). n − 2 · 1 · 1 · n − 3 · n − 4 · · · · · 2 · 1; 7. 1 · 3 · 2 · 1 · 1; 8(a). 3 · 3 · 2 · 2 · 1 · 1; 8(a). n · n · n − 1 · n − 1 · · · · · 2 · 2 · 1 · 1;
3. There are n! schedules. Each committee in each schedule must be checked to see if it received its first choice - this takes n steps per schedule. The computational complexity is f (n) = n · n!; 5. We will start (and end) at 1. Total cost Order 1 2 3 4 1 1+ 3+ 11+8 = 23 12431 1+ 6+ 2+ 4 = 13 8+ 9+ 6+ 8 = 31 13241 1 3 4 2 1 8+ 11+ 3+ 16= 38 1 4 2 3 1 11+ 3+ 3+ 4 = 21 1 4 3 2 1 11+ 2+ 9+ 16= 38 6. best order is 2, 3, 1; 7(a). n × 3 × 10−9 . 7(b).
= 21, C (6, 4) =
6! 4!2!
= 15, C (6, 5) =
6! 5!1!
11(a). C (8, 4); 11(b). C (8, 4)/2; 11(c). 28 − 2; 12. C (6, 3) + C (6, 2) + C (6, 1) + C (6, 0); 13(a). C (10, 5); 13(b). 210 − 2; 14. C (21, 5)C (5, 3)8! + C (21, 4)C (5, 4)8! + C (21, 3)C (5, 5)8!; 15. Calculate the sum of those odd numbers with distinct digits with no 0’s, a 0 in the tens place, or a 0 in the hundreds place. No 0’s: 5 choices for the ones place, then 8 · 7 · 6 choices for the other three places; 0 in the tens place: 5 choices for the ones place and 1 choice for the tens place, then 8 · 7 choices for the other two places; 0 in the hundreds place: 5 choices for the ones place and 1 choice for the hundreds place, then 8 · 7 choices for the other two places; (5 · 8 · 7 · 6) + (5 · 1 · 8 · 7) + (5 · 1 · 8 · 7) = 2240; 16(a). C (7, 3) · C (4, 2); 16(b). C (7, 1) · C (4, 1) + C (7, 2) · C (4, 2) + C (7, 3) · C (4, 3) + C (7, 4) · C (4, 4); 16(c). C (10, 3); 16(d). C (7, 2) · C (4, 2) − C (6, 1) · C (3, 1); 17(a)(i). C (9, 4); 17(a)(ii). 6; 17(a)(iii). 2; 17(a)(iv). 1; 17(b). JAVA, JAVA, JAVA, JAVA, JAVA, C++, C++, C++, C++; 17(c)(i). 9!; 17(c)(ii). 6 · 4! · 5!; 17(c)(iii). 2 · 4! · 5!; 17(c)(iv). 5 · 4 · 4 · 3 · 3 · 2 · 2 · 1 · 1;