Exercises on Counting Principles and Assignments

1 Chapter 1 Problems 1 a By the generalized basic principle of counting there are 26 26 10 10 10 10 10 67600000 b 26 25 10 9 8 7 6 19656000 2 64 1296 3 An assignment is a sequence i1 i20 where ij is the job to which person j is assigned Since only one person can be assigned to a job it follows that the sequence is a permutation of the numbers 1 20 and so there are 20 different possible assignments 4 There are 4 possible arrangements By assigning instruments to Jay Jack John and Jim in that order we see by the generalized basic principle that there are 2 1 2 1 4 possibilities 5 There were 8 2 9 144 possible codes There were 1 2 9 18 that started with a 4 6 Each kitten can be identified by a code number i j k l where each of i j k l is any of the numbers from 1 to 7 The number i represents which wife is carrying the kitten j then represents which of that wifes 7 sacks contain the kitten k represents which of the 7 cats in sack j of wife i is the mother of the kitten and l represents the number of the kitten of cat k in sack j of wife i By the generalized principle there are thus 7 7 7 7 2401 kittens 7 a 6 720 b 2 3 3 72 c 43 144 d 6 3 2 2 1 1 72 8 a 5 120 b 7 22 1260 c 11 442 34650 d 7 22 1260 9 12 64 27720 10 a 8 40320 b 2 7 10080 c 54 2880 d 424 384 Copyright 2010 Pearson Education Inc Publishing as Prentice Hall 2 Chapter 1 11 a 6 b 323 c 34 12 a 305 b 30 29 28 27 26 13 20 2 14 52 5 15 There are 10 12 5 5 possible choices of the 5 men and 5 women They can then be paired up in 5 ways since if we arbitrarily order the men then the first man can be paired with any of the 5 women the next with any of the remaining 4 and so on Hence there are 10 12 5 5 5 possible results 16 a 6 7 4 2 2 2 42 possibilities b There are 6 7 choices of a math and a science book 6 4 choices of a math and an economics book and 7 4 choices of a science and an economics book Hence there are 94 possible choices 17 The first gift can go to any of the 10 children the second to any of the remaining 9 children and so on Hence there are 10 9 8 5 4 604800 possibilities 18 5 6 4 2 2 3 600 19 a There are 8 4 8 2 4 3 3 3 1 2 896 possible committees There are 8 4 3 3 that do not contain either of the 2 men and there are 8 2 4 3 1 2 that contain exactly 1 of them b There are 6 6 2 6 6 3 3 1 2 3 1000 possible committees Copyright 2010 Pearson Education Inc Publishing as Prentice Hall Chapter 1 3 c There are 7 5 7 5 7 5 3 3 2 3 3 2 910 possible committees There are 7 5 3 3 in which neither feuding party serves 7 5 2 3 in which the feuding women serves and 7 5 3 2 in which the feuding man serves 20 6 2 6 6 6 5 1 4 5 3 21 7 34 35 Each path is a linear arrangement of 4 rs and 3 us r for right and u for up For instance the arrangement r r u u r r u specifies the path whose first 2 steps are to the right next 2 steps are up next 2 are to the right and final step is up 22 There are 4 22 paths from A to the circled point and 3 21 paths from the circled point to B Thus by the basic principle there are 18 different paths from A to B that go through the circled piont 23 323 25 52 13131313 27 12 12 3 4 5 345 28 Assuming teachers are distinct a 48 b 4 8 8 2222 2 2520 29 a 10342 b 3 7 3 2 42 30 2 9 228 since 2 9 is the number in which the French and English are next to each other and 228 the number in which the French and English are next to each other and the US and Russian are next to each other Copyright 2010 Pearson Education Inc Publishing as Prentice Hall 4 Chapter 1 31 a number of nonnegative integer solutions of x1 x2 x3 x4 8 Hence answer is 11 3 165 b here it is the number of positive solutionshence answer is 7 3 35 32 a number of nonnegative solutions of x1 x6 8 answer 13 5 b number of solutions of x1 x6 5 number of solutions of x1 x6 3 10 8 5 5 33 a x1 x2 x3 x4 20 x1 2 x2 2 x3 3 x4 4 Let y1 x1 1 y2 x2 1 y3 x3 2 y4 x4 3 y1 y2 y3 y4 13 yi 0 Hence there are 12 3 220 possible strategies b there are 15 2 investments only in 1 2 3 there are 14 2 investments only in 1 2 4 there are 13 2 investments only in 1 3 4 there are 13 2 investments only in 2 3 4 15 2 14 2 13 12 2 2 3 552 possibilities Copyright 2010 Pearson Education Inc Publishing as Prentice Hall Chapter 1 5 Theoretical Exercises 2 1 m i in 3 nn 1 n r 1 nn r 4 Each arrangement is determined by the choice of the r positions where the black balls are situated 5 There are n j different 0 1 vectors whose sum is j since any such vector can be characterized by a selection of j of the n indices whose values are then set equal to 1 Hence there are n j k n j vectors that meet the criterion 6 n k 7 1 1 1 n n r r 1 1 1 1 n n r n r n r r n n n r r r r n r n n 8 There are n m r gropus of size r As there are n m i r i groups of size r that consist of i men and r i women we see that 0 r i n m n m r i r i 9 0 2 n i n n n n i n i 2 0 n i n i 10 Parts a b c and d are immediate For part e we have the following n k k 1 k n n n k k n k k 1 1 n n k k 1 1 1 1 n k n n n k k n k k 1 1 n n k 1 1 1 n n n n k k n k k Copyright 2010 Pearson Education Inc Publishing as Prentice Hall 6 Chapter 1 11 The number of subsets of size k that have i as their highest numbered member is equal to 1 1 i k the number of ways of choosing k 1 of the numbers 1 i 1 Summing over i yields the number of subsets of size k 12 Number of possible selections of a committee of size k and a chairperson is n k k and so 1 n k n k k represents the desired number On the other hand the chairperson can be anyone of the n persons and then each of the other n 1 can either be on or off the committee Hence n2n 1 also represents the desired quantity i n k2 k ii n2n 1 since there are n possible choices for the combined chairperson and secretary and then each of the other n 1 can either be on or off the committee iii nn 12n 2 c From a set of n we want to choose a committee its chairperson its secretary and its treasurer possibly the same The result follows since a there are n2n 1 selections in which the chair secretary and treasurer are the same person b there are 3nn 12n 2 selection in which the chair secretary and treasurer jobs are held by 2 people c there are nn 1n 22n 3 selections in which the chair secretary and treasurer are all different d there are n k3 k selections in which the committee is of size k 13 1 1n 1 0 1 n n i n i 14 a n j n n i j i i j i b From a n j i n j j i 2 1 n n i j i n n i n i j i c 1 n n j j i n j j i 1 1 n n j j i n n i i j 0 1 n i n i k k n n i i k 0 Copyright 2010 Pearson Education Inc Publishing as Prentice Hall Chapter 1 7 15 a The number of vectors that have xk j is equal to the number of vectors x1 x2 xk1 satisfying 1 xi j That is the number of vectors is equal to Hk1j and the result follows b H21 H11 1 H22 H11 H12 3 H23 H11 H12 H13 6 H24 H11 H12 H13 H14 10 H25 H11 H12 H13 H14 H15 15 H35 H21 H22 H23 H24 H25 35 16 a 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 1 2 3 1 3 2 2 3 1 1 2 3 2 1 3 3 1 2 1 2 3 b The number of outcomes in which i players tie for last place is equal to n i the number of ways to choose these i players multiplied by the number of outcomes of the remaining n i players which is clearly equal to Nn i c 1 1 n i n N n i 1 n i n N n i n i 1 0 n j n N j j where the final equality followed by letting j n i d N3 1 3N1 3N2 1 3 9 13 N4 1 4N1 6N2 4N3 75 17 A choice of r elements from a set of n elements is equivalent to breaking these elements into two subsets one of size r equal to the elements selected and the other of size n r equal to the elements not selected 18 Suppose that r labelled subsets of respective sizes n1 n2 nr are to be made up from elements 1 2 n where n 1 r i i n As 1 1 1 i r n n n n represents the number of possibilities when person n is put in subset i the result follows Copyright 2010 Pearson Education Inc Publishing as Prentice Hall 8 Chapter 1 19 By induction x1 x2 xrn 1 1 1 1 2 0 1 n i n i r i n x x x i by the Binomial theorem 1 1 1 1 0 n i i n x i 2 r i i 2 2 1 1 2 i i r r n i x x i i 2 1 r i i n i 1 r i i 1 1 1 r i i r r n x x i i 1 2 r i i i n where the second equality follows from the induction hypothesis and the last from the identity 1 1 1 2 r n n i n n i i i i i 20 The number of integer solutions of x1 xr n xi mi is the same as the number of nonnegative solutions of y1 yr n 1 r mi yi 0 Proposition 62 gives the result 1 1 1 r i n m r r 21 There are r k choices of the k of the xs to equal 0 Given this choice the other r k of the xs must be positive and sum to n By Proposition 61 there are 1 1 1 n n r k n r k such solutions Hence the result follows 22 1 1 n r n by Proposition 62 Copyright 2010 Pearson Education Inc Publishing as Prentice Hall Chapter 1 9 23 There are 1 j n j nonnegative integer solutions of 1 n i i x j Hence there are 0 1 k j j n j such vectors Copyright 2010 Pearson Education Inc Publishing as Prentice Hall