Answers to Selected Exercises Applied Combinatorics

1 4 Answers to Selected ExercisesApplied Combinatoricsby Fred S. Roberts and Barry TesmanAnswers to Selected Exercises1 Chapter 2 Section : 263<20,000; : 263 103>5,000;3(a).31+32+33;3(b).31+32+33+34;3(c ).2 33; 105;8 2 10 83 105; +22+23+24=30and21+22+23+24+25= ;7.(2 2 2 2 3) 1; 96; stringxS1(x)S2(x)S3(x)S4(x)S5(x)S6(x)S7( x)S8(x)00 0000000010 0000111110 0011001111 01010101 Bit stringxS9(x)S10(x)S11(x)S12(x)S13(x)S14( x)S15(x)S16(x)00 1111111110 0000111110 0011001111 solutions to come. Comments/Corrections would be appreciated and should be sent to:Barry Tesman or Fred Roberts to Selected 1; ;2p 1;13(a).

2 2m2p m;13(b).2m 12p m;13(c).(2m 1) 2p m;14(a).3 2 3;14(b).23 2 +24+25;2.(8 7) + (8 12) + (7 12); +45; : 1015>10,000,000; No: 215<10,000,000; +255; +3;7.(7 3)30; +3 (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; 4 3 2 1; n 2 n 3 2 1 1;4(b).s6 710 vs. 6! = 720; 3 2 1 = 12;6(a).4 1 3 2 1;6(b).n 2 1 1 n 3 n 4 2 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;6 Answers to Selected ! 5! vs. 10!.Section 25! 1109 107 25! 11011 107 !

3 Schedules. Each committee in each schedule must be checked tosee if it received its first choice - this takesnsteps per schedule. Thecomputational complexity isf(n)=n n!;5. We will start (and end) at cost123411+ 3+ 11+8 = 23124311+ 6+ 2+ 4 = 13132418+ 9+ 6+ 8 = 31134218+ 11+ 3+ 16= 381423111+ 3+ 3+ 4 = 211432111+ 2+ 9+ 16= 386. best order is 2, 3, 1;7(a).n 3 10 (b).n+12 3 10 (a).n 3 10 (b).n+12 3 10 (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; Answers to Selected Exercises73(d).1 6 5 1; (20,5);5(a).9 9 8 7;5(b). 4088.

4 There are 1 9 8 7 extensions if the first digit is 1 and there are8 8 8 7 extensions if the first digit is 2 - 9; , {},{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}; ; ; 1; 9;7(a). 8 subsets of A and each subset can be assigned a 0 or 1;7(b).22n;8(a).223;8(b). (10,5); (50,7);3(a).6!3!(6 3)!= 20;3(b).7!4!3!= 35;3(c).5!1!4!=5;3(d).0; !1!(n 1)!=n; !2!3!= 10;{a, b},{a, c},{a, d},{a, e},{b, c},{b, d},{b, e},{c, d},{c, e},{d, e}; !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).

5 C(7,2) =7!2!(7 2)!=7!2!5!andC(7,5) =7!5!(7 5)!=7!5!2!;8 Answers to Selected Exercises7(b).C(6,4) =6!4!(6 4)!=6!4!2!andC(6,2) =6!2!(6 2)!=6!2!4!; ; (5,3) =5!3!2!= 10,C(4,2) =4!2!2!=6,C(4,3) =4!3!1!=4,and10=6+4; (7,5) =7!5!2!= 21,C(6,4) =6!4!2!= 15,C(6,5) =6!5!1!= 6, and 21 = 15 + 6;11(a).C(8,4);11(b).C(8,4)/2;11(c).28 2; (6,3) +C(6,2) +C(6,1) +C(6,0);13(a).C(10,5);13(b).210 2; (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 inthe 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 theones place and 1 choice for the tens place, then 8 7 choices for the other twoplaces; 0 in the hundreds place: 5 choices for the ones place and 1 choice for thehundreds 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).

6 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). J AVA , J AVA , J AVA , J AVA , J AVA , 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; Answers to Selected Exercises918(a).[C(3,1)C(27,2) +C(3,2)C(27,1) +C(3,3)C(27,0)] [C(12,1)C(138,2) +C(12,2)C(138,1) +C(12,3)C(138,0)];18(b).C(30,3) C(150,3) C(27,3) C(138,3);19(a).(nm)(mk)=n!m!(n m)!m!k!(m k)!=n!(n m)!k!(m k)!;(nk)(n km k)=n!k!(n k)!(n k)!(m k)!((n k) (m k))!

