3.1: Combinations

As mentioned last time, the following flowchart summarizes how each structure is naturally derived from the one before it:

In the last section, we saw The Generalized Principle of Counting leads to a permutation. In this section, we will discuss how permutations leads to the idea of a combination.

In order to discuss the theory of combinations, we first define what a combination is.

Definition: Permutation

Suppose a set has \(n \) distinct elements and an experiment consists of selecting \( k\) of the elements one at a time without replacement. Let each outcome consist of the \( k\) elements in any order. Each such outcome is called a combination of \( n \) elements taken \( k\) at a time or is called an unordered sample without replacement.

Moreover, if the \( k\) elements selected are \( s_1, s_2, s_3 \ldots, s_k \), then we denote this combination of \( n \) elements taken \( k \) at a time by the following notation: \( \{s_1, s_2, s_3 \ldots, s_k\} \).

The total number of combinations of \(n\) elements taken \(k\) at a time is denoted by \( C_{n,k} \) or \( \binom{n}{k} \) which is read as " \(n\) choose \(k\)".

There is a lot to take in the above definition and so allow us to highlight the important assumptions above.

Assumptions of a Permutation

In order to have a combination, the following assumptions must be met:

1. We have \(n \) distinct elements.
2. We are selecting \( k\) of the elements.
3. The selection takes place without replacement (meaning there is no repetition of elements).
4. For some reason, we do not wish to note the order in which the elements are selected. That is, there is nothing special/unique about being chosen first, second or third, and so on.

Once all four assumptions are met, we can denote the combination by writing the elements between braces as we would normally do with our set notation.

Here is a classic example of a scenario involving a combination.

Example 1 \(\PageIndex{1}\)

Suppose that in a group of 26 friends, I am inviting three friends to attend a concert. Explain why the three people we invite can be thought of as a combination of 26 elements taken 3 at a time. Can you write down a few different outcomes?

Solution

In order to explain why our invitee list can be thought of as combination of 26 elements taken 3 at a time, we simply verify that all four assumptions outlined above apply to the given situation.

1. We have 26 distinct friends.
2. We are selecting 3 of the friends.
3. The selection takes place without replacement since once we choose a friend to attend the concert with us, we cannot choose that friend again. Hence, there is no repetition.
4. The order of selection is irrelevant because if we were to first choose Alice then Bob then Charlie, this is the same as first choosing Charlie, then Bob then Alice. In each case, I am attending the concert with the same three people and so there is nothing special/unique about being chosen first, second or third.

Hence an outcome can be viewed as a combination of 26 elements taken 3 at a time.

Now suppose my friends are labeled \(A, B, C, D, \ldots, Z \). Here is an example of a combination of 26 elements taken 3 at a time: \( \{C, A, R \} \). In this outcome, friends \(C, A \) and \(R\) were invited to the concert.

Here is another (different!) outcome: \( \{K, A, R \} \). This outcome is different because here, friend \(K\) is attending whereas in the previous outcome, \(K\) was not attending.

Finally, although this was not asked in the problem, note that \( \{ B, T, B ) \} ) is not a possible outcome since in a combination, there is no repetition.

Intuition of a Combination

Informally speaking, a combination of \( n \) elements taken \( k\) at a time is just simply a subset of \(k\) elements without replacement. For instance, a combination of \( n \) elements taken \(2 \) at a time is just simply a subset of two elements, \( \{ x,y \} \). Meanwhile, a permutation of \( n \) elements taken \(3 \) at a time is just simply a subset of three elements, \( \{x,y,z \} \), so on and so forth.

With this idea in mind, allow us to try and count the number of combinations of \( n \) elements taken \( k\) at a time. We first start off with a concrete example and ask some questions concerning the problem.

Example 2 \(\PageIndex{2}\)

Find the total number of combinations of 4 elements taken 2 at a time.

Critique This Solution

