Section 9.5 Combinations
In this section we look at how to count subsets of a set and define the mathematical concept of a combination.
Definition 9.5.1.
Let \(n, r\) be nonnegative integers with \(r\leq n\text{.}\) An \(r\)-combination of a set of \(n\) elements is the number of subsets of size \(r\) that can be chosen from a set of \(n\) elements. We denote it \(\binom{n}{r}\text{,}\) which is read “\(n\) choose \(r\text{.}\)”
Other common notation are
\(C(n, r)\text{,}\) or
\(nCr\text{.}\) We will use
\(\binom{n}{r}\) notation, which we first saw in
Section 5.1. For example,
\(\binom{5}{4}\) is the number of subsets of size 4 chosen from a set of 5 elements.
Since order does not matter in a set, the order in which we choose elements of a set does not matter. Recall, when counting permutations, the order in which we chose our elements did matter. We can use what we know about permutations, though, to count combinations.
We can calculate combinations by first finding all the \(r\)-permuatations of a set, then dividing by all the possible orderings of that subset: \(\frac{P(n, r)}{r!}\text{.}\) This can be rewritten to be the standard formula for calculating combinations:
\begin{equation*}
\binom{n}{r}=\frac{n!}{r!(n-r)!}\text{.}
\end{equation*}
Note, since \(0!=1\text{,}\) \(\binom{n}{0}=1\) and \(\binom{0}{0}=1\text{.}\) This also makes sense with the definition, as there is only one set with 0 elements, the empty set.
Activity 9.5.1.
Calculate \({6 \choose 2}\) and \({6 \choose 4}\text{.}\)
Activity 9.5.2.
Calculate \({4 \choose 0}\) and \({4 \choose 4}\text{.}\)
Example 9.5.2. Combinations versus Permutations.
Suppose you want to choose a group of 3 students in a class of 15 for a group project. How many ways can you choose the group?
We use combinations: \(\binom{15}{3}\text{.}\) It does not matter if a member was chosen first, second, or third, they would still be a member of the group. Thus, there are \(\frac{15!}{3!12!}=455\) ways to choose a group of 3.
Now suppose you want to choose a group of 3 students in a class of 15 for a group project, but the first student chosen will be the note-taker, the second will be the presenter, the third will manage the discussion. How many ways can you choose the group?
We use permutations: \(P(15, 3)\text{.}\) Now it does matter if a member was chosen first, second, or third, as each member has a different role. Thus, there are \(\frac{15!}{12!}=2730\) ways to choose a group of 3 where the members’ roles are defined.
In deciding whether to use combinations or permutations, you need to decide whether order matters. For combinations, order doesn’t matter; think about choosing subsets. For permuations, order does matter; think about choosing ordered lists.
Recall, a binary string is just a list of 0s and 1s
Example 9.5.3. Binary Strings.
How many binary strings of length 5 can have exactly 2 ones?
We can think of forming a binary string with 2 ones as a list of 5 places where we need to choose 2 places for the ones. Once we’ve done that, the other places must have 0’s. Thus, we have five places and choose 2:
\begin{equation*}
\binom{5}{2}=\frac{5!}{2!3!}=10.
\end{equation*}
How many binary strings of length 5 can have at most 2 ones?
Here we can count the strings with 2 ones, 1 one, and 0 ones. We add them since the strings with different numbers of ones are disjoint:
\begin{equation*}
\binom{5}{2}+\binom{5}{1}+\binom{5}{0}=10+5+1=16.
\end{equation*}
Activity 9.5.3.
How many binary strings of length 7 have exactly 3 ones?
Hint.
Think of this as a list of 7 digits. How many ways are there to place the ones?
Activity 9.5.4.
How many binary strings of length 7 have at most 2 ones?
Hint.
First count how many have 0 ones, then 1 one, then 2 ones. Should you use the addition rule or multiplication rule to find the total number?
Example 9.5.4. Rearranging Letters.
How many ways are there to order the letters in the word “letter”?
We can think of the string of letters as 6 places where we can choose to put letters. First we can choose the place to put the “l”: we have 6 places, we need to choose 1: \(\binom{6}{1}.\)
Next we choose the places to put the two “e”s: we now only have 5 places (since one has the l), we need to choose 2: \(\binom{5}{2}.\)
We continue in this way, with 3 places to put the two “t”s: \(\binom{3}{2}\text{,}\) and one remaining place to put the “r”: \(\binom{1}{1}\text{.}\)
Since placing each letter is a process (we don’t have a complete string until we have placed all the letters), we need to use the multiplication rule:
\begin{equation*}
\binom{6}{1}\cdot \binom{5}{2}\cdot \binom{3}{2}\cdot \binom{1}{1}=6\cdot 10\cdot 3\cdot 1=180.
\end{equation*}
There is another way to calculate the previous example.
Example 9.5.5. Alternate Rearranging Letters.
How many ways are there to order the letters in the word “letter”?
We can think of the string of letters as 6 places where we can choose to put letters. First we can think of all the letters as distinct. Then we have 6 letters to choose for the first place, 5 for the second, 4 for the third, etc. Thus we have \(6!\) ways to place 6 distinct letters.
But the letters are not distinct, so we need to divide by the number of ways we over-counted. For each permutation we just counted, switching the two “e”s gives us the same word, so we need to divide by the number of ways to rearrange the two “e”s: \(2!.\) Similarly, we need to divide by equivalent arrangements of the two “t”s: \(2!\text{.}\)
Putting this together we have
\begin{equation*}
\frac{6!}{2!2!}=180.
\end{equation*}
Activity 9.5.5.
How many ways are there to order the letters in “book”?
Hint.
First place all the “b”s--how many ways can you do this? Then count how many ways to place all the “o”s, then all the “k”s.
Activity 9.5.6.
How many ways are there to order the letters in “infinity”?
Example 9.5.6. Forming Committees.
A class has 13 students. How many ways can a group of 7 be chosen?
Answer.
\(\binom{13}{7}\)
Suppose in this class of 13 there are 7 juniors and 6 seniors.
-
How many groups of 7 can be chosen that contain 4 juniors and 3 seniors?
Answer.
\(\binom{7}{4}\cdot \binom{6}{3}\text{,}\) first choose the juniors then the seniors.
-
How many groups of 7 can be chosen so that there is at least one senior?
Answer.
\(\binom{13}{7}- \binom{7}{7}\text{,}\) all the possible groups minus the groups with no seniors.
-
How many groups of 7 can be chosen so that there are at most 3 juniors?
Answer.
\(\binom{7}{1}\cdot \binom{6}{6}+\binom{7}{2}\cdot \binom{6}{5}+\binom{7}{3}\cdot \binom{6}{4}\text{,}\) count the groups of one junior and 6 seniors, two juniors and 5 seniors, three juniors and 4 seniors. Note, there are no groups with no juniors.
-
How many groups of 7 can be chosen if two people refuse to work together?
Call the two people A and B.
Find the number of groups with A and not B: \(\binom{11}{6}\text{.}\) Note, we only need to choose 6 out of 11 since we know A is in the group and B is not, so we just need to choose the other 6 members.
Similarly, find the number of groups with B and not A: \(\binom{11}{6}\text{.}\)
Now, find the number of groups with neither A nor B: \(\binom{11}{7}\text{.}\) Note, we need to choose 7 out of 11 since we know A and B cannot be chosen.
Since the sets of each type of group (with A, with B, with neither) are disjoint, we use the addition rule:
\begin{equation*}
\binom{11}{6}+\binom{11}{6}+ \binom{11}{7}.
\end{equation*}
Reading Questions Check Your Understanding
1.
2.
3.
4.
5.
6.
7.
8.
9.
Exercises Exercises
1.
Calculate
\(\displaystyle {6 \choose 0}\)
\(\displaystyle {6 \choose 1}\)
\(\displaystyle {6\choose 2}\)
\(\displaystyle {6\choose 3}\)
\(\displaystyle {6\choose 4}\)
\(\displaystyle {6\choose 5}\)
\(\displaystyle {6\choose 6}\)
2.
A student council consists of 15 students.
In how many ways can a committee of 6 be selected from the membership of the council?
Two council members have the same major and are not permitted to serve together on a committee. How many ways can a committee of 6 be selected from the membership of the council?
Two council members always insist on serving together on a committee. If they can’t serve together, they won’t serve at all. How many ways can a committee of 6 be selected from the membership of the council?
-
Suppose the council contains 8 seniors and 7 juniors.
How many committees of six contain three seniors and three juniors?
How many committees of six contain at least one junior?
Suppose the council consists of three freshmen, four sophomores, three juniors, and five seniors. How many committees of eight contain two from each class?
3.
An instructor gives an exam with fourteen questions. Students are allowed to choose any ten questions to answer.
How many different choices of ten questions are there?
-
Suppose six questions require proof and eight do not.
How many groups of ten questions contain four that require proof and six that do not?
How many groups of ten questions contain at least one that requires proof?
How many groups of ten questions contain at most three that require proof?
Suppose the exam instructions specify that at most one of the questions 1 and 2 may be included among the ten. How many different choices of the ten questions are there?
Suppose the exam instructions specify that either questions 1 and 2 are to be included among the ten or neither is to be included. How many different choices of ten questions are there?
4.
A coin is tossed ten times. In each case the outcome (H or T) is recorded.
What is the total number of possible outcomes of the coin tossing experiment?
In how many of the possible outcomes are exactly five heads obtained?
In how many of the possible outcomes are at least eight heads obtained?
In how many of the possible outcomes is at least one head obtained?
In how many of the possible outcomes is at most one head obtained?
5.
A binary or bit string consists of just 0’s and 1’s. A bit string of length 16 is called a 16-bit string.
How many 16-bit strings contain exactly seven 1’s?
How many 16-bit strings contain at least thirteen 1’s?
How many 16-bit strings contain at least one 1?
How many 16-bit strings contain at most one 1?
6.
Consider the word \(NINETEENTH\)
How many distinguishable ways are there to order the letters in the word \(NINETEENTH\text{?}\)
How many distinguishable ways are there to order the letters in the word \(NINETEENTH\) if it must begin with \(I\) and end with \(E\text{?}\)
How many distinguishable ways are there to order the letters in the word \(NINETEENTH\) if the letters \(HI\) must be next to each other in order?
7.
In Morse code, symbols are represented by variable-length sequences of dots and dashes. For example, \(A=\cdot -, 1=\cdot - - - -, ?=\cdot \cdot - - \cdot \cdot\text{.}\) How many different symbols can be represented by sequences of seven or fewer dots and dashes?
You have attempted
of
activities on this page.
