Exam (elaborations) TEST BANK FOR Discrete and Combinatorial Mathematics 5th Edition By Ralph P. Grimaldi (Instructor's Solution Manual)

Exam (elaborations) TEST BANK FOR Discrete and Combinatorial Mathematics 5th Edition By Ralph P. Grimaldi (Instructor's Solution Manual) INSTRUCTOR'S SOLUTIONS MANUAL DISCRETE AND COMBINAtORIAL MATHEMATICS FIFTH EDITION Ralph P. Gritnaldi Rose-Hulman Institute o/Technology Boston San Fra.'1cisco New York London Toronto Sydney Tokyo Madrid Mexico City Munich Paris Town Dedicated to the memory of Nellie and Glen /Fuzzy/ Shidler CONTENTS PART 1 FUNDAMENTALS OF DISCRETE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 PART 2 Fundamental Principles Counting :Fundamentals of Logic Set Theory Properties of the Integel's: Mathematical Induction Relations and Functions Languages: Finite State Machines Relations: The Second Time Around FURTHER TOPICS IN ENUMERATION Chapter 8 Chapter 9 Chapter 10 The Principle of Inclusion and Exclusion Generating Functions Recurrence Relations GRAPH 1.'HEORY AND APPLICATIONS 1 3 26 59 95 134 167 179 207 209 229 243 281 4: Chapter 14 Riugs and Modular Arithmetic 369 Chapter 15 Boolean Algebra and Switching Functions 396 Chapter 16 Groups, Coding Theory, and Polya's Method. 413 Enumeration Chapter Fini te Fields and Comhinatorial Designs 440 THE APPENDICES 459 Appendix 1 Exponential and Logarithmic Functions 461 Appendix 2 Properties of Matrices 464 Appendix 3 Countable and Uncountable Sets 468 PART 1 FUNDAMENTALS OF DISCRETE MATHEMATICS CHAPTER 1 Sections and 1. ( a) By the rule of sum, there are 8 5 = 13 for the eventual winner. (b) Sim~e there are eight Republica,ns and Democrats, the rule of product we have 8 X 5 ::;:;; 40 possible pairs of opposing candidates. (c) The rule of sum in part (a); the rule of product in part (b). 2. By the rule of product there are 5 x 5 x 5 x 5 x 5 x 5 = 56 license plates where the first two symbols are vowels and the last four are even digits. 3. By the rule of product there are (a) 4 X 12 X 3 x 2 = 288 distinct Buicks that can be manufactured. Of these, (b) 4 x 1 x 3 x 2 = 24 are blue. 4. ( a) From the rule of product there are 10 X 9 X 8 X 7 = P( 10, 4) = 5040 possible slates. (b) (i) There are 3 x 9 x 8 x 7 = 1512 slates where a physician is nominated for president. (ii) The number of slates with exactly one physician appearing is 4 x [3 x 7 x 6 x 5] = 2520. (iii) There are 7 x 6 x 5 x 4 = 840 slates where no physician is nominated for any of the four offices. Consequently, 5040 - 840 = 4200 slates include at least one physician. 5. Based on the evidence supplied by Jennifer and Tiffany, from the rule of product we find that there are 2 x 2 x 1 x 10 x 10 x 2 = 800 different license plates. 6. (a) Here we are dealing with the permutations of 30 objects (the runners) taken 8 (the first eight finishing positions) at a trophies can be awarded in P(SO,S) = 30!/22! ways. (b) .n.!.Hl>en;(:!, and runners in 6 ways. each these 6 ways, there are P(28,6) ways for the other 6 finishers (in the top 8) to finish the race. the are 6· to with two runners a.U:lon,~ the top are (a.) 12! re31~nCl"lOl,LI); (b) (4!)( 8!) ways so that the four ..... ,." ..... "' ... and (c) (4!)(51)(3!) where the top .,..""",.,. ... tare PT(:JCe:8SE:<1 3 9. (a) (14)(12) = 168 (b) (14)(12)(6)(18) = 18,144 (c) (8)(18)(6)(3)(14)(12)(14)(12) = 73,156,608 10. Consider one such arrangement - say we have three books on one shelf and on the other. This can be accomplished 15! ways. fact for any subdivision (resulting in two nonempty shelves) of the 15 books we get 15! ways to arrange the books on the two shelves. Since there are 14 ways to subdivide the books so that each shelf has at least one book, the total number of ways in which Pamela can arrange her books in this manner is (14)(15!). 11. ( a) There are four roads from town A to town B and three roads from town B to town C, so by the rule of product there are 4 x 3 = 12 roads from A to C that pass through B. Since there are two roads from A to C directly, there are 12 + 2 = 14 ways in which Linda can make the trip from A to C. (b) Using the result from part (a), together with the rule of product, we find that there are 14 X 14 = 196 different round trips (from A to C and back to A). (c) Here there are 14 x 13 = 182 round trips. 12. (1) a,c,t (2) a,t,c (3) c,a,t (4) c,t,a (5) t,a,c (6) t,c,a 13. (a) 8! = P(8, 8) (b) 71 6! 14. (a) P(7,2) = 7!/(7 - 2)! = 7!/5! = (7)(6) = 42 (b) P(8,4) = 8!/(8 - 4)! = 8!/4! = (8)(7)(6)(5) = 1680 (c) P(lO, 7) = 10!/(1O - 7)! = 101/3! = (10)(9)(8)(7)(6)(5)(4) = 604,800 (d) P(12, 3) = 12!/(12 - 3)! == 12!/9! = (12)(11)(10) = 1320 15. Here we must place a,b,c,d in the positions denoted by x: e A e A e A e A e. By the rule of product there are 4! ways to do this. 16. (a) With repetitions allowed there are 4025 distinct messages. 20. (b) By the rule of product there are 40 x 30 x 30 x ... x 30 x 30 x 40 = (402)(3023) messages. Class (21 - 2)(224 - 2) = 2,1 928,964 Class B: 214(216 - 2) = 1,073,709,056 C: = 532, 608 system. (a) 7! == 5040 (3!)(5)( 4!) = (b) 4 x 3 x 3 x 2 x 2 x 1 x 1 = Since are three A's, there are 8l/3! = arrangements. 4 (b) Here we arrange the six symbols D,T,G,R,M, AAA in 6! = 720 21. (a) 121/(3!2!2!2!) (b) [11!/(3!2!212!)] (for AG) + [11!/(31212!2!)] (for GA) (c) Consider one where the are adjacent: S,C,L,G,C,L, OIOOIA. These seven symbols can be arranged in (7!)/(2!21) ways. Since O,O,O,I,I,A can be arranged in (6!)/(3!2!) ways, the number of arrangements with all vowels adjacent is [7!/(2!2!)}[61/(3!2!)]. 22. (Case 1: leading digit is 5) (6!)/(21) (Case 2: The leading digit is 6) (6!)/(2!)2 (Case 3: leading digit is 7) (61)/(21)2 In total there are (6!)/(2!)][1 + (1/2) + (1/2)J = 6! = 720 such positive integers n. 23. Here the solution is the number of ways we can arrange 12 objects - 4 the first type, 3 of the second, 2 of the third, and 3 of the fourth. There are 12!/( 4!3t2!31) = 277,200 ways. 24. Pen + 1,r) = {n + l)!/(n 1- 1')1 = [en + l)/Cn 1 - r)] . [nt/en - 1')IJ = fen + 1)/Cn 1- r)]P(n,r). 25. ( a) n = 10 (b) n = 5 (c) 2nl/(n - 2)1 + 50 = (2n)!/(2n - 2)! =} 2n(n -1) + 50 = (2n)(2n -1) =} n 2 = 25 =} n=5. 26. Any such path fro:m, (0,0) to (7,7) or from (2,7) to (9,14) is an arrangement of 7 R's and 7 U's. There are (141)/(7!7!) such arrangements. In general I for m, n nonnegative integers, and any real numbers a, b, the number of such paths from (a, b) to (a + m, b n) is (m n)!/{m!n!). 21. (a) path consists 2 1 V, and 7 A's. There are 10!/(2!1!7!) ways to arrange these 10 letters and this is the number of paths. numbers and m~ n, and p are nonnegative integers, bj to (a m,b+ c +n times, while those for j and k are py';·rut.PI'I 10-5+ 1 = 6 o ) we the instrudio:o.s in. k ............ '1-'''', resPei:trv'elY, 5 29. (3) & (b) By rrue product print statement is executed x 6 x 8 = 576 times. five '.<>1'.1':,0,..., X 1 x 1 x 1 = 263 x1x1= letters. are 26x26x (b) When letters may not appear more than two times, there are 26 x 25 x 24 = 15,600 palindromes for either five or six letters. 31. By rule product are (a) 9 X 9 X 8 x 7 x 6 x 5 = 136,080 six-digit integers with no leading zeros and no repeated digit. (b) When digits may he repeated there are 9 X 105 such six-digit integers. (i) (a) (9 x 8 x 7 x 6 x 5 x 1) (for the integers euding in 0) (8 x 8 x 7 x 6 x 5 x 4) (for the integers ending in 2,4,6, or 8) = 68,800. (b) When the digits may be repeated there are 9 x 10 x 10 x 10 x 10 x 5 = 450,000 six-digit even integers. (ii) (a) (9 X 8 x 7 x 6 x 5 x 1) (for the integers ending in 0) + (8 x 8 x 7 X 6 x 5 x 1) (for the integers ending in 5) = 28,560. (b) 9 x 10 x 10 x 10 x 10 x 2 = 180,000. (iii) We use the fact that an integer is divisible by 4 if only if the integer formed by the last. two digits is divisible by 4. (a) (8 x 7 x 6 x 5 x 6) (last two digits are 04, 08, 20, 40, 60, or 80) + (7 x 7 x 6 x 5 x 16) (last two digits are 12, 16, 24, 28, 32, 36, 48, 52, 56, 64, 68, 72, 76, 84, 92, or 96) = 33,600. (b) 9 x 10 x 10 x 10 x 25 = 225, O~~. 32. (a) For positive integers n, k, where n = 3k, n!/(3!)k is the number of ways to arrange the n objects Xl! Xt, Xb Xz, X2, X2,' .• ,Xk, Xk, XI;. This must be an integer. (b) If n,k are positive integers with n = mk, then n!/(m!)" is an integer. 33. (a) With 2 choices per question there are 210 = 1024 to answer the examination. (b) Now there are 3 choices per question and 310 ways. 34. (41/2!) (No 7'8) (4!) (One 7 and one 3) + (2)(4!/21) (One 7 all.d two 3's) (4!/2!) (Two 7'13 and no 3's) (2)(41/20 (Two 7'8 and one 3) + (41/(2121» (Two 7'8 and two 3'15). The total gives us 1.02 such four-digit Intc~l!elrS (a) 6! 36. Aon 6 38. The nine women can be situated around the table in 8! Each such arrangement 39. 1. 2. provides nine spaces (between women) where °a man can placed. VVe can of these places situate a man each of them (:)6! = {). 8 . 7· 6 . 5· 4 ways. Consequently, seating arrangements the 18 (:) 6! = 2,438, 553, 600. SumOfFad( i, sum: positive integers; j,k: nonnegative integers; factorial: array [0 .. 9] of positive integers) begin factorial [0] := 1 for i := 1 to 9 do factorial [~1 : = i * factorial [i - 1] for i := 1 to 9 do for j := 0 to 9 do end for k := 0 to 9 do begin sum := factorial [iJ + factorial [y] factorial [kl if (100 :+: i + 10 * j + k) = sum then print (100 * i + 10 * j + k) end The unique answer is 145 since (II) + (41) + (5!) = 1 24 120 = 145. Sedion 1.3 -- -- - -. a b b c c e a c b d c f a d b e d e a e b f d f a f c d e f Order is not relevant can selection in 5 - = (10)(9)(8)(7)/(4)(3)(2)(1) = 210 (b) = 12!/(7!5!) == (12)(11)( 7 ways. (c) C(14, = 14!j(1212!) = (14)(13)!{2)(1) c::; 91 (d) G!) = 151/(10!51) = (15)(14)(13)(12)(11)/(5)(4)(3)(2)(1) = 3003 4. (a) -1= + (:) (:) = 31 5. (a) are peS,3) = S!j(5 - = 51/2! = (5)(4)(3) = 60 permutations size 3 for the 6. five letters l, a, f, and t. (b) There are C(5, 3) = S!j[3!{5 - 3)IJ = 5!/(312!) = combinations of size 3 for the five letters m, l', a, f, and t. They are a,f,m a,r ,t a,f,r f,m,r a,f,t f,m,t a,m,r f,r,t a,m,t m,r,t (;) (n ~ 1) = (~)(n)(n _ 1) (~)(n - l)(n - 2) = (~)(n -l)[n + (n - 2)J = n)(n - 1)(2n - 2) = (n - 1)2. 7. (a) (~) (b)eaO) (~) 11. (c) C20) G~)(2 women) (~O) (~O) (4 women) ... + G~) e!O) (10 women) = Ef=l (;~) (121~2i) (d) e:) C50) (7 women) + (~O) (::) (8 women) + e:) (~) (9 women) + G~) (;0) (10 women) = C?) (l;~i)' (e) E!!s eiO) (li~i) (b) (!) (~8) (c) e1 3) (!) (~) (d) (:) (;) (f) (~3) (!) C12) (~) = 3744 (Division by 2 is needed since no distinction is made for the order are result 54, = 1 (!) (~) -3744 = + , r, 1 S (:) (four six) = (15)(4) ways. set G) ways. vOllSe<luelllUJI the 12 8 14. .l (b) 10 = (1 = 97 -1) = (c) }J1 +(- i",{l 2'1 (._- 6 + _m 1) = =2+0+2+0+2+0+2+0+2+0+2= + ~)( = -1 + 2 - 3 + 4 - 5 + 6 = 3 i;:::l n i + 1 i=O n + i 7 (b) L>~ i;;;;;l + 1 )' + 1, one + 9 -- 2--1 0+1 + (;~) - an even locations for (~~) ways for 0 < i < 5. Then for the positions selected there are tvvo choices; for the 10 - . 'C.u,~C:WJ,,,,.uJ'5 positions there are also two choices - 1,3. 20. (a) We can select 3 vertices from A, B, C, D, E, F, G, H in (:) ways, so there are (:) = 56 distinct inscribed triangles. (b) (:) = 70 quadrilaterals. (c) total number of polygons is (~) (:) (:) (:) (~) + (:) = 28 - [(~) (~) + (~) J = 256 - [1 8 + 28] = 219. 21. There are (;) triangles if sides of the n-gon may be used. Of (;) triangles, when n 4 there al'e n triangles that use two sides of the n-gon and n(n - 4) trian~les that use only one side. So if the sides of the n-gon cannot be used, then there are G) - n - n( n - 4), n 2 4, triangles. 22. (a) From the rule of product it follows that there are 4 x 4 x 6 = 96 terms in the complete expansion of (a + b + c + d)( e f 9 + h)( 'It + V w x y + z). (b) The terms bvx and egu do not occur as summands in this expansion. 23. (a) en (b) e~2)(23) (c) Let a = 2x and b = -3y. By the binomial theorem the coefficient of a9b3 in the expansion of (a + b)12 is (~). But e;n a9b3= (~2)(2x)9(_3y)3= (~)(29)(_3)3x9y3,so the cient of x9y3 is e:)(29 )( _3)3, (a) (1'~'2) = 12 ( 4. ) - 12 0,1,1,2 - (c) (1,i,2)(!~)( -1)( -1)2 = (d) (1,:,2)<-2)(3)2 = -216 (3,2~1,Z) (d) 4/' TO 1 1 n (n) 28. a) E =- = f E . =2n/nl i=O n! n·i=o ; 1 n . (n) 1 =- = f E(--lt : = - n. i=O ~ 29. ( m+n) _ (m+n)! _ (m+n)! _ n m - n m!n! - m!(n-l)! - ( 1) (m+n)! ( 1) (m+",)! ( m (m+1)(m!)(n-l)! = m (m+l)!(n-l)! = m (m+n) m+l The sum is the binomial expansion of + 2)n = 3"', 31. (a) 1=[(1 x)- =(1+x)n_-(7) 1 x)n-1 (;)x2(1 x)",-2_ ... (_l)n(:)xn . (b) 1=[(2 x)-(x+lW'· (c) 2'l = [(2 + x) - x]n 3 33. (a) I:(ai - ai-l) = (al - ao) (a2 - al) + (aa - (2) = as - G() 34. i:;;;:l 11, (b) E(ai - ai-d = (al - 0.0) + (a2 - al) + (as - (2) i=l an -0.0 100 1 1 1 1 1 1 1 1 (c) ~(i + 2 - i + 1) = (3 - "2) + (4 - 3) + (:5 - 4) + ... 1 1 1 - 51 -50 -25 102 -"2 = 102 = 102 ::::: 5"1- procedure Seled2(i,j: positive integers) begin for i:= 1 to 5 do for i:= i + 1 6 end begin for * := 1 to 4, do end j:= i + 1 5 Ii::= j 11 1. 2. 3. Section 1.4 Let Xi, 1 :s; i :5 5, denote the arnounts given to the five "'u.J'~'UJ.""·"'4 (a) integer Xl X2 + X3 + X4 + Xl) = 0 :5 Xi, 1 :5 i :5 5, is (5+i~-l) = G~). Here n = 5, r = 10. (b) Giving each child one dime results in the equation Xl + X2 X3 X4 X5 = 5, 0 < Xi, 1 :5 i 5. There are e+:-1 ) = (:) ways distribute the remaining five dimes. (c) Let Xs denote the for the oldest child. number of solutions to Xl + X2 Xa X4 X5 = 10, 0 :5 Xi, 1 :s; i :5 4, 2 :5 X5 is the number of solutions to Yl Yz + + Y4 + Ys = 8, O:S; Yi, 1 i :5 5, which is C'+:-1) = (~2). Let Xi, 1 i:5 5, denote the number of candy bars for the five children with Xl the number for the youngest. (Xl = 1): X2 + Xs + X4 Xs = 14. Here there are (4+~:-1) = (i:) distributions. (Xl = 2): X2 + X3 + X4 + X5 = 13. Here the number of distributions is (4+!~-1) = G:). The answer is G~) G:) by the rule of sum. (~H20-1) _. (23) 20 - 20 4. (a) (~;) (b) e1 +1 1 2 2 - 1 ) = G;) (c) There are 31 ways to have 12 cones with the same flavor. So there are (:;) - 31 ways to order the 12 cones and have at least two flavors. 5. (&) 25 1. 8. (b) For each of the n distinct objects there are two choices. If an object is not selected, then one of the n identical objects is used in the selection. This results in 21'1. possible selections of size n. (a) e+:!--l) = (;~) e+:-1) = C;) (e) X4 = OVJ'U",~V£.I":> to Ya + 'lI4 = 40, Yi (b) e+;:~-l) = (;!) (d) 1 1 12 10. Here we want the number of integer for Xl X2 X3 + X4 X.r; X6 = 100, Xi ?: 3, 1 :s; i :s; 6. (For 1 ::; i :s; 6, Xi counts the number of times the face with i dots is rolled.) This is equal to the numher of nonnegative integer solutions there are to '113 +'115+116 = > 1:S i Consequently the answer is e+:;-l) = (:;). 11. (a) ('0+55-1) = e}4) (h) ('+:-1) SC'+:-l) + 3(7+;-1) + e+~~l) = en -t 3(~O) 3(:) (~), where the first summand accounts the case where none of 1,3,7 ap~ars, the second summand for when exactly one of 1,3,7 appears once, the summand for th~ case exactly two of digits appearing once each, and the last summand for when all three appear. 12. (a) The number of solutions for Xl + X2 +.. . X5 < 40, Xi ?: 0, 1 < i 5, is the same as the number for Xl + X2 ••• + X5 < 39, Xi ?: 0, 1 :S i < 5, and this equals the number of solutions for Xl + X2 ••• + X5 + X6 = 39, Xi 2: 0, 1 :S i ::; 6. There are C,+:-l) = (::) such solutions. (b) Let 'IIi = Xi 3, 1 :S i :5 5, and consider the inequality '111 + '112 + ... + '115 :s; 54, 'IIi > O. There are in part (a)] e+::-1) = (!:) solutions. 13. (a) e+:-1 ) = G). (b) e+~-l) (container 4 has one marble) e+!-l) (container 4 has three marbles) e+~-l) (container 4 has five marbles) + (3+~-1) (container 4 has seven marbles) = Lr:o (~=~~). 14. (a) (2t4.~,O,1)(3r~(2)4 (b) The terms in the expansion have the forID vawb xCyd ze where a, h, c, d, e are nonnegative integers that sum to There are e+:-1) == e:) terms. Consider one sum dist:dbutioll - the one where shelves. Here there are 24! ways for this to happen. books any other lS are six books on tP..ach of four And we see that there a:re also 24! + Tl?, + + '114 = 20. 13 18. 19. 20. For (1) we the nonnegative 1U~"'K'C;" WI W:;t + Ws +... W19 = n -19, where Wi 0 for alll (:"::-1~)' The number of positive integer solutions equation ative integer solutions for IS number of nonneg- Z64 = n - 64, d thi . (64+(n-S4)--1) _ (n-1) an S IS (n-M) - n-64 • So (:.:-~~) = (::;4) = (n~l) and n - 19 = 63. Hence n = 82. (b) (a) There are e+:-1) = (:) solutions for Xl +X2 X3 = 6 and (4+i~-l) = (~) solutions for X4 + XI) x~ + X7 = 31, where Xi 2: 0, 1 ::; i ::; 7. By the rule of product the pair of equations has :) (~) solutions. (b) (~) (~i) Here there are r = 4 nested for loops, so 1 < m ::; k ::; j ::; i ::; 20. We are making selections, with repetition, of size r = 4 from a collection of size n = 20. Hence the print statement is executed eO+,t1) = (~3) times. Here there are r = 3 nested for loops and 1::; i ::; j < k ::; 15. So we are making selections, with repetition, of size r = 3 from a collection of size n = 15. Therefore the statement counter := COftnier + 1 is executed C5+aS-l) = en times, and the final value of the variable counteris 10+ e:) = 690. 21. The begin .. end segment executed e°",;a-l) = :3 = 220 times. execution of this segment the value of the variable Bum is i = (220)(221 )/2 = 24,310. 24. (a) for i := 0 to 10 do end for j := 0 to 10 - i do 10 . . - t - J) (b) For all 1:5 i ::; 4 = Xi + 2 2:: O. the number of integer solutions to Xl + X2 + X3 X4 = 4, where -2::; Xi for 1::; i :5 4, is the number of integer solutions to !II + !l2 + '!J3 - where !Ii 2:: 0 1 ::; i < 4. use this observation the following. procedure Selectio'n$2(i,j,k: nonnegative integers) begin for i := 0 to 12 do end for j := 0 to 12 - i do for k := 0 to 12 - i - j do print (i,j,k, 12 - i - j - k) 25. If the smmnands must all be even, then consider one such composition - say, 26. 20 = 10 + 4 + 2 + 4 = 2(5 + 2 + 1 + 2). Here we notice that 5 + 2 + 1 + 2 provides a composition 10. Further, each composition of 10, when multiplied through by 2, provides a composition 20, where each summand is even. we see the number 20, e8,(".h summand even, equals the nUlnher of compositions of 10 ~ namely, 210- 1 = 29. Consequently, 6 = 10 c) an~~enlellts that m. Consequently, a is a runs. the run we number of solutions for Xl Xz + X3 X4 = 12, whe,re Xl + xa = 5, XI, X3 > 0 and X2 X", = XZ, X4 > This number is e+~-l) e+:-1) = (!) (:) = 4·6 = Vhen the first run consists of tails we get (:) (:) = 6 . 4 = 24 arrangements. all there are 2(24) = 48 arrangements with four runs. d) If the first run starts with an H, thel1 we need the number of integer solutions for Xl + Xz + Xs + X4 + Xs = Xl + Xs + X5 = Xl) Xa, X5 > 0 and X2 + X4 = 7, Xz, X4 > O. This is e+~-l) C+:-l) = (:) (:) = 36. For the case where the first run starts with a T, the number of arrangements is e+:-1) e+;-l) = (!) = 60. hI total tha'e are 36 60 = 96 ways for these 12 t()sses to determine five runs. e) e+:-1) e+~-l) = (:) G) = 90 - the number of arrangel'uents which result in six runs, if the first run starts with an H. But this is also the number when the first run starts with a T. Consequently, six runs come about in 2·90 = 180 ways. f) 2C+:-l) e~:-1)+2e+~-1) e+:-1 ) +2(3+;-1) e+:-1)+2(4+!-1) (4+~-1)+2(5+6-1) e+~-l) = 2 L,t:::o (i~i) (6~i) = 2fl . 1 4 . () () . 15 + 4 . 20 + 1 . 15] = 420. 28. (a) For n 4, cIOn sider the strings made up of n bits - that is, a total of nO's and 1's. In particular, c()nsider those strings where there are (exactly) two ()ccurrences ()f 01. For example, if n = 6 we want to include strings such a..~ and , but not or . How many such strings are there? (b) For n ~ 6, how many strings ()f nO's and l's contain (exactly) three occurrences of 01? ( c) Provide a combinatorial proof for the foll()wing: For n ~ 1, 2ft = (n ~ 1) + (n 3 1) ( a) type of :1::1 followed X2 followed X3 1'8 foll()wed by x" O's followed by Xs 1 '8 followed by X6 O's, where, Xs > O • ..."n",,,,.,,, the of ~J""""""""lD Y5 + Ya = n- o for 1 t 6. Us = n - 6, o 1 ~ _ (n+l) - 'i • ( C) There are strings n 1 strings where there are k followed by n ,- k for k = 0, .. '/: n. n 1 strings contain no occur:rence~ of 01, so there are 21'1, - (n 1) = - ntl) strings that contain at least one occurrence of are (n;l) strings that contain (exactly) one occurrence of 01, (nil) strings with (exactly) two occurrences, (n~l) strings with (exactly) three occurrences, ... ) and for n odd, we can have at most 1'1.;1 occurrences of 01. number of strings with occurrences of 01 is the number of integer solutions for This is the same as the number of integer solutions for 1116+1 = n - (n - 1) = 1, where !II, 112, ••• ,111'1.+1 0. This number is (n+1)+1-1) = (n+l) _ (1'1,+1) _ ( n+l ) 1 1 - n - 2( ~)+1 . (ii) n even, we can have at most ~ occurrences of The number of strings n 2" occurrences of 01 is the number of integer solutions for This is the same as the number of integer solutions for YI + Y2 +,., + YnH = n - n = 0, where Y' ~ 0 for 1 :::; i :::; n + 2. This number is (1'1.+2()) +0-1) = (1'1(,)+ 1) -_ ("n'++11 ) -_ ( 1'1,+1 ) 2(~)+1 • Consequently, . { ~;~;~: : odd follows. blO = 16796 bs)j 14(= (b) For n ;:: 0 there are bn ( = (~) such from (0,0) to (n,n). (e) n 2: 0 the move is U and the 4. (a) lis = 132 (b) bs = 5. Using the results third column of Table 1.10 we have: 123 456 6. (a) (i) 1347 2568 (b) (i) 7. There are bs( = 42) ways. 125 346 (ii) 1 2 5 7 3468 (ii) 8. (a) (i) 0 (ii) 0 (b) (i) «(ab(c(de H> «(ab)(c(de»)f) Oi) «ab((cd(e H> «ab)«cd)(ef») (iii) (a«(bc(de H> (a«(bc)(de»f» 9. (i) When n = 4 there are 14(= b4 ) such diagrams. 135 246 07 = 429 (iii) 1 2 3 5 4678 (iii) (iii) 0 (li) For any n 0, there are bn different drawings of n semicircles on and above a horizontal line, with no two semicircles intersecting. Consider, for instance, the diagram part (f) of the figure. Going from left to right, write 1 the first time you encounter a semicircle write 0 IS en(:oUltltel~ed. corresponds with the dn'wing such rlr""'i:vn~ ""u,::;<"". as 10. R R U RRR 18 Here condition is violated, for the first time, after the third U. Transform the U R +-'?RU U UUU. Here the entries up to and including the first violation remain unchanged, while those following first violation are changed: become U's and U's become R'a. This cOITesponcience sbows us that the number of paths that violate the given condition the same as the of paths up of eight U's and two R's - and there are e:) = e:) such paths. Consequently, the answer is (10) _ (10) _ lQi _ JQl _ 10!(S) _ 1O!(3} = (2) 1O! _ (1±1-3) (10) '1 8 - 7131 8!2! - 8!3! 8!3! 8 7!3! - 1+1 '1' (b) (m+n) (m+'ll) _ (m+n)! (m+n)! n - n+1 - n!m! - (n+1}!(m-l)! = (mtn)!(n+1)-(m+».)!m = (n±l-m)«m+n)!) = (n±l-m)(m+n). (n+l)!m! '11.+1 n!m! '1+1 n [Note that when m = n, this becomes (n!l)(~)' the formula for the nth Catalan number.] 11. Consider one oUlle C~!l) e~6) = n) e:) ways in which the $5 and $10 bills can be arranged - say, (*) $5, $5, $10, $5, $5, $10, $10, $10, $5, $5, $10, $10. Here we consider the six $5 bills as indistinguishable -likewise, for the six $10 bills. However, we consider the patrons as distinct. Hence, there are 6! ways for tbe six patrons, each with a $5 bill, to occupy positions 1, 2~ 4, 5, 9, and 10, in the arrangement (*). Likewise, there are 6f ways to locate the othe:r six patrons (each with a $10 hill). Consequently, here the number of arrangements is seen in Consequently, the largest UW,UVPJl. all (~2) = 495. 4. (a) e:t (b) 3 e15) :I (~) (four hymns from one book, one from each the other two) 6 e15) e:) e:) hymn from one two hymns a <:>""AJJ.J.U and third book) 3 :I ( two from each of the three books). 5. (a) 1025 (b) There are 10 choices for the first flag. For the second flag there are 11 choices: The poles with no flag, above or below the first flag on the pole where it is situated. There are 12 choices for the third choices for fourth, ... , and 34 choices for the last (25th). Hence there are (34!)/(91) possible arrangements. (c) There are 251 ways to arrange the flags. For each arrange:tnent consider the 24 spaces, one between each pair of flags. Selecting 9 of these spaces provides a distribution among the 10 flagpoles where every flagpole has at least one flag and order is relevant. Hence there are (25!)(~) such arrangements. 6. Consider the 45 heads and the 46 positions they determine: (1) One position to the left of the first head; (2) One position between the i-th head and the (i l)-st head, where 1 SiS 44; and, (3) One position to the right of the 45-th (last) head. To answer the question posed we need to select 15 of the 46 positions. This we can do in (::) ways. In an alternate way, let Xi denote the number of heads to the left of the i-th tail, for 1 siS. 15. Let X16 denote the number heads to the right of the 15th taiL Then we want the number of integer solutions for Xl + XzXa + ... + Xli; + XIS = 45, where Xl > 0, Xi6 2 0, and Xi > 0 for 2 sis 15. This is th.e number of integer solutions for 111 + Ya '1/3 ••• +1115 Y16 = 31, with Yi > 0 for 1 z 16. Consequently P(12,8) 8. ,N 9. (a) There are two blocks, only only wooden not adjacent to a (i) S12~e: there are 1 x 2 = 2 (li) Material, color: pair yields 1 X 4 = 4 such blocks. (iii) Material, shape: For this pair we obtain 1 x 5 := 5 such blocks. (iv) Size, we get 2 X 4 = 8 of the ULV .... !.O (v) Size, shape: This pair gives us 2 x 5 = 10 such blocks. (vi) Color, shape: this pair we find 4 x 5 = 20 the blocks we need count. In total there are 2 + 4 5 + 8 + 20 := 49 of blocks that differ from the large blue plfUltic hexagonal block in exactly two ways. 10. Sinc..e 'R' is the 18th letter of en = (17)(16)/2 = 136 ways. alphabet, the first and middle initials can be chosen in Alternately, since 'R' is the 18th letter of the alphabet, consider what happens when the middle initial is any letter between 'B' and 'Q'. For middle initial 'Q' there are 16 possible first initials. For middle initial 'P' there are 15 possible choices. Continuing back to 'B' where there is only one choice (namely' A') for the first initial, we that the total number of choices is 1 + 2 + 3 15 16 = (16)(17)/2 = 136. 11. The number of linear arrangements of the 11 horses is 11!/(513!31). Each circular arrangement represents 11Unear arrangements, so there are (1/11)[111/(5!313!)J ways to arrange the horses on the carousel. 12. (a) P(16,12) 13. (a) (i) (!) e) (!) + (!) (~) (D + G) (iii) (b) (i) (n (!) (!) (~) (b) (;2) P(15, 10) (ii) e+:-1) + e+;-l) C'+;-1) e+:-1):= (!) + (:) + (~) (;) + (~) - 9 (ii) and (iii) (~) e+:-1) e+;-l) (~) = (D (:) + G) (:). 14. (a) there are no restrictions Mr. Kelly can the a8sigmnenis 12! = 479,001,600 UGAU."O can in 4 x 3 = 12 ways, the assigned in 10! ways. Consequently, in Mr. 348,364,800. 13. (a) can be arranged as a decreasing :l:O'!.U'-(l1f!lt UM,"-'.",,"'oI. 'To complete the solution we ZIlust account for the decreasing four-digit integers where the units digit is are (:) = 84 of these. . Consequently there are 2 (!) (:) = 343 such four-digit integers. (b) For each ~ondecrea8ing four-digit integer we . four nonzero digits, with repetitions allowed. These four digits can be selected e+!-l) = en ways. And these same four digits account for a nonincreasing four-digit integer, So at this point we have 2cn - 9 of the four-digit integers we waut to count. (The reason we subtract 9 because we have counted the nine integers 2222,3333, .. " 9999 twice 2(~2).) We have not accounted for those nonincreasing four-digit integers where the units digit is O. There are Cil+3S-1) - 1 = (;2) - 1 of these four-digit integers. (Here we subtracted 1 since we do not want to include 0000.) Therefore there are [2C42) - 9} + {(;2) -- 1] = [2e,n (~)] - 10 = 1200 such four-digit integers. 16. (a) (~,~,2)(1/2)2( _3)2 = 135/2 (b) Each term is of the form :ent yn2 zrl.S where each ni, 1 < i :s; 3, is a nonnegative integer and nl + n2 + n3 = 5. Consequently, there are e+:-1) = G) terms. e c ) Replace x, y, and z by 1. Then the sum of all the coefficients in the expansion is «1/2) + 1 - 3)5 = (-3/2)5. 17. (a) First place person A at the table. There are five distinguishable places available for A (e.g., any of the positions occupied by A,B,C,D,E in Fig. 1.11(a». Then position the other nine people relative to A. This can be done in 9! ways, so there are (5)(91) seating arrangements. (b) There are three distinct ways to position A,B 80 that are seated on longer sides table across from each other. other eight people can then be 8! different ways, so the total nw::-qber of arrangements is (3)(8!). 18. (a) For Xl 3''>;1 + X3 = 6 are e+:-1 ) = (:)nonnegative ultel:€~' Xl X2 X3:= 6 X2 X4 = 15, solutions for X4 - . The number of <>'-P .... ",."" ... '''' of scores for each set scores to can win sets e) ways, soores can be """I"nr-d"l1'>F1 So if A wins in four or five the scores can be recorded in [(;) Since B may be the winner, the final answer is 2[(~)74 (~)75]. (~)74 ways. (:) 75 ] ways. 20. We can choose r objects from ,n in (:) ways. Once the r objects are selected they can be' arranged a circle (1" - 1)! ways. So there are (~) circular arrangements of the n objects taken 1" at a 21. For every positive integer n, 0 == (1 - l)n = (~)(1)o - (~)(1)1 + (;)(1Y' """' (;)(1)3 + ... (-l)n(:)(l)and (~)+(~) (~)+ ... =(7)+(;) (~) 22. (a) 7!/3! (b) 5! (c) (~)(4!) 23. (a) There are P(20, 12) == 2~! = (20)(19)(18)··· (11)(10)(9) ways in which Francesca can fill her bookshelf. (b)' There are en ways in which Francesca can select nine othe~ books. Then she can arrange those nine books and the three books on tennis on her bookshelf in 12! ways. Consequently, among the arrangements