Skip to main content

Section 2.3 Counting Subsets

In Section 2.2 we counted strings and other ordered objects. How might we count the number of ways to choose some items from a set when we do not care about the order, like a group of students to work on a project? In this section, we discuss subsets and introduce the binomial coefficients that count subsets. We combine counting subsets with our other rules for counting: steps Theorem 2.2.3, cases Theorem 2.2.7, and counting the opposite Theorem 2.2.9. We also introduce our first proof format, which is for combinatorial proof.
Before we learn any new rules, try the following activity.

Activity 2.3.A Adopting two cats.

 
  1. There are five cats (\(\str{c1}\text{,}\) \(\str{c2}\text{,}\) \(\str{c3}\text{,}\) \(\str{c4}\text{,}\) \(\str{c5}\)) waiting to be adopted at the animal shelter. You want to adopt two of the cats. Make a list of possibilities. Notice that the order in which we choose the cats does not matter. For example, choosing \(\str{c2}\) and \(\str{c5}\) is the same as choosing \(\str{c5}\) and \(\str{c2}\text{.}\) For that reason, we use set notation to indicate a choice, such as \(\{\str{c2}, \str{c5}\}\text{.}\)
  2. In how many ways can you choose two cats to adopt?
  3. Betelehem tried to answer (b) without making a list. Here is her work.
    Solution.
    We will count the possibilities using steps.
    Step 1: Choose the first cat. (5 ways)
    Step 2: Choose the second cat. Note that the second cat must be a different cat from the first cat. (4 ways)
    Since steps multiply Theorem 2.2.3, there must be \(5 \times 4 = 20\) ways to adopt two cats.
    Uh oh! The correct answer is ten, so Betelehem’s answer is incorrect. (Hint: If you also had 20, you should go back and fix your work.) What went wrong? Explain. Hint: Betelehem’s answer is exactly twice (\(\times 2\)) the correct answer, so she must have double counted (counted each pair twice).
  4. If there were \(k\) cats and you wanted to adopt two cats, how many possibilities are there? Hint: You can use Betelehem’s approach as long as you remember that you will get twice the correct answer. Another hint: handshakes!

Subsection 2.3.A Subsets and the Binomial Coefficients

In many situations, we want to select some of the elements of a set. We can think of a set as corralling
 1 
The word corral means to collect and contain. A common usage is in reference to fencing in animals such as horses or sheep.
its elements inside a rope. For example, the set \(A=\{1,2,3,7,8\}\) is drawn in Figure 2.3.2. If we corral some, all, or none of the elements within \(A\text{,}\) we get a subset of \(A\text{.}\) For example, Figure 2.3.2 shows the subset \(\{2,8\}\) shaded in gray.
Figure 2.3.2. The subset \(\{2,8\}\) corrals some of the elements of the set \(A=\{1,2,3,7,8\}\text{.}\)
We formally define a subset.

Definition 2.3.3 Subsets.

 
  1. A subset of the set \(A\) is a set consisting of some of the elements of \(A\text{,}\) where the word “some” is understood to be any number of elements– from none to all. That is, the set \(T\) is a subset of the set \(A\text{,}\) denoted \(T \subseteq A\) if every element of \(T\) is also an element of \(A\text{.}\) For example, \(\{2,8\} \subseteq \{1,2,3,7,8\}\) and \(\{3\} \subseteq \{1,2,3,7,8\}\text{.}\) Note that the set \(A\) is a subset of itself. For example, \(\{1,2,3,7,8\} \subseteq \{1,2,3,7,8\}\text{.}\)
  2. The empty set \(\varnothing\) is the set with no elements. That is \(\varnothing=\{ ~\}\text{.}\) Note that \(\varnothing\) is a subset of any set. Imagine corralling no elements or drawing a shaded shape within \(A\) that contains none of the elements of \(A\text{.}\) For example, \(\varnothing \subseteq \{1,2,3,7,8\}\text{.}\)

Remark 2.3.4 Notation for zero.

Computer scientists often write the number zero with a slash to avoid confusion with the letter \(O\text{,}\) so the zero symbol in computer science looks similar to the empty set symbol \(\varnothing\text{.}\) In this textbook, we write \(0\) for the number zero (without a slash), \(\str{0}\) for the zero bit, and \(\varnothing\) for the empty set.
In Activity 2.3.A, we chose two cats from a set of five cats. It is useful to have a name for the number of ways to select exactly \(k\) objects from a set of \(n\) distinct objects.