In order to answer this question, we first must understand what the problem is asking us. Based off our intuition of a combination, this problem is asking us to find the total number of subsets of size 2 without replacement. This means we must find the number of ways to fill in the following structure: \( ( \{ \_\_ , \_\_ \} \).

We can think of filling in the above spaces as a 3-stage experiment. We proceed in steps:

1. Choose an element for the first placeholder: there are \( 4 \) choices.

2. Choose an element for the second placeholder 2: there are \(3 \) choices.

3. Choose an element for the third placeholder: there are \(2 \) choices.

By The Generalized Principle of Counting, there are \( 4 \times 3 \times 2 = 12 \) different combinations.

Do you think the above solution is correct? Why or why not?

Answer

Unfortunately, the above solution is incorrect! It is incorrect to use The Generalized Principle of Counting. Recall that The Generalized Principle of Counting requires us to have distinct steps! In the proposed solution, there is no difference between step 1, 2 or 3 since we are filling out a combination. In a combination, we said the order in which we select the elements does not matter and so we should not select the elements in separate steps. Thus the proposed solutions are incorrect. In order to correctly answer this problem, we need a different technique.

With the above example in mind, allow us to consider the more general problem:

Example 3 \(\PageIndex{3}\)

Find the total number of combinations of 4 elements taken 2 at a time.

Answer

For this question, we seem to be stuck. Whenever we are stuck in a counting question, there is one technique which will always work (although it can be time-consuming and diificult!). Specifically, the technique we will use to answer this question is enumeration. This means we are going to list out all of the possibilities.

As mentioned above, this problem is asking us to find the total number of subsets of size 2 without replacement. This means we must find the number of ways to fill in the following structure: \( ( \{ \_\_ , \_\_ \} \). Listing out all possibilities yields the following:

\[ \{a,b \} \nonumber\ \]

\[ \{a,c \} \nonumber\ \]

\[ \{a,d \} \nonumber\ \]

\[ \{b,c \} \nonumber\ \]

\[ \{b,d \} \nonumber\ \]

\[ \{c,d \} \nonumber\ \]

We see that there are a total of 6 different combinations of 4 elements taken 2 at a time. In terms of notation, we have found that \( C_{4,2} = 6 \}.

Unfortunately, the above process does not tell us anything on how to generalize the problem to the case of \(n\) elements taken \(k\) at a time. And so we must make another insight concerning the problem. What is this insight? Allow us to consider the following related problem.

Example 4 \(\PageIndex{4}\)

Enumerate all permutations of 4 elements taken 2 at a time.

Answer

For this question, it is clear that there should be \(P_{4,2} = 4 \times 3 \times 2 = 12 \) such permutations. What are these permutations? Here they are:

\[ (a,b), (b,a) \nonumber\ \]

\[ (a,c) , (c,a) \nonumber\ \]

\[ (a,d ), (d,a) \nonumber\ \]

\[ (b,c), (c,b) \nonumber\ \]

\[ (b,d), (d,b) \nonumber\ \]

\[ (c,d), (d,c) \nonumber\ \]

How does the above solution help us? Let us create a chart to see if we notice anything:

Combinations of 4 elements taken 2 at a time	Permutations of 4 elements taken 2 at a time
\[ \{a,b \} \nonumber\ \]	\[ (a,b), (b,a) \nonumber\ \]
\[ \{a,c \} \nonumber\ \]	\[ (a,c) , (c,a) \nonumber\ \]
\[ \{a,d \} \nonumber\ \]	\[ (a,d ), (d,a) \nonumber\ \]
\[ \{b,c \} \nonumber\ \]	\[ (b,c), (c,b) \nonumber\ \]
\[ \{b,d \} \nonumber\ \]	\[ (b,d), (d,b) \nonumber\ \]
\[ \{c,d \} \nonumber\ \]	\[ (c,d), (d,c) \nonumber\ \]

Looking at the above chart, is there anything that we notice? That is, is there any formula we can develop between the number of combinations of \(4\) elements taken \(2\) at a time and permutations of \(4\) elements taken \(2\) at a time?

Answer

1) The first thing we notice is that there are 6 entries on the left hand side and 12 entries on the right hand side.

2) Where does the 6 come from? The 6 stems from the fact that we computed \( C_{4,2} = 6 \}. Similarly, where does the 12 come from? The 12 stems from the fact that \( P_{4,2} = 12 \}.

