[10] (a) How many codewords of length 10 can be constructed which don't start with 5?
Answer: 4*59 = 7,812,500
[15] (b) How many codewords of length n have exactly two different digits?
Answer: C(5,2)*(2n-2)
[15] (c) How many codewords of length 10 use exactly five of one digit, three of a second digit, and two of a third digit?
Answer: C(10;5,3,2)*53 = 302,400
[20] 2. Find and prove combinatorially an explicit formula for: Sum k=0nC(n,k)2.
Answer: There are C(2n,n) ways of choosing n objects from among a collection of 2n distinct objects. This number can also be enumerated by dividing the 2n objects into two equal-sized subsets A and B, and counting ways of choosing k objects from A, namely C(n,k), while rejecting k objects from B, namely C(n,k). By the sum and product rules, this works out to the desired sum.
[20] 3. There are 16 students in the swim class. Find the number of ways to pair off all the children into "buddies" for an exercise.
Answer: Order the children arbitrarily. You then have 15 choices for the first child's buddy, 13 for the next unbuddied child's buddy, and so on down to one choice for the last unbuddied child's buddy. By the product rule, the total number of ways is thus 15*13*11*9*7*5*3*1 = 2,027,025. Some other ways of working this out are: C(16,2)*C(14,2)...C(2,2)/8! = C(16,8)*8!/28 = 16!/8!28.
[20] 4. How many arrangements of LISITANNY are there in which the letters N are separate (that is, the two N's do not appear side by side).
Answer: There are C(9;1,1,1,1,1,2,2) = 90,720 ways in which the given letters can be arranged, of which C(8;1,1,1,1,1,1,2) = 20,160 involve placing the N's beside each other. The answer is therefore 90,720-20,160 = 70,560. The answer can also be worked out as C(8,2)*7!/2! = 14*7! = C(8,2)*C(7,2)*5!.