Definition 2.3.5 Binomial coefficient.

For non-negative integers \(k\) and \(n\text{,}\)
  1. The number of ways to select a subset of \(k\) elements from a set of \(n\) elements is the binomial coefficient \(\binom{n}{k}\) which is pronounced “\(n\) choose \(k\text{.}\)” For example, “5 choose 2” is \(\binom{5}{2} = 10\) because we saw in Activity 2.3.A that there are 10 ways to select two cats from a set of five cats.
  2. Note that if \(k>n\text{,}\) then \(\binom{n}{k}=0\text{.}\)
The simplest way to evaluate a binomial coefficient is to search for it on the Internet or ask a virtual assistant. For example, search for “five choose two” and you will get ten. You can also evaluate binomial coefficients using some calculators and spreadsheet programs. Therefore, it is perfectly acceptable to leave binomial coefficients in an answer to a counting problem.

Remark 2.3.6 Not evaluating counts, version 3.

Unless stated otherwise, when counting you may leave any answer greater than twenty in a format that could easily be evaluated on a calculator. In particular, your answer may involve addition, subtraction, multiplication, division, factorials, binomial coefficients, and parentheses.
For small values, we can evaluate binomial coefficients by listing the possible subsets. As usual, working with small values can help us to understand the concept.

Example 2.3.7 Four choose \(k\).

Evaluate \(\binom{4}{k}\) for each nonnegative integer \(k\) by listing the \(k\)-element subsets of \(\{1,2,3,4\}\text{.}\)
Solution.
When \(k=0\text{,}\) the only 0-element subset is \(\varnothing\) and so \(\binom{4}{0}=1\text{.}\)
When \(k=1\text{,}\) the 1-element subsets are \(\{1\}, \{2\}, \{3\}, \{4\}\) and so \(\binom{4}{1}=4\text{.}\)
When \(k=2\text{,}\) the 2-element subsets are \(\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}\) and so \(\binom{4}{2}=6\text{.}\)
When \(k=3\text{,}\) the 3-element subsets are \(\{1,2,3\}, \{1,2,4\}, \{1,3, 4\}, \{2,3,4\}\) and so \(\binom{4}{3}=4\text{.}\)
When \(k=4\text{,}\) the only 4-element subset is \(\{1,2,3,4\}\) and so \(\binom{4}{4}=1\text{.}\)
When \(k >4\) we have \(\binom{4}{k}=0 \text{ for } k>4\text{.}\)
It is your turn to use subsets to evaluate some small binomial coefficients.

Activity 2.3.B Six choose \(k\).

 
  1. Evaluate \(\binom{6}{0}\text{,}\) \(\binom{6}{1}\text{,}\) and \(\binom{6}{6}\) by listing subsets of \(\{1,2,\ldots,6\}\text{.}\)
  2. Conjecture the values of \(\binom{n}{0}\text{,}\) \(\binom{n}{1}\text{,}\) and \(\binom{n}{n}\) where \(n\) is a positive integer.
  3. Evaluate \(\binom{6}{5}\) by listing subsets of \(\{1,2,\ldots,6\}\text{.}\) Hint: stay organized by considering which integer is not in the set.
  4. Conjecture the value of \(\binom{n}{n-1}\) where \(n\) is a positive integer.

Subsection 2.3.B Combining Counting Techniques

Many counting problems require a combination of techniques we have learned, including cases, steps, opposites, and subsets.

Example 2.3.9 Team and leader.

There are 25 students in the coding club, ten of whom are first-year students. For the coding competition, we need a team of four students that includes exactly one first-year student. How many different teams are possible?
Solution.
Since ten of the 25 students are first-year students, the other \(25-10=15\) are not first-year students. To make a team of four with exactly one first-year student, we will also need three students who are not first-year.
Step 1: Choose the first-year student. We want one first-year student out of ten, so there are \(\binom{10}{1} = 10\) ways to do this step.
Step 2: Choose the other three students. We want three students who are not first year out of 15, so there are \(\binom{15}{3}\) ways to do this step.
Since steps multiply Theorem 2.2.3, there are a total of
\begin{equation*} \binom{10}{1}\binom{15}{3} = 10\binom{15}{3} = 4,550 \end{equation*}
ways to choose a team.
Try your hand at combining these techniques.

