Concept
How many groups of three to five people contain at least one child and one adult?
Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1
"When it’s finally time to go trick-or-treating, we join up with our next-door neighbors and split up the families into somewhat haphazard groups. There are eleven total children, and six adults. Now let’s say each group must have between 3 and 5 members, and must have at least one adult (to stay safe) and at least one kid (otherwise what’s the point?) How many different groups are possible? Ignoring the at-least-one-child-and-adult constraint for the moment, the total number of groups would seem to be (17 choose 3) + (17 choose 4) + (17 choose 5) = 680 + 2380 + 6188 = 9,248 possible groups. But of course this is an overcount, since it includes groups with no children and groups with no adults. We’ll use the trick from p. 144 to subtract those out. How many size-3-to-5 groups with no adults (all kids) are there? (11 choose 3) + (11 choose 4) + (11 choose 5) = 957. And how many size-3-to-5 groups with no kids (all adults)? (6 choose 3) + (6 choose 4) + (6 choose 5) = 41. Therefore, by the p. 144 trick, the total number of legal groups is 9248 − 957 − 41 = 8,250. Final answer."
Related Ideas
- What is the formula for combinations, and why are they called binomial coefficients?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What are the three basic situations behind most counting problems?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How can overcounting permutations help us count combinations?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How can choosing players be equivalent to choosing non-players?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- When are the numbers of combinations greatest and smallest?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How does the multiplication principle count costume choices with optional or unlimited accessories?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is a permutation, and how is the factorial used to count permutations?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How are partial permutations counted when only some items are selected?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1