Practice Problems on Counting subsets of sets
By Steve Mussmann, proud Member of the Math Squad.
The tutorial for this set of problems can be found here. The answers are at the end of this article.
Questions
1. A bookstore has a selection of 10 books for free. However, any customer is allowed only 3 books. How many ways can a customer choose 3 books?
2. A car race has 8 contestants. A record keeper writes down the car names as they cross the finish line. How many possible ways could the race turn out?
3. Your house has 10 (different) paintings that you are packing. You have 2 (identical) burlap bags that can each hold 3 paintings and a box that can hold 4 paintings. How many ways can you pack the paintings?
4. You are planning a vacation for 6 days. You can either spend 2 days each at 3 destinations or 3 days each at 2 destinations. There are 12 destinations in your surroundings.
- a:How many different vacation plans are there?
- b:You can't make up your mind so you write down all possibilities on slips of paper, put them in a (big) box, and draw one. What is the probability that the drawn vacation plan only includes 2 destinations?
5. In a variation of chess, the 16 pieces are randomly arranged in the two back rows of the board. A chess set has 8 pawns, 2 rooks, 2 knights, 2 bishops, a queen, and a king.
- a. What is the probability of getting the standard setup?
- b. What is the probability of getting the pawns all in the front row?
6. Suppose you are playing 5 card poker.
- a. What is the probability of getting a four of a kind?
- b. What is the probability of getting a two pair (and nothing better)?
7. A fun-size bag of M&M's has 15 M&M's. There are 5 red, 3 green, 3 blue, 2 yellow, 1 brown, and 1 orange.
- a. You randomly take 3 M&M's. What is the probability that all 3 are red?
- b. You randomly take 3 M&M's. What is the probability that 1 is red, 1 is green, and 1 is blue?
- c. You randomly take a subset of at least size 3 from the M&M's. What is the probability that the subset only contains red, green, and blue M&M's?
- d. You randomly take a subset of at least size 3 from the M&M's. What is the probability that all 3 green M&M's are included in the subset?
8. A movie theater has 9 showings in a day. The theater will be playing 3 new movies. There will be 5 showings of one movie, 3 showings of another, and just one showing of the third.
- a. How many ways are there to organize the showings?
- b. Suppose the manager enjoys making completely arbitrary decisions for the showings. What is the probability that no movie is played in consecutive showings?
Answers
1. This is equivalent to taking a subset of size 3 without order from a set of size 10. So the number of choices is,
$ {10 \choose 3} = \frac{10!}{3! 7!} = 120 $
2. This is equivalent to finding all permutations of size 8 which is $ 8! = 40320 $
3. This is equivalent to partitioning a set of size 10 into 2 subsets of size 3 and a subset of size 4 where two of the subsets are indistinguishable. So the number of ways is,
$ \frac{1}{2!} {10 \choose 3,3,4} = \frac{10!}{2! 3! 3! 4!} = 2100 $
4.a. We will proceed by counting the number of vacations with two destinations and counting the number of vacations with three destinations and then add the numbers. If we only go to two destinations, this is equivalent to taking a subset of size 2 with order from a set of size 12. So the number of options with two destinations is,
$ P^{12}_2 = \frac{12!}{10!} = 132 $
If we go to three destinations, in the same way, the number of options is,
$ P^{12}_3 = \frac{12!}{9!} = 1320 $
So the total number of vacation plans is $ 132 + 1320 = 1452 $
4.b. The sample set S is all vacation plans and the event A is all vacation plans with only 2 destinations.
$ P(A) = \frac{|A|}{|S|} = \frac{132}{1452} = \frac{1}{11} $
5.a. The sample set S is all random setups and the event A is the standard setup is chosen so $ |A|=1 $.
We can think of the 16 squares in the back two rows as a set and divide them up into subsets where each subset has the same type of piece placed. Thus, the size of S is the same as the number of partitions of a set of size 16 into subsets of size 8, 2, 2, 2, 1, and 1. So,
$ |S| = \frac{16!}{8! 2! 2! 2! 1! 1!} = 64864800 $
$ P(A) = \frac{|A|}{|S|} = \frac{1}{64864800} $
5.b. I will solve this two different ways.
First, we could lay out the 16 pieces and then choose 8 pieces for the front row. Let the sample set S be the choices for the front row. Let A be the choices that have the all pawns in the front row, so $ |A|=1 $.
$ |S| = { 16 \choose 8 } = \frac{16!}{8! 8!} = 12870 $
$ P(A) = \frac{|A|}{|S|} = \frac{1}{12870} $
Secondly, we could define S as in part a. So the size of A would be the number of ways to organize the back row with non-pawn pieces which is the number of partitions of a set of size 8 into subsets of size 2, 2, 2, 1, and 1. So,
$ |A| = {8 \choose 2,2,2,1,1} = \frac{8!}{2! 2! 2! 1! 1!} = 5040 $
$ P(A) = \frac{|A|}{|S|} = \frac{5040}{64864800} = \frac{1}{12870} $
6.a. Let S be the sample space of all hands without order. So we are choosing 5 cards from 52 cards without order.
$ |S| = {52 \choose 5} = 2598960 $
Let A be the event of a four of a kind. There are 13 options for the suit of the four of a kind, and once the four cards are chosen, there are 48 options for the last card. So,
$ |A| = 13 \times 48 = 624 $
$ P(A) = \frac{|A|}{|S|} = \frac{624}{2598960} = \frac{1}{4165} $
6.b. Let S be the sample space of all hands without order. So once again, $ |S| = 2598960 $
Let A be the event of a two pair and nothing better. So from the 13 different kinds we need to choose a subset of 3 with order and 2 indistinguishable (the two suits with pairs). Once we choose the suits, we need to choose 1 or 2 cards without order from the 4 suits. So,
$ |A| = \frac{1}{2!} P^{13}_3 \times {4 \choose 2} {4 \choose 2} {4 \choose 1} = \frac{13!}{2! 10!} \frac{(4!)^3}{(2!)^4 1! 3!} = 123552 $
$ P(A) = \frac{|A|}{|S|} = \frac{123552}{2598960} = \frac{198}{4165} $
7.a. Let us assign each us the M&M's a unique "ID". Let S be the sample space of all possible choices of 3 M&M's. So,
$ |S| = {15 \choose 3} = \frac{15!}{12! 3!} = 455 $
Let A be the event that the 3 chosen M&M's are all red. Since there are 5 M&M's to choose from,
$ |A| = {5 \choose 3} = \frac{5!}{3!2!} = 10 $
$ P(A) = \frac{|A|}{|S|} = \frac{10}{455} = \frac{2}{91} $
7.b. Let S be defined as in part a, so $ |S| = 455 $
Let A be the desired event. Since there are 5 reds and 3 of the other two types and we need one of each,
$ |A| = {5 \choose 1} \times {3 \choose 1} \times {3 \choose 1} = 5 \times 3 \times 3 = 45 $
$ P(A) = \frac{|A|}{|S|} = \frac{45}{455} = \frac{9}{91} $
7.c. Let S be the sample space of all subsets of size at least three. In order to calculate this, let us calculate the total number of subsets (partitions into 2 subsets, in and out) and subtract the number of subsets of size 0, 1, or 2.
$ |S| = 2^{15} - {15 \choose 0} - {15 \choose 1} - {15 \choose 2} = 32768 - 1 - 15 - 105 = 32647 $
Let A be the event that the subset is completely composed of red, green, and blue M&M's. So let us calculate the number of subsets of size at least 3 (as before) from the 11 M&M's of the desired colors.
$ |A| = 2^{11} - {11 \choose 0} - {11 \choose 1} - {11 \choose 2} = 2048 - 1 - 11 - 55 = 1981 $
$ P(A) = \frac{|A|}{|S|} = \frac{1981}{32647} $
7.d. Let S be defined as in part c, so $ |S| = 32647 $
Let A be the event that the subset has all 3 green M&M's. So the size of A is the same as the size of all possible subsets of the 12 non-green M&M's. So,
$ |A| = 2^{12} = 4096 $
$ P(A) = \frac{|A|}{|S|} = \frac{4096}{32647} $
8.a. Think of the 9 showing times as a set that we will partition into three subsets, where each subset is defined by the show times that play a given movie. So the number of ways to show the movies is the number of ways to partition a set of size 9 into subsets of sizes 5, 3, and 1. So the number of ways is,
$ {9 \choose 5,3,1} = \frac{9!}{5!3!1!} = 504 $
8.b. Let S be the sample set of all possible ways of showing the movies. From part a, $ |S| = 504 $.
Let A be the event that there are no consecutive movies. Since over half (5 of 9) of the movies are of one type, there is only one possibility for the placement of those 5 movies. So the size of A is the number of ways to partition the remaining showing times into the two remaining movies which is the number of ways to partition a set of size 4 into subsets of sizes 3 and 1. So,
$ |A| = {4 \choose 3,1} = \frac{4!}{3!1!} = 4 $
$ P(A) = \frac{|A|}{|S|} = \frac{4}{504} = \frac{1}{126} $