Activity 2.3.C Adopting two animals.

There are five cats and 12 dogs waiting to be adopted.
  1. In how many ways can you choose two animals to adopt? Hint: How many animals are there?
  2. In how many ways can you choose two animals to adopt if they are both cats? Write your answer as a binomial coefficient. (Yes, we made a list and counted this same number in Activity 2.3.A).
  3. In how many ways can you choose two animals to adopt if they are both dogs?
  4. In how many ways can you choose two animals to adopt if you choose one cat and one dog?
  5. How are your answers to (b), (c), and (d) related to your answer to (a)? Use technology to evaluate the binomial coefficients.
  6. Why? Hint: Use cases.
Several exercises in this section refer to a 52-card deck of playing cards. The key facts to know are stated in the following definition.

Definition 2.3.11 52-card deck of playing cards.

 
  1. A hand is a set of cards, without regard to order. The name comes from the fact that in many card games you hold the cards in your hand. The number of cards in a hand varies depending on the game. Poker is a family of card games that often uses hands with five or seven cards, whereas Bridge is a card game that uses hands with thirteen cards.
  2. Each card in the deck has one of thirteen denominations: Ace (A), 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack (J), Queen (Q), or King (K).
  3. Each card in the deck also has one of four suits clubs \(\clubsuit\text{,}\) diamonds \(\diamondsuit\text{,}\) hearts \(\heartsuit\text{,}\) or spades \(\spadesuit\text{.}\) For example, a card might be the Jack of hearts, denoted J\(\heartsuit\text{.}\) Note that for each choice of denomination and suit, there is exactly one card with that denomination and suit. For example, there is exactly one card that is J\(\heartsuit\text{.}\)
  4. The cards with clubs and spades are black cards. The cards with diamonds and hearts are red cards.
To learn more about a standard 52-card deck of playing cards, check out Wikipedia: Standard 52-card Deck
Here is an example of counting hands.

Example 2.3.12 Three-of-a-kind.

In a 52-card deck of playing cards, how many 5-card hands have a three-of-a-kind, which is three cards of one denomination, a fourth card of a different denomination, and fifth card of another denomination.
 2 
The fourth or fifth cards cannot be the same denomination as the three-of-a-kind because that is a four-of-a-kind. The fourth and fifth cards cannot be the same denomination as each other because that is a full house.
How many different 5-card hands have a three-of-a-kind?
Solution.
Let’s build such a hand through a series of steps.
Step 1: Select the denomination of the three-of-a-kind. Since there are 13 denominations, there are \(\binom{13}{1} = 13\) ways to complete this step.
Step 2: Select the cards for the three-of-a-kind. There are four cards in the denomination we chose in Step 1 and we want three of them, so there are \(\binom{4}{3} = 4\) ways to complete this step.
Step 3: Select the denominations of the other two cards. Since there are \(13-1=12\) remaining denominations and we want two of them, there are \(\binom{12}{2}\) ways to complete this step.
Step 4: Select the cards in the other two denominations. Since there are four cards in each denomination chosen in Step 3, there are \(\binom{4}{1}\) ways to choose each. Since there are two cards and steps multiply Theorem 2.2.3, there are \(\binom{4}{1}\binom{4}{1} = 4 \times 4 = 16\) ways to complete this step, which finishes building our hand.
Since steps multiply Theorem 2.2.3, there are
\begin{equation*} \begin{aligned} \binom{13}{1}\binom{4}{3}\binom{13}{2}\binom{4}{1}\binom{4}{1} &= (13)(4)\binom{13}{2}(4)(4)\\ & =4^3(13)\binom{12}{2}\\ &=64,896 \end{aligned} \end{equation*}
ways. (Any of those formats of the answer is acceptable.)

Subsection 2.3.C Proof Format: Combinatorial Proof

Jarrett and Xueqing solve the same counting problem, but they use two different methods. They should still get the same answer, right? This observation can lead to a way to prove that two quantities are equal: Jarrett’s answer = Xueqing’s answer. This strategy might remind you of the saying “six of one, half dozen of the other” which sounds like two different quantities, but because a dozen is twelve, half a dozen is also six.
There are many different types of proof. A proof format is a structure or outline of a particular type of proof. Our first proof format is combinatorial proof, a proof that counts, in which we prove that two quantities are equal by counting the same situation using two different methods.
Whenever we introduce a new proof format, we present an example of such a proof and then ask you to write a very similar proof by copying the example proof mutatis mutandis (mm), which means changing what needs to be changed.

