Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 4.3.2 Combinations

Definition 4.3.2.1.

A combination of a set of distinct objects is an unordered selection of these objects. An unordered selection of \(r\)-elements from a set is called an \(r\)-combination . The number of \(r\)-combinations of a set of size \(n\) is denoted \(C(n,r)\) .
🔗
🔗

Example 4.3.2.2. Combinations and Permutations of \(\{a, b, c, d\}\).

Let \(S = \{a, b, c, d\}\text{.}\)
  1. The \(1\)-combinations of \(S\) are
    🔗
    🔗
  2. The \(2\)-permutations of \(S\) are
    🔗
    🔗
  3. The \(3\)-combinations of \(S\) are
    🔗
    🔗
  4. The \(4\)-combinations of \(S\) are
    🔗
    🔗
🔗
🔗

Remark 4.3.2.3.

There is only one way to select all of the elements of \(S\text{,}\) so \(C(n,n) = 1\text{,}\) in general.
🔗
🔗

Proof.

We can carry out the last of listing the \(r\)-combinations by listing the \(r\)-permutations. By Theorem 4.3.1.6, there are \(\frac{n!}{(n - r)!}\) ways to do this. For each of these ways, exactly \(r!\) of the ways correspond to the same way. The result then follows by the Division Rule.
🔗
🔗

Example 4.3.2.5. Poker hands.

How many poker hands (5 cards) are in a standard deck of \(52\) cards?
🔗
Solution.
We want to count \(5\)-combinations of cards. Since there are \(52\) cards, the number of \(5\)-combinations is
\begin{equation*} C(52, 5) = \frac{52!}{5!(52 - 5)!} = \frac{52!}{5!47!} = \frac{52\cdot 51 \cdot 50 \cdot 49 \cdot 48}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = {2598960}. \end{equation*}
🔗
🔗
🔗
Selecting \(r\) elements from a set of size \(n\) to be in an \(r\)-combination is equivalent to selecting \(n - r\) elements not to be in the \(r\)-combination. Thus the number of ways to do each must be the same. This gives the following theorem.
🔗

Example 4.3.2.7. Exam committees.

Suppose there are \(9\) freshmen and \(11\) sophomores in MAT 253. How many different final exam committees can be made if a committee consists of \(3\) freshmen and \(4\) sophomores ?
🔗
Solution.
The procedure of choosing a committee can be broken down into two tasks, namely, selecting the freshmen and selecting the sophomores. The number of ways to select freshmen is
\begin{equation*} C(9,3) = \frac{9!}{3!(9-3)!} = \frac{9!}{3!6!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84. \end{equation*}
The number of ways to select sophomores is
\begin{equation*} C(11,4) =\frac{11!}{4!(11-4)!} = \frac{11!}{4!7!} = \frac{11 \cdot 10 \cdot 9 \cdot 8}{4 \cdot 3 \cdot 2 \cdot 1} = 330. \end{equation*}
Then by the Product Rule, the number of different committees is
\begin{equation*} 84 \cdot 330 = {27720}. \end{equation*}
🔗
🔗
🔗

Example 4.3.2.8. Bit strings with three zeros.

How many bit strings of length ten have exactly three 0s?
🔗
Solution.
We can describe a bit string with exactly three 0s by specifying the location of the three 0s. There are ten possible places for them to go, and we cannot distinguish the three 0s, so the order does not matter. Thus the number of bit strings with exactly three 0s is
\begin{equation*} C(10,3) = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120. \end{equation*}
🔗
🔗
🔗

Example 4.3.2.9. Soccer team.

Thirteen students on a soccer team consisting of freshman and sophomores show up for a game. Of the thirteen that show up, three are sophomores. How many ways are there to choose ten players to take the field if at least one of these players must be a sophomore ?
🔗
Solution.
Which of the following computations is correct?
  1. There are \(C(3,1) = 3\) ways to choose a sophomore. Then there are 12 remaining players, and we need to choose \(9\) of them. The number of ways to choose \(9\) from \(12\) is
    \begin{equation*} C(12,9) = \frac{12!}{9!(12-9)!} = \frac{12!}{9!3!} = \frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = 220. \end{equation*}
    By the Product Rule, the number of ways to choose a team with at least one sophomore is the product
    \begin{equation*} C(3,1)C(12,9) = 3 \cdot 220 = 660. \end{equation*}
    🔗
    🔗
  2. There are \(3\) ways to choose a sophomore. Of the remaining \(10\) freshmen, we need to choose \(9\text{.}\) The number of ways to choose \(9\) from \(10\) is \(C(10,9) = 10\text{.}\) By the Product Rule, the number of ways to choose a team with at least one sophomore is the product \(3 \cdot 10 = 30\text{.}\)
    🔗
    🔗
  3. To pick a team, independent of class year, we need to choose \(10\) people from a group of \(13\text{.}\) The number of ways to pick \(10\) from \(13\) is
    \begin{equation*} C(13, 10) = \frac{13!}{10!(13-10)!}= \frac{13!}{10!3!} = \frac{13\cdot 12 \cdot 11}{3 \cdot 2 \cdot 1} = 286. \end{equation*}
    There is \(C(10,10) = 1\) way to choose a team of all freshmen. Therefore there are \(286 - 1 = 285\) ways to choose a team with at least one sophomore.
    🔗
    🔗
🔗
The third method is correct. The second method counts the teams with exactly 1 sophomore. It does not allow for more than one sophomore. The first method counts certain teams more than once. For example if Alice is chosen first as part of the \(C(3,1)\text{,}\) and then Beverly is chosen as part of the \(C(12,9)\text{,}\) the team created is duplicated when Beverly is chosen first as part of the \(C(3,1)\) and Alice is chosen as part of the \(C(12,9)\text{.}\) We can see furthermore that the value of \(660\) cannot be correct, as the total number of possible teams is \(286\text{,}\) as shown in the third method.
🔗
🔗
🔗

Example 4.3.2.10. People in a line.

How many ways are there for eight freshmen and five sophomores to stand in a line so that no two sophomores stand next to each other?
🔗
Hint: First position the freshmen and then consider the possible positions for the sophomores.
🔗
Solution.
There are \(P(8,8) = 8!\) ways to arrange the freshmen in order. There are 9 slots where a sophomore can go so that the sophomores are separated by at least one freshman. There are \(C(9,5) = \frac{9!}{5!(9-5)!}\) ways to choose the slots for the sophomores. There are \(P(5,5) = 5!\) ways to arrange the sophomores. By the Product Rule, there are
\begin{equation*} 8! \cdot \frac{9!}{5!(9-5)!} \cdot 5!= {609638400} \quad \text{ways.} \end{equation*}
🔗
🔗
🔗
🔗
PrevTopNext