3) There are twice as many permutations as combinations and so C_{4,2} \times 2 = P_{4,2}. But where did the 2 come from?

4) To answer where the 2 came from, we note the once difference between a combination and a permutation. As seen from our list of assumptions, in a combination the order is not noted while for a permutation, the order is indeed noted. Thus, given any combination, if we were to impose an ordering, then we would obtain a permutation! This is precisely what is happening in our chart. Fix any row and start with a combination. If we were to impose an ordering on the two elements, then we would end up with the corresponding permutation. The question now becomes, how many ways can we order two elements? By our theorem from Section 2.3, there are \(2!\) ways to arrange two distinct elements.

5) Putting everything together, it seems like \( C_{4,2} \times 2! = P_{4,2} \) where the \( 2! \) stems from the fact that there are \(2!\) ways to arrange 2 distinct elements.

If we had to guess, the general formula which links permutations and combinations is given by \( C_{n,k} \times k! = P_{n,k} \) and hence

\[ \displaystyle C_{n,k} = \frac{P_{n,k} }{ k! } \nonumber\ \]

Note

Based off the above discussion, we expect \( C_{n,k} \times k! = P_{n,k} \). If you are not convinced, then we can do the same procedure with different numbers. For instance, let us check if \( C_{5,3} \times 3! = P_{5,3} \). Clearly \( P_{5,3} = 60 \). To find \( C_{5,3} \) try enumerating all the possibilities. If you get stuck, then run the following script:

combn(5, 3, FUN = NULL, simplify = FALSE)

If done correctly, we will see that \( C_{5,3} \times 3! \) does indeed equal \( P_{5,3} \).

We can now finally answer the following question: Find the number of combinations of \( n \) elements taken \( k\) at a time. The answer is presented in the form of the following theorem.

Theorem: Total Number of Combinations \(\PageIndex{5}\)

\[ \displaystyle C_{n,k} = \frac{P_{n,k} }{ k! } = \frac{n!}{k!(n-k)!} \nonumber\ \]

Proof: We consider how a permutation is constructed. Specifically, a permutation is constructed in two steps.

1) A subset of \(k\) elements are chosen. The number of ways to generate a subset of \(k\) elements without repetition is given by \( C_{n,k} \).

2) We then order the \(k\) elements. There are \(k!\) ways to do so.

The above two-stage process yields all possibile permutations, \(P_{n,k} \). Hence, by The Basic Principle of Counting \( C_{n,k} \times k! = P_{n,k} \) and so

\[ \displaystyle C_{n,k} = \frac{P_{n,k} }{ k! } \nonumber\ \]

Note that Substituting in \( \frac{n!}{(n-k)!} \) for \( P_{n,k} \) in \( \frac{P_{n,k} }{ k! }\) yields \( \frac{n!}{k!(n-k)!} \).

We now add on a question to the first example we discussed at the beginning of this section.

Example 5 \(\PageIndex{5}\)

Suppose that in a group of 26 friends, I am inviting three friends to attend a concert. Find the number of different friend groups that I can invite.

Answer

As we discussed in the first example, each group of three friends can be regarded as a subset of three people. Hence, the question is asking us to find the number of subsets of size three. By the above theorem, the number of different combinations of friend groups is given by \[ \displaystyle C_{26,3} = \frac{P_{26,3} }{ 3! } = 15,600 \nonumber\ \]

Example 6 \(\PageIndex{6}\)

From a group of 28 people, two people are chosen to be secretaries. How many different choices are possible?

Answer

We first ask ourselves what counting structure do we have here? Observe the following:

1) Do we have \(n\) distinct elements? Yes, we have 28 distinct people.

2) In this experiment are we selecting \(k\) elements? Yes, we are selecting 2 people.