Activity 2.3.D Combinatorial proof — choosing two animals.

 
  1. Copy the following example of a combinatorial proof. Yes, that means copy every word. Use a combinatorial proof to prove for any positive integers \(m\) and \(n\) that
    \begin{equation*} \binom{m+n}{2} = \binom{m}{2} + \binom{n}{2} + mn \end{equation*}

    Proof.
    We use a combinatorial proof. Consider the following situation: there are \(m\) cats and \(n\) dogs and we want to adopt two animals. How many ways are there to choose the two animals?
    First, since there are a total of \(m+n\) animals and we want to choose two of them, the answer is \(\binom{m+n}{2}\text{.}\)
    On the other hand, we can consider three cases.
    Case 1: Choose two cats. In this case, we want two out of \(m\) cats, and so there are \(\binom{m}{2}\) ways to choose the two animals.
    Case 2: Choose two dogs. In this case, we want two out of \(n\) dogs, and so there are \(\binom{n}{2}\) ways to choose the two animals.
    Case 3: The only remaining case is that we choose one cat and one dog. In this case, we want one out of \(m\) cats (\(m\) ways) and then one out of \(n\) dogs (\(n\) ways).
    Since steps multiply (by Theorem 2.2.3), there are \(mn\) ways to choose the two animals.
    Since cases add (by Theorem 2.2.7), there is a total of \(\binom{m}{2} + \binom{n}{2} + mn\) ways to choose two animals.
    Since we counted the same quantity in two different ways, it follows that \(\binom{m+n}{2} =\binom{m}{2} + \binom{n}{2} + mn\)
  2. Edit the proof you copied in (a), changing what needs to be changed to prove for any positive integer \(n\) that
    \begin{equation*} \binom{2n}{2} = 2\binom{n}{2} + n^2\text{.} \end{equation*}
Here is another example of a combinatorial proof.

Example 2.3.15 Combinatorial proof — team and leader.

Use a combinatorial proof to prove that
\begin{equation*} \displaystyle 7\binom{10}{7} = 10 \binom{9}{6} \end{equation*}
Solution.
  Proof. We use a combinatorial proof. Consider the following situation: there is a group of ten employees. How many ways are there to choose seven employees to be on a project team where one member of the team is the project leader?
First, we can choose the seven-person project team from the group of ten employees. There are \(\binom{10}{7}\) ways to do this step. Then we need to choose one of those seven people on the project team to be the project leader. There are seven ways to do this step. (You could think of it as \(\binom{7}{1}\) ways, but \(\binom{7}{1}= 7\) and that is simpler.) Since steps multiply Theorem 2.2.3, the answer is \(7\binom{10}{7}\text{.}\)
On the other hand, we can make the choices in reverse order. We can start by choosing the project leader, one of the ten people. There are ten ways to do this step. Then we need to choose the rest of the project team. Since we already chose the project leader, we only need six more people out of the nine remaining people. There are \(\binom{9}{6}\) ways to do this step. Since steps multiply Theorem 2.2.3, the answer is also \(10 \binom{9}{6}\text{.}\)
Since we counted the same quantity in two different ways, it follows that \(7\binom{10}{7} = 10\binom{9}{6}\text{.}\)
In Activity 2.3.B we calculated \(\binom{6}{0}=\binom{6}{6}=1\) and \(\binom{6}{1}=\binom{6}{5}=6\text{.}\) We conjectured that for any integer \(n\) we have\(\binom{n}{0}=\binom{n}{n}=1\) and \(\binom{n}{1}=\binom{n}{n-1}=n\text{.}\) In the next proof, we use a combinatorial proof to show the symmetry of the binomial coefficients, in general.
Let’s look at a combinatorial proof of this theorem.

Example 2.3.17 Combinatorial proof — symmetry of the binomial coefficients.