7 =n!k!(m k)!(n m)!; fromnis the same as not pickingn ritems Sum the entries in the row labeledn, , the (n+1)strow since the labelsstart with 0. Forn=2: 1+2+1=4; Forn=3: 1+3+3+1=8; Forn=4:1+4+6+4+1=16; in general, use repeated applications of Theorem and the fact that(n0)=(n+10);23. A set consists ofnmale items andmfemale items for a total ofn+ side: number of ways to pick a subset of sizerfrom this set ofn+ side: Picking a subset of sizercanbedonebypicking0males&rfemales,o r 1 male andr 1 females, or .., orrmales & 0 (a). nr =(n+r 1r)and nr 1 + n 1r =(n+r 2r 1)+(n+r 2r)are equal usingequation ( );25.

8 Nr =(n+r 1r)=(n+r 1)!r!(n 1)!andnr n+1r 1 =nr(n+r 1r 1)=nr(n+r 1)!(r 1)!n!=(n+r 1)!r!(n 1)!andn+r 1r nr 1 =n+r 1r(n+r 2r 1)=n+r 1r(n+r 2)!(r 1)!(n 1)!=(n+r 1)!r!(n 1)!;26(a). In the sequence ofn1 s,tcould be any integer from 0 ton,inclusive;26(b). The sequence is strictly increasing when(ni)<(ni+1)orn!i!(n i)!<n!(i+1)!(n i 1)!ori!(n i)!>(i+1)!(n i 1)! orn i>i+1 ori<n 12. Similarly, it is strictly decreasing wheni>n (c). By 26(b), the largest entry in the sequence occurs wheni= n2 .Thatis,at(n n/2 );Section (a).No;1(b).No;1(c).Yes;1(d).No;10 Answers to Selected Exercises1(e).No;2(a). 1/2;2(b).

9 1/36;2(c). 1/3;3(a).38;3(b).12;3(c).34; (3,2) 2+C(3,3)33=727; ; ; ; 452; ; ; (4,3) +C(4,4)42=516; ; ; 18 16 144!C(20,4);15(a).C(6,2)/26+C(6,3) (b).C(6,2)/26+C(6,4) (c).C(6,2)/26+25/26 C(5,1) (d).C(6,0)/26+C(6,2)/26+C(6,4)/26+C(6,6) (e).C(5,1)/26+C(5,3)/26+C(5,5) (a). probability ofE=n(E)n(S)and probability ofEc=n(S) n(E)n(S)=1 n(E)n(S).16(b).EandFdisjoint impliesn(E F)=n(E)+n(F).So, probability ofE F=n(E F)n(S)=n(E)+n(F)n(S)and probability ofE+ probability ofF=n(E)n(S)+n(F)n(S). Answers to Selected Exercises1116(c).EandFnot disjoint impliesn(E F)=n(E)+n(F) n(E F).So, probability ofE F=n(E F)n(S)=n(E)+n(F) n(E F)n(S)and probability ofE+probability ofF probability ofE F=n(E)n(S)+n(F)n(S) n(E F)n(S).

10 17(a).22/24+22/24 1 (b).23/24+2/24 1 (a).aaaa,aaab,aaba,abaa,baaa,aabb,abab,a bba,baab,baba,bbaa,abbb,babb,bbab,bbba,b bbb;1(b).aa, ab, ac, ba, bb, bc, ca, cb, cc;1(c).{a, a, a, a},{a, a, a, b},{a, a, b, b},{a, b, b, b},{b, b, b, b};1(d).{a, a},{a, b},{a, c},{b, b},{b, c},{c, c};2(a).PR(2,4) = 24;2(b).PR(3,2) = 32;2(c).CR(2,4) =C(2 + 4 1,4) = 5;2(d).CR(3,2) =C(3 + 2 1,2) = 6;3(a).PR(3,7) = 37;3(b).CR(4,7) =C(4 + 7 1,7); (4,8) =C(4 + 8 1,8); (5,12) =C(5 + 12 1,12) = 1820; (5,8) PR(5,7) = 58 57;7(a).CR(4,2) =C(4 + 2 1,2) = 10;7(b). 1560;8(a).CR(3,82) =C(3 + 82 1,82) = 3486;8(b).CR(2,82) =C(2 + 82 1,82) = 83; (4,12) = 412; j=0CR(3,j); j=0CR(m, j).