Skip to main content

Section 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 3.2.1.

Let \(n\) be a positive natural number, and \(0 \le r \le n\text{.}\) 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).

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.2 that there are \(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 \(10!/(7!3!)=10\cdot 9 \cdot 8 /6=120\text{.}\)

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

By Theorem 3.1.3, the number of \(r\)-permutations of \(n\) object is \(n!/(n-r)!\) . 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\cdot r!=n!/(n-r)!\text{.}\) Rearranging the equation, we obtain \(k=n!/(r!(n-r)!)\text{.}\)

⬛

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

Notation 3.2.4.

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

\begin{equation*} \binom{n}{r}=\frac{n!}{r!(n-r)!}\text{.} \end{equation*}
Definition 3.2.5.

We read \(\binom{n}{r}\) as “ \(n\) choose \(r\),” so \(n\) choose \(r\) is \(n!/[r!(n-r)!]\text{.}\)

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

\begin{equation*} \binom{n}{r}=\frac{n!}{n!(n-n)!}=\frac{n!}{n!0!}=\frac{n!}{n!}=1\text{,} \end{equation*}

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

\begin{equation*} \binom{n}{0}=\frac{n!}{0!(n-0)!}=1; \end{equation*}

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

One of the earliest known historical examples of calculating combinations comes from India in the \(500\)s (CE).

Varāhamihira (499—587), an astronomer and mathematician from the region of Ujjain, wrote the Brhatsambitā, an extensive treatise on divination. At one point in this book, he considers \(16\) possible fragrances that can be included in perfumes, and counts the number of distinct perfumes that could be made using any four of these fragrances. What is the correct answer to this?

Solution

Now that we understand how to calculate combinations, the answer to this is very straightforward:

\begin{equation*} \binom{16}{4}=\frac{16!}{4!(16-4)!}=\frac{16\cdot 15\cdot 14\cdot 13}{4\cdot 3\cdot 2}=1820. \end{equation*}

Let's go over another example that involves combinations.

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

\begin{equation*} \binom{11}{2}+\binom{11}{2}+\binom{11}{1}=\frac{11!}{2!9!}+\frac{11!}{2!9!}+\frac{11!}{1!10!}=\frac{11\cdot 10}{2}+\frac{11\cdot 10}{2}+11=55+55+11=121 \end{equation*}

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\text{.}\)

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\text{.}\) 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.

We return to some simple examples of how combinations have been studied and used historically.

Abraham ibn Ezra (c. 1093—1167) lived in Spain while it was under Moorish rule. In his book Se'fer Ha'Olam (“The Book of the World”), he considered the number of “planetary conjunctions” that could occur involving any given number of the seven “planets”. At the time, all of the “wandering” celestial bodies were thought to orbit the earth, and the seven such bodies that were known were called the planets. These seven were the moon, the sun, Mercury, Venus, Mars, Jupiter, and Saturn. When at least two of them appear to meet in the sky, it is called a conjunction. For each \(k\) from \(2\) through \(7\text{,}\) how many different ways can exactly \(k\) of these be involved in a conjunction?

Solution

For \(k=2\text{,}\) the answer is

\begin{equation*} \binom{7}{2}=\frac{7!}{2!(7-2)!}=\frac{7\cdot 6}{2}=21. \end{equation*}

For \(k=3\text{,}\) the answer is

\begin{equation*} \binom{7}{3}=\frac{7!}{3!(7-3)!}=\frac{7\cdot 6 \cdot 5}{3 \cdot 2}=35. \end{equation*}

For \(k=4\text{,}\) the answer is

\begin{equation*} \binom{7}{4}=\frac{7!}{4!(7-4)!}=\frac{7\cdot 6 \cdot 5}{3 \cdot 2}=35. \end{equation*}

For \(k=5\text{,}\) the answer is

\begin{equation*} \binom{7}{5}=\frac{7!}{5!(7-5)!}=\frac{7\cdot 6}{2}=21. \end{equation*}

For \(k=6\text{,}\) the answer is

\begin{equation*} \binom{7}{6}=\frac{7!}{6!(7-6)!}=7. \end{equation*}

For \(k=7\text{,}\) the answer is

\begin{equation*} \binom{7}{7}=\frac{7!}{7!(7-7)!}=1 \end{equation*}

(recall that \(0!=1\)).

In \(1144\) at the age of \(19\text{,}\) Al-Samaw’al ben Yahyā al-Maghribī (c.1130—c.1180) of Baghdad wrote Al-Bāhir fi'l-jabr (the “Brilliant in Algebra”). Among other things, he considered equations in multiple variables and counted the number of ways in which it is possible to take a sum of exactly \(6\) out of \(10\) possible variables. What is the correct answer to this?

Solution

The answer to this is the number of ways to choose \(6\) of the \(10\) variables to sum up: that is,

\begin{equation*} \binom{10}{6}=\frac{10!}{6!(10-6)!}=\frac{10\cdot 9 \cdot 8 \cdot 7}{4\cdot 3 \cdot 2}=210. \end{equation*}

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 they have chosen?

  2. For the same trick, you insist that your friend keep replacing their first draw until they draw a card that isn't a spade. They can choose any cards for their other two cards. How many possible sets of cards might they end up with? (Caution: choosing \(5\clubsuit, 6\diamondsuit, 3\spadesuit\) in that order, is not different from choosing \(6\diamondsuit, 5\clubsuit, 3\spadesuit\) 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 (A, K, Q, J, \(10\text{,}\) 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 1\(0\) flavours of ice cream and \(7\) toppings. Their megasundae 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 megasundaes are there?