Give a combinatorial proof of Theorem 2.3.16.
Solution.
Proof We use a combinatorial proof. Consider the following situation: there are \(n\) people who auditioned for a play, and we want to choose \(k\) people to be in the play. How many ways are there to do this?
First, since we want to choose \(k\) out of \(n\) people, there are \(\binom{n}{k}\) ways to select who is in the play.
On the other hand, instead of deciding who will be in the play, we can choose which people will not be in the play. There are \(n-k\) people who auditioned but will not be in the play, so there are \(\binom{n}{n-k}\) ways to select who will be in the play in this way.
Since we counted the same quantity in two different ways, it follows that \(\binom{n}{k} = \binom{n}{n-k}\text{.}\)

Subsection 2.3.D Exercises

Subsubsection Exercises for 2.3.A Subsets and the Binomial Coefficients

1. Practice.

 
  1. Evaluate \(\binom{3}{k}\) for \(k = 0, 1, 2, 3\) by listing the subsets of \(\{1,2,3\}\text{.}\)
  2. Evaluate \(\binom{2}{k}\) for \(k = 0, 1, 2\) by listing the subsets of \(\{1,2\}\text{.}\)
  3. Evaluate \(\binom{1}{k}\) for \(k = 0, 1\) by listing the subsets of \(\{1\}\text{.}\)
  4. Evaluate \(\binom{0}{k}\) for \(k = 0\) by listing the subsets of \(\varnothing\text{.}\)
Check.
  1. When \(k=0\text{,}\) the only 0-element subset is \(\varnothing\text{,}\) and so \(\binom{3}{0}=1\text{.}\) When \(k=1\text{,}\) the 1-element subsets are \(\{1\}\text{,}\) \(\{2\}\text{,}\) and \(\{3\}\text{,}\) and so \(\binom{3}{1}=3\text{.}\) When \(k-2\text{,}\) the 2-element subsets are \(\{1,2\}\text{,}\) \(\{1,3\}\text{,}\) and \(\{2,3\}\text{,}\) and so \(\binom{3}{2}=3\text{.}\) When \(k=3\text{,}\) the only 3-element subset is \(\{1,2,3\}\text{,}\) and so \(\binom{3}{3}=1\text{.}\)
  2. Hint: You should get \(\binom{2}{0}=1\text{,}\) \(\binom{2}{1}=2\text{,}\) and \(\binom{2}{2}=1\text{.}\)
  3. Hint: The only subsets of \(\{1\}\) are \(\varnothing\) and \(\{1\}\text{.}\)
  4. Hint: The only subset of \(\varnothing\) is \(\varnothing\text{.}\)

2. Practice.

There are five courses that I would like to take this semester: Architectural drawing (A), bioinformatics (B), computational theory (C), differential equations (D), and ecological models (E).
  1. If I can take three of these courses, what are my options? List them.
  2. If I can take four of these courses, what are my options? List them.
  3. Based on your answers, evaluate \(\binom{5}{3}\) and \(\binom{5}{4}\) and check your answers using technology.

3. Practice.

The library’s new arrivals section offers 24 mystery novels, 50 young adult novels, 17 biographies, and 46 fantasy novels. In each part of this problem, your answer should be a binomial coefficient.
  1. In how many ways can I choose two young adult novels for my niece?
  2. In how many ways can I choose three mystery novels to take on vacation?
  3. My brother likes to read biographies, but he also likes fantasy novels. In how many ways can I choose four books to bring him?
Check.
  1. \(\displaystyle \binom{50}{2}\)
  2. \(\displaystyle \binom{24}{3}\)
  3. Hint: choose four out of \(17 + 46 = 63\) books.

4. Understand.

Explain how to evaluate each quantity involving a positive integer \(n\) by explicitly discussing the subsets of \(S = \{1,2,3,4,\ldots, n\}\text{.}\)
  1. \(\displaystyle \binom{n}{0}\)
  2. \(\displaystyle \binom{n}{1}\)
  3. \(\displaystyle \binom{n}{n}\)
Check.
  1. Hint: The only 0-element subset is \(\varnothing\text{.}\)
  2. Hint: \(\binom{n}{1}=n\text{.}\)
  3. Hint: The only \(n\)-element subset is \(S\text{.}\)

5. Recap.

Do you know …
  1. How to pronounce \(\binom{n}{k}\text{?}\)
  2. What \(\binom{n}{k}\) counts?
  3. How to evaluate \(\binom{n}{k}\) for small values of \(n\) by listing subsets?

Subsubsection Exercises for 2.3.B Combining Counting Techniques

6. Practice.

