3.2: Combinations

Sometimes the order in which individuals are chosen doesn’t matter; all that matters is whether or not they were chosen. An example of this is choosing a set of problems for an exam. Although the order in which the questions are arranged may make the exam more or less intimidating, what really matters is which questions are on the exam, and which are not. Another example would be choosing shirts to pack for a trip (assuming all of your shirts are distinguishable from each other). We call a choice like this a “combination,” to indicate that it is the collection of things chosen that matters, and not the order.

Definition: \(r\)-Combination

Let n be a positive natural number, and \(0 ≤ r ≤ n\). Assume that we have \(n\) distinct objects. An \(r\)-combination of the \(n\) objects is a subset consisting of \(r\) of the objects.

So a combination involves choosing items from a finite population in which every item is uniquely identified, but the order in which the choices are made is unimportant.

Again, you should not be surprised to learn (since we are studying enumeration) that what we’ll be asking is how many combinations there are, in a variety of circumstances. One significant difference from permutations is that it’s not interesting to ask how many n-combinations there are of \(n\) objects; there is only one, as we must choose all of the objects.

Let’s begin with an example in which we’ll calculate the number of \(3\)-combinations of ten objects (or in this case, people).

Example \(\PageIndex{1}\)

Of the ten athletes competing for Olympic medals in women’s speed skating (1000 metres), three are to be chosen to form a committee to review the rules for future competitions. How many different committees could be formed?

Solution

We determined in Example 3.1.1 that there are \(\dfrac{10!}{7!}\) ways in which the medals can be assigned. One easy way to choose the committee would be to make it consist of the three medal-winners. However, notice that if (for example) Wong wins gold, Sajna wins silver, and Andersen wins bronze, we will end up with the same committee as if Sajna wins gold, Andersen wins silver, and Wong wins bronze. In fact, what we’ve learned about permutations tells us that there are \(3!\) different medal outcomes that would each result in the committee being formed of Wong, Sajna, and Andersen.

In fact, there’s nothing special about Wong, Sajna, and Andersen – for any choice of three people to be on the committee, there are \(3! = 6\) ways in which those individuals could have been awarded the medals. Therefore, when we counted the number of ways in which the medals could be assigned, we counted each possible 3-member committee exactly \(3! = 6\) times. So the number of different committees is \(\dfrac{10!}{(7!3!)} = 10 · 9 · \dfrac{8}{6} = 120\).

We can use the same reasoning to determine a general formula for the number of \(r\)-combinations of \(n\) objects:

Theorem \(\PageIndex{1}\)

The number of \(r\)-combinations of \(n\) objects is

\[\dfrac{n!}{r!(n − r)!}\]

Proof

By Theorem 3.1.1, there are \(\dfrac{n!}{(n − r)!}\) \(r\)-permutations of n objects. Suppose that we knew there are \(k\) unordered \(r\)-subsets of \(n\) objects (i.e. \(r\)-combinations). For each of these \(k\) unordered subsets, there are \(r!\) ways in which we could order the elements. This tells us that \(k · r! = \dfrac{n!}{(n − r)!}\). Rearranging the equation, we obtain \(k = \dfrac{n!}{(r!(n − r)!)}\).

It will also prove extremely useful to have a short form for the number of \(r-\)combinations of \(n\) objects.

Note

We use \(\binom{n}{r}\) to denote the number of \(r\)-combinations of \(n\) objects, so

\[\binom{n}{r} = \dfrac{n!}{r!(n-r)!}\]

Definition

We read \(\binom{n}{r}\) as “\(n\) choose \(r\),” so \(n\) choose \(r\) is \(\dfrac{n!}{[r!(n − r)!]}\)

Notice that when \(r = n\), we have

\[\binom{n}{r} = \dfrac{n!}{n!(n-n)!} = \dfrac{n!}{n!0!} = \dfrac{n!}{n!} = 1 \]

coinciding with our earlier observation that there is only one way in which all of the \(n\) objects can be chosen. Similarly,

\[\binom{n}{0} = \dfrac{n!}{0!(n-0)!} = 1 \]

there is exactly one way of choosing none of the \(n\) objects.

Let’s go over another example that involves combination