3) Does the selection happen without replacement? Yes, the selection happens without replacement (otherwise it's possible we pick the the same person both times and so we only have 1 secretary as opposed to 2).

4) Is the order of selection noted? In order to answer this, we ask ourselves is there anything special about being chosen first versus being chosen second? The answer is no! Both chosen people end up with the same task/role of being a secretary.

This means we may think of an outcome as a subset of two people, \( \underbrace{ \{\_\_, \_\_}_{sec.} \} \). The number of subsets of two people is given by \( C_{28,2} = \binom{28}{2} = 378 \).

Let us now reconsider the problem posed in our last section:

Example 7: Critique This Solution! \(\PageIndex{7}\)

Suppose that from a group of 30 people, a president, vice president, and two secretaries are to be chosen. How many different outcomes are possible?

Answer

For this question, we can consider an outcome to look like the following: \( ( \underbrace{\_\_}_{pres.}, \underbrace{\_\_}_{vp.}, \underbrace{ \{\_\_, \_\_}_{sec.} \} ) \). That is, we can think of an outcome as being fulfilled in three steps:

1) We first select a president. There are 30 choices.

2) We then select a vice president. There are 29 choices.

3) We then select a subset of two people to be secretaries. There are \( \binom{28}{2} \) choices.

By The Generalized Principle of Counting, there are \( 30 \times 29 \times \binom{28}{2} = 328,860 \) different outcomes.

Example 8 \(\PageIndex{8}\)

From a group of 10 women and 12 men, a committee of 2 women and 3 men must be formed. How many different committees are possible?

Answer

For this question, we can consider an outcome to look like the following: \( \{ \underbrace{ \_\_, \_\_}_{women}, \underbrace{ \_\_, \_\_, \_\_}_{men}\} \). That is, we can think of an outcome as a subset of 5 people where 2 people are women and the other 3 are men. Thus, an outcome is fulfilled in two steps:

1) We first choose a subset of two women. There are \( \binom{10}{2} = 45 \) ways to do this.

2) We now select a subset of three men. There are \( \binom{12}{3} = 220 \) ways to do this.

By The Generalized Principle of Counting, there are \( \binom{10}{2} \times \binom{12}{3} = 9,900 \) different committees consisting of 2 women and 3 men.

Example 9 \(\PageIndex{9}\)

From a regular deck of 52 cards, 5 cards are drawn at random with no emphasis on the order of the cards. How many outcomes are there where we obtain 2 Kings, 2 Queens, and 1 Jack?

Answer

For this question, we can consider an outcome to look like the following: \( \{ \underbrace{ \_\_, \_\_}_{Kings}, \underbrace{ \_\_, \_\_}_{Queens}, \underbrace{\_\_}_{Jacks} \} \). That is, we can think of an outcome as a subset of 5 cards where 2 cards are Kings, 2 cards are Queens, and the other card is a Jack. Thus, an outcome is fulfilled in three:

1) We first choose a subset of two Kings. There are \( \binom{4}{2} = 6 \) ways to do this.

2) We now select a subset of two Queens. There are \( \binom{4}{2} = 6 \) ways to do this.

3) We select one Jack. There are \( \binom{4}{1} = 4 \) ways to do this.

By The Generalized Principle of Counting, there are \( \binom{4}{2} \times \binom{4}{2} \times binom{4}{1} = 4 = 144 \) different subsets of consisting of 2 Kings, 2 Queens, and 1 Jack.

Example 10 \(\PageIndex{9}\)

From a regular deck of 52 cards, 5 cards are drawn at random with no emphasis on the order of the cards. How many outcomes are there where we obtain three 7's and two Aces?

Answer

For this question, we can consider an outcome to look like the following: \( \{ \underbrace{ \_\_, \_\_, \_\_}_{Sevens}, \underbrace{ \_\_, \_\_}_{Aces} \} \). That is, we can think of an outcome as a subset of 5 cards where 3 of the cards have the denomination of a 7 and the other two cards have the denomination of an Ace. We proceed in steps.

1) We first choose three cards that are labeled with a seven. There are \( \binom{4}{3} = 4 \) ways to do this.

2) We now choose two cards that are labeled with an ace. There are \( \binom{4}{2} = 6 \) ways to do this.