This problem refers to the 52-card deck of playing cards in Definition 2.3.11.
  1. How many different ways are there to deal a hand of five cards?
  2. How many different hands have all five cards of the same suit? Hint: First choose one of the four suits and then choose the cards. There are 13 cards in each suit.
Check.
  1. Hint: Choose five out of 52.
  2. \(\displaystyle 4\binom{13}{5}\)

7. Practice.

There are usually 16 players on a Division III volleyball team. Of those, six players are starters, which means that they are on the court when the game starts. This year, 21 students tried out for the volleyball team.
  1. How many different ways are there to choose the players from the group that tried out?
  2. Once we have chosen the team, how many ways are there to choose the starters?
  3. In total, how many ways are there to choose the players and then the starters?
  4. How many ways are there to choose the players, then the starters, and then one of the starters to be captain?
Check.
  1. \(\displaystyle \binom{21}{16}\)
  2. Hint: Choose six out of 16.
  3. Hint: Step 1 choose the players as in (a) and then step 2 choose the starter as in (b). Recall that by Theorem 2.2.3, we multiply the answers of each step.
  4. Hint: Now there is a third step.

8. Understand.

As in Exercise 3, the library’s new arrivals section offers 24 mystery novels, 50 young adult novels, 17 biographies, and 46 fantasy novels.
  1. In how many ways can I choose three books to read if I want two mystery novels and one fantasy novel?
  2. In how many ways can I choose four books for my son if he wants two young adult novels and two biographies?
  3. My mother would like two mystery novels, two biographies, and two fantasy novels. In how many ways can I choose books for her?
Check.
  1. \(\binom{24}{2}\binom{46}{1}\text{,}\) or just \(46\binom{24}{2}\text{.}\)
  2. Hint: There are two steps.
  3. Hint: There are three steps.

9. Understand.

Our local pizza parlor has a long list of toppings you can add to your pizza: five meats, three cheeses, and 12 vegetables. How many different “build your own” pizzas can you make if you want
  1. (Exactly) three toppings?
  2. One meat, one cheese, and one vegetable?
  3. Two meats, one cheese, and three vegetables?
  4. (Exactly) three toppings, including at least one meat and at least one cheese? Hint: Consider cases based on the number of meats, cheeses, and vegetables. For example, one case has one meat, two cheeses, and no vegetables.
Check.
  1. Hint: there are a total of \(5+3+12=20\) toppings and we want to choose three.
  2. \((5)(3)(12)\) Note: It would also be correct to have \(\binom{5}{1}\binom{3}{1}\binom{12}{1}\text{,}\) but since \(\binom{n}{1}=n\text{,}\) it is simpler to write the numbers.
  3. \(\displaystyle \binom{5}{2}\binom{3}{1}\binom{12}{3}\)
  4. Hint: There are three cases. Case 1 is one meat, two cheeses, and no vegetables. Case 2 is two meats, one cheese, and no vegetables. Case 3 is one meat, one cheese, and one vegetable as in (b). In each case, the steps multiply and then, by Theorem 2.2.7, add the answers from the three cases.

10. Understand.

There are 27 students in our Math Club.
  1. We need five students to run Pi Day activities. How many ways are there to pick five students?
  2. A team for the Problem Contest consists of three or four students. In how many different ways could we select a Problem Contest team?
  3. The club has four officers: President, Secretary, Treasurer, and Information Officer. In how many ways can we pick officers?
  4. We need a group of three students to write the annual report. Usually one of the officers volunteers and then two students who are not officers help. In how many ways could we form the group to write the annual report?
Check.
  1. \(\displaystyle \binom{27}{5}\)
  2. Hint: The word “or” indicates cases. Find the answer in each case and then add them together.
  3. \(\displaystyle (27)(26)(25)(24)\)
  4. Hint: Choose one officer and then choose two students who are not officers. Your answer should involve the number 23.

11. Recap.

Do you know …
  1. When to use \(n\) choose \(k\) versus steps or cases?
  2. How to combine counting subsets with steps and cases?

12. Explore.

This problem refers to the 52-card deck of playing cards in Definition 2.3.11.
  1. A hand is aces-over-eights if it has three aces and two eights. How many different aces over eights are possible?
  2. A full house is a hand of five cards with three cards of one denomination (a triple) and two cards of a different denomination (a pair). Aces-over-eights is an example of a full house. How many different full houses are there? Hint: first choose the denomination for the triple, then choose a different denomination for the pair, and then choose the actual cards.

