Homework 3 solutions
a) There are 12 months (boxes), 240 people (balls):
b) There are 52 weeks in a year (boxes):
c) There are 7 days in a week (boxes):
In the worst case, you will pick out 4 of each color before you get the 5th one.
5+5+5+5+1 = 21 or 4+4+4+4+4+1=21
a) This is a permutation or multiplication rule. P(9,5) = 9 x 8 x 7 x 6 x 5 = 15120
b) Method 1: The 7 and the 2 must be the 5 digit number. There are 5 ways to pick a spot for the 7. Then there are 4 ways to pick a spot for the 2. That leaves 3 free spots to be occupied by the leftover numbers 1,3,4,5,6,8,9: P(7,3) = 7 x 6 x 5
Answer: 5 x 4 x P(7,3) = 4200
Method 2: We can find the complement. A = contains a 7, B = contains a 2
We want |(A ∩ B)|. Its complement is |(AC È BC)| = |AC| + |BC| - |AC∩ BC|
|AC| = do not contain 7 = P(8,5) = 8 x 7 x 6 x 5 x 4 = 6720
|BC| = do not contain 2 = P(8,5) = 6720
|AC∩ BC| = do not contain 7 and 2 = P(7,5) = 7 x 6 x 5 x 4 x 3 = 2520
|(A ∩ B)| = Total – complement = 15120 – (6720 + 6720 – 2520) = 4200
c) Treat 27 or 72 as one number. Since 27 or 72 must appear in the 5 digit number, you have 4 choices for its position and 2! arrangements for the 2 and the 7. That leaves 3 free spots for the remaining numbers to be chosen from 1,3,4,5,6,8,9. This is P(7,3) = 7 x 6 x 5
Answer: 2!x4 x P(7,3) = 1680
a) Combinations: chose 6 people out of 20: C(20,6) =
b) Choose 3 men out of 8 and choose 3 women out of 12:
c) 5 cases: 2 women, 4 men; 3 women, 3 men; 4 women, 2 men; 5 women, 1 man, 6 women, 0 men
You can also look at the complement so reduce the number of computations: at most 1 woman on the committee:
Answer: Total – complement = 38760 – 700 = 38060
a) These are circular permutations: (n - 1)! 7! = 5040
b) Treat the couple as one person: 6! = 720 and there are 2 ways to arrange the couple.
Ans: 2! x 6! = 2 x 720 = 1440
Permutation with repetitions. There are 14 letters, 5 S’s, 2 A’s, 2 T’s
a) Combinations with repetitions: n = 20 types, k = 15
b) Combinations with repetitions and restriction: n = 20, k = 15, s1= 1
a)
b) 5th term is found by letting k = 4;
c) We need to find k such that we get x16
a) largest term is 7n3 which has the same order as n3
b) largest term is 6nn which has the same order as nn
c) largest term is 2n, order is 2n
d) 67 has the same order as 1
e) n! is the largest term
f) Multiplying out we get ; in the numerator the largest term is n3log n and in the denominator the largest term is n3. All the other terms don’t matter as n becomes large. So it simplifies to
So it has the same order as log n.