Example \(\PageIndex{2}\)

Jasmine is holding three cards from a regular deck of playing cards. She tells you that they are all hearts, and that she is holding at least one of the two highest cards in the suit (Ace and King). If you wanted to list all of the possible sets of cards she might be holding, how long would your list be?

Solution

We’ll consider three cases: that Jasmine is holding the Ace (but not the King); that she is holding the King (but not the Ace), or that she is holding both the Ace and the King

If Jasmine is holding the Ace but not the King, of the eleven other cards in the suit of hearts she must be holding two. There are \(\binom{11}{2}\) possible choices for the cards she is holding in this case.

Similarly, if Jasmine is holding the King but not the Ace, of the eleven other cards in the suit of hearts she must be holding two. Again, there are \(\binom{11}{2}\) possible choices for the cards she is holding in this case.

Finally, if Jasmine is holding the Ace and the King, then she is holding one of the other eleven cards in the suit of hearts. There are \(\binom{11}{1}\) possible choices for the cards she is holding in this case.

In total, you would have to list

\(\binom{11}{2} + \binom{11}{2} +\binom{11}{1} = \dfrac{11!}{2!9!} + \dfrac{11!}{2!9!} + \dfrac{11!}{1!10!} = \dfrac{11 \cdot 10}{2} + \dfrac{11 \cdot 10}{2} + 11 = 55 + 55 + 11 = 121 \) possible sets of cards.

Here is another analysis that also works: Jasmine has at least one of the Ace and the King, so let’s divide the problem into two cases: she might be holding the Ace, or she might be holding the King but not the Ace. If she is holding the Ace, then of the twelve other hearts, she is holding two; these can be chosen in \(\binom{12}{2} = 66\) ways. If she is holding the King but not the Ace, then as before, her other two cards can be chosen in \(\binom{11}{2} = 55\) ways, for a total (again) of \(121\).

A common mistake in an example like this is to divide the problem into the cases that Jasmine is holding the Ace, or that she is holding the King, and to determine that each of these cases includes \(\binom{12}{2} = 66\) possible combinations of cards, for a total of \(132\). The problem with this analysis is that we’ve counted the combinations that include both the Ace and the King twice: once as a combination that includes the Ace, and once as a combination that includes the King. If you do this, you need to compensate by subtracting at the end the number of combinations that have been counted twice: that is, those that include the Ace and the King. As we worked out in the example, there are \(\binom{11}{1} = 11\) of these, making a total of \(132−11 = 121\) combinations.

Exercise \(\PageIndex{1}\)

Use what you have learned about combinations to work out the following problems. Permutations and other counting rules we’ve covered may also be required.

1. For a magic trick, you ask a friend to draw three cards from a standard deck of \(52\) cards. How many possible sets of cards might she have chosen?
2. For the same trick, you insist that your friend keep replacing her first draw until she draws a card that isn’t a spade. She can choose any cards for her other two cards. How many possible sets of cards might she end up with? (Caution: choosing \(5\)♣, \(6\)♦, \(3\)♠ in that order, is not different from choosing \(6\)♦, \(5\)♣, \(3\)♠ in that order. You do not need to take into account that some sets will be more likely to occur than others.)
3. How many \(5\)-digit numbers contain exactly two zeroes? (We insist that the number contain exactly \(5\) digits.)
4. Sandeep, Hee, Sara, and Mohammad play euchre with a standard deck consisting of \(24\) cards (\(\text{A}\), \(\text{K}\), \(\text{Q}\), \(\text{J}\), \(10\), and \(9\) from each of the four suits of a regular deck of playing cards). In how many ways can the deck be dealt so that each player receives \(5\) cards, with \(4\) cards left in the middle, one of which is turned face-up? The order of the \(3\) cards that are left face-down in the middle does not matter, but who receives a particular set of \(5\) cards (for example, Sara or Sandeep) does matter.
5. An ice cream shop has \(10\) flavours of ice cream and \(7\) toppings. Their mega-sundae consists of your choice of any \(3\) flavours of ice cream and any \(4\) toppings. (A customer must choose exactly three different flavours of ice cream and four different toppings.) How many different mega-sundaes are there?