13. Explore.

This problem refers to the 52-card deck of playing cards in Definition 2.3.11. A bridge hand has thirteen cards.
  1. How many bridge hands are there?
  2. How many bridge hands have a 6-card spade suit, which means that exactly six of the thirteen cards are spades?
  3. How many bridge hands have a 5-card spade suit and a 5-card heart suit, which means that the remaining three cards are diamonds or clubs.
  4. A yarborough is a bridge hand with no ten, jack, queen, king, or ace. How many yarboroughs are there?
  5. Which is more common — a bridge hand with a 5-card space suit and a 5-card heart suit or a yarborough? Use technology to evaluate your answers to 13.(c) and 13.(d).

Subsubsection Exercises for 2.3.C Proof Format: Combinatorial Proof

14. Practice.

 
  1. Copy the proof in Example 2.3.15.
  2. Change what needs to be changed to prove that
    \begin{equation*} 4\binom{12}{4}=12\binom{11}{3} \end{equation*}
    instead. You may edit the proof you copied instead of writing it out again.
  3. Use technology to confirm this equation.

15. Practice.

 
  1. Copy the proof in Example 2.3.15.
  2. Change what needs to be changed to prove that
    \begin{equation*} k\binom{n}{k}=n\binom{n-1}{k-1} \end{equation*}
    for any positive integers \(n\) and \(k\) instead. You may edit the proof you copied instead of writing it out again.
Check.
Hint: in (b) start with ``Consider a group of \(n\) employees. How many ways are there to choose \(k\) employees to be on a project team where one member of the team is the project manager?

16. Understand.

  Give a combinatorial proof that
\begin{equation*} \displaystyle 3\binom{10}{7} = 10 \binom{9}{7}\text{.} \end{equation*}
Hint: from a group of 10 people, choose a committee of 7 people, and its (outside) chair.

17. Understand.

  Give a combinatorial proof that
\begin{equation*} \displaystyle (n-k)\binom{n}{k} = n \binom{n-1}{k} \end{equation*}
for any positive integers \(n\) and \(k\text{.}\)
Hint: This equation generalizes Exercise 16, so use the same hint.

18. Chair and Secretary.

Give a combinatorial proof that
\begin{equation*} \displaystyle k(k-1)\binom{n}{k} = n(n-1)\binom{n-2}{k-2} \end{equation*}
for any positive integers \(n\) and \(k\text{.}\)
Hint: Choose a project team where one member of the team is the project manager and another member of the team is the lead analyst.

19. Understand.

Give a combinatorial proof that
\begin{equation*} \displaystyle \binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \end{equation*}
for any integers \(n\) , \(m\text{,}\) and \(k\text{.}\)
Hint: of \(n\) people who show up to try-outs, we will select \(m\) players for our team, of whom \(k\) will be starters.
Check.
Hint: Follow the hint. The first way to count is the usual order: choose the players, and then choose the starters. The second way to count is the reverse order: choose the starters, and then choose the rest of the players from the rest of the students who tried out.

20. Recap.

Do you know …
  1. Why a combinatorial proof works?
  2. When we can use a combinatorial proof?
  3. What the proof format for a combinatorial proof is?

21. Explore.

 
  1. Use a combinatorial argument to expand \(\displaystyle \binom{3n}{2}\) in terms of \(n\) for any positive integer \(n\text{.}\) Your answer may involve \(\binom{n}{2}\) and \(n\text{.}\) Hint: Suppose that there are \(n\) cats, \(n\) dogs, and \(n\) birds. No justification required.
  2. Use a combinatorial argument to expand \(\displaystyle \binom{n+m}{3}\) in terms of \(n\) and \(m\) for any positive integers \(n\) and \(m\text{.}\) Your answer may involve \(\binom{n}{2}\text{,}\) \(\binom{m}{2}\text{,}\) \(n\text{,}\) and \(m\text{.}\) No justification required.
Check.
  1. \(3n^2+3\binom{n}{2}\) Hint: Consider six cases and then simplify the answer.
  2. Hint: Suppose that there are \(n\) cats and \(m\) dogs and we want to choose three pets. Consider cases and simplify your final answer.
PrevTopNext