By The Generalized Principle of Counting, there are \( \binom{4}{3} \times \binom{4}{2} = 24 \) different subsets of consisting of three 7's and two Aces.

Example 10 \(\PageIndex{10}\)

From a regular deck of 52 cards, 5 cards are drawn at random with no emphasis on the order of the cards. How many outcomes are there where we obtain a full house? (By a full house we mean that we obtain three cards of one denomination and two cards of another denomination, different from the first. For instance, an example of a full house would be \( 7\heartsuit, 7\diamondsuit, 7 \clubsuit, A \heartsuit, A \spadesuit \).

Answer

For this question, we can consider an outcome to look like the following: \( \{ \underbrace{ \_\_, \_\_, \_\_}_{\text{Three of a kind}}, \underbrace{ \_\_, \_\_}_{\text{Two of a kind}} \} \). That is, we can think of an outcome as a subset of 5 cards where 3 of the cards have the same denomination and the other two cards have the same denomination. We proceed in steps.

1) We first choose a denomination for the three of a kind. There are \( \binom{13}{1} = 13 \) ways to do this.

2) For the selected denomination, we choose three of the four cards. There are \( \binom{4}{3} = 4 \) ways to do this.

3) We now choose a denomination for the two of a kind. There are \( \binom{12}{1} = 12 \) ways to do this.

4) For the selected denomination in step 3, we choose two of the four cards. There are \( \binom{4}{2} = 6 \) ways to do this.

By The Generalized Principle of Counting, there are \( \binom{13}{1} \times \binom{4}{3} \times \binom{12}{1} \times \binom{4}{2} = 3,744 \) different full houses.

An important note to make is that for certain problems, there is not one unique set of steps to a solution. For instance, consider the following:

Exercise 11 - Alternative Solution to Example 10 \(\PageIndex{11}\)

In the above example, notice that the answer \( \binom{13}{2} \binom{2}{1} \binom{4}{3} \binom{4}{2} \) is equivalent to 3,744. Can you determine the steps associated with this alternative solution?

Answer

For this question, we still regard an outcome as the following: \( \{ \underbrace{ \_\_, \_\_, \_\_}_{\text{Three of a kind}}, \underbrace{ \_\_, \_\_}_{\text{Two of a kind}} \} \). The only thing which is different is the order of our steps:

1) We first choose the two denominations that will be in our full house. There are \( \binom{13}{2} = 78 \) ways to do this.

2) From these two denominations, we must choose one denomination that will be used to fill in the three of a kind. There are \( \binom{2}{1} = 2 \) ways to do this.

3) For the selected denomination, we choose three of the four cards. There are \( \binom{4}{3} = 4 \) ways to do this.

4) For the other denomination, we choose two of the four cards. There are \( \binom{4}{2} = 6 \) ways to do this.

By The Generalized Principle of Counting, there are \( \binom{13}{2} \binom{2}{1} \binom{4}{3} \binom{4}{2} = 3,744 \) different full houses.

We end this section with

Theorem \(\PageIndex{1}\)

\[ \binom{n}{k} = \binom{n}{n-k} \nonumber\ \]

Proof: The formal proof is left as a homework exercise.

Intuition (Informal Justification of the above theorem)

For example, the above theorem is stating that \[ \binom{30}{5} = \binom{30}{25} \nonumber\ \]

Why is this true? Let us suppose we have 30 students in a room and we have to select 5. Clearly, \( \binom{30}{5} \) represents the number of subsets of size 5. But notice every time we choose a subset of 5 students what are we also doing? We are not choosing 25 students. Hence, for every subset of 5 students, we are indirectly creating a subset of 25 students and vice-versa. Each time we choose 25 students, we are indirectly creating a subset of 5 students. Thus \[ \binom{30}{5} = \binom{30}{25} \nonumber\ \]. More generally, \[ \binom{n}{k} = \binom{n}{n-k} \nonumber\ \] since every time we choose \(k\) elements, we are creating a subset of \(n-k\) elements and vice-versa.