Type 3 - Selection Without Repetition - Combinations

In this section, we present some tasks involving selection without repetition problems. In our 2x2 grid, this is the cell in which repetition is not allowed, and we are counting unordered outcomes (or combinations). In problems like these, we can again employ multi-stage processes, where the number of options is reduced at each stage, because repetition is not allowed. However, in addition, we must avoid duplicate outcomes, as we do not want to count ordered outcomes, but rather unordered outcomes. For instance, in counting ordered outcomes, we might count 123, 132, 213, 231, 312, and 321 as distinct outcomes. In counting UNordered outcomes, we do not consider those as distinct; they are all the same set {1, 2, 3}. Thus, we need to account for duplicates when we count combinations.

There are a couple of ways to handle this. First, we will discuss turning unordered outcomes into uniquely ordered outcomes. Then, we will discuss how to leverage division and equivalence in order to find a general formula.

Combinations - Turning UNordered into Uniquely Ordered

Consider the following problem:

1) Write out a list of unordered sets of two numbers from the numbers {1, 2, 3, 4, 5, 6}. How many are there?

If we were to list these outcomes, we could start with the number 1, and pair it with 2 through 6, yielding 12, 13, 14, 15, 16. (Note, we do not write 11, because repetition is not allowed). Then, we could move to the number 2, and pair it with numbers. We do not pair it with 21, because we already wrote 12, and we want unordered outcomes (so we do not want to count both 12 and 21). We also don’t want to write 22, as repetition is not allowed. So, we write 23, 24, 25, 26. Similar, we would list 34, 35, 36, then 45, 46, and finally 56. An expression for the number of outcomes is thus \(5+4+3+2+1 = 15\). This is reflected in the process of pairing 1 with any of the 5 numbers greater than it, then pairing 2 with any of the 4 numbers greater than it, and proceeding in that fashion.

12, 23, 34, 45, 56

13, 24, 35, 46

14, 25, 36

15, 26

16

For any unordered sequence of distinct numbers, there is only one way to write them in increasing order. By choosing to create sequences of numbers in increasing order, we are ensuring that we will never produce the same outcome twice. This is what we mean when we say “turning unordered into uniquely ordered.” If you are counting unordered objects, you can alternatively count the objects in a specific order, provided there is exactly one way to put them in that order. For example, alphabetical order is a way to order sequences of letters uniquely, and strictly increasing order is a way to order sequences of integers uniquely. The program below will generate exactly the combinations we want, which are strictly increasing sequences of numbers. The use of the if statement using \(j > i\) ensures that the numbers in a given position will be greater than the values in all of the previous positions, and this means that we have strictly increasing sequences.

Reflect on the outcomes of the program below, which answers the question “How many unordered sets of two numbers are there from the numbers {1, 2, 3, 4, 5, 6}?” Are you convinced that the output is giving you what you want it to? Why or why not? Do you see a structure of \(5+4+3+2+1\) in the outcomes?

Active Code 2

Let us try to extend this idea by answering the following question:

3. How many combinations of size 3 are there from the numbers {1, 2, 3, 4, 5, 6}?

Here again we can consider a process of writing down outcomes. We can start with the number 1, and then pair it with 2, and then, since 1 and 2 have been used, we can pair 12 with 3, 4, 5, and 6. Then, we can pair 1 with 3, and then pair 13 with 4, 5, and 6. Once we have exhausted all of the options starting with 1, we can move to 2, and start with 23 paired with 4, 5, and 6. We can proceed in this manner, again essentially creating 3-digit sequences that are strictly increasing.

Note that there are \(4+3+2+1\) sets that start with 1, then \(3+2+1\) that start with 2, \(2+1\) that start with 3, and \(1\) that start with 4. Thus the overall expression that reflects this process is \((4+3+2+1)+(3+2+1)+(2+1)+(1) = 20.\)

The program below executes this idea. Note again that the conditional statements ensure the sequences will be strictly increasing. In the outcomes, we see this expression reflected in the structure of the outcomes.

Active Code 3

Check your knowledge using the problem below:

Combinations - Leveraging Division and Equivalence

Focusing on outcomes is a great way to figure out what formula is appropriate to use, and why that formula can be applied. Because the above method looks at the outcomes being counted, it can be good to keep it in mind as a way of identifying problem types. However, for problems that involve three or more objects being selected, it can be tedious to use. Another way we can count this type of problem is to leverage division and equivalence in order to “uncount” all the repeated outcomes. This can be most easily seen in Type 2 problems - arrangements without repetition, also called permutations.

For instance, suppose we want to select, but not arrange, 3 objects from 5 objects. That is, we want to count unordered outcomes of 3 objects chosen from 5 objects. To do this, let us first consider arranging objects, which we know can be done in \(5 \cdot 4 \cdot 3 = \frac{5!}{2!} = 60\) ways.

If we look at the outcomes of this process, notice that we get outcomes like 123, 132, 312, and 321. Run the next bit of code to check that we generated ordered outcomes.

Active Code 1

In the above problem, note that for any given set of digits, such as {1, 2, 3}, there are 6 total outcomes in the list of ordered outcomes that contain these three digits. These are, specifically, 123, 132, 213, 231, 312, and 321. It makes sense that there are 6 such outcomes, as there are \(3! = 3 \cdot 2 \cdot 1 = 6\) arrangements of three distinct digits. Thus, for every set of numbers, there are 6 times as many ordered outcomes as there are unordered outcomes. For every 6, we want to count one outcome. Answer the following question:

Quick Check 1.1

General formula for Selection without Repetition

In general, if we are arranging \(r\) elements from \(n\) distinct elements, there will always be \(r!\) arrangements of any given \(r\) elements. So, if we want to count unordered rather than ordered outcomes, there will be \(r!\) times more ordered outcomes than unordered outcomes. We thus have the following general relationship for selecting \(r\) elements from \(n\) distinct elements:

In particular, we get that \((\text{Number of unordered outcomes})\cdot (\text{Number of ways to arrange } r \text{ elements} ) = (\text{Number of ordered outcomes})\), which we know to be the following:

\((\text{Number of unordered outcomes}) \cdot r! = \frac{n!}{(n-r)!}\).

Thus, the total \((\text{Number of unordered outcomes}) = \frac{n!}{(n-r)!\cdot r!}.\)

This is often denoted as \(C(n,r)\) and, more commonly as \({n \choose r}\), which is said “\(n\) choose \(r\).” So, \({n \choose r} = \frac{n!}{(n-r)!\cdot r!}\).

For example, consider the problem below.

1. Nine horses compete in a beauty competition, and there will three identical
prizes given. How many possibilities are there for which three horses receive prizes?

If we want to select a set of three horses from a field of 9 horses to win a prize, we can take the number of ordered outcomes (which we know to be \(9 \cdot 8 \cdot 7 = \frac{9!}{6!}\)) and divide it by the number of ways to arrange three horses, which is \(3!\). Thus, the total number of unordered outcomes is \(\frac{9 \cdot 8 \cdot 7}{3!} = \frac{9!}{6!\cdot 3!} = {9 \choose 3} = 84\).

Check your knowledge on the following problem.

Some Practice Problems

4. There are 20 professors in a department, and a 4-person Graduate Committee
must be formed. How many possibilities are there for who can be on the committee?

Notice, a committee is an unordered outcome because all that matters for determining a committee is who is on the committee - different orders or arrangements of the committee members do not make distinct outcomes. So, we are counting 4-combinations chosen from 20 people.

We can employ our general formula to get \({20 \choose 4} = \frac{20!}{16!\cdot4!} = 4,845.\)

We can check our work by running a program, as seen below.

Active Code 4

5. A Poker hand consists of a set of 5 cards from a standard 52-card deck.
How many possible Poker hands are there?

Here we must just choose 5 cards from 52 cards, so we get \({52 \choose 5} = \frac{52!}{47!\cdot5!} = 2,598,960.\)

The following code yields this same result.

Active Code 5

Many problems will not be only a direct application of this formula, but rather they will involve or incorporate the formula in some way into a broader problem. Here we offer some examples of how this formula might arise or be used in problems.

5. I have 12 books. I want to give three of them away to my friend John, and I
want to give six of them away to my friend Craig. How many possible outcomes are
there for giving my books away?

This counting process has a two-stage process. Note that I can first pick 3 of the 12 books to give to John. There are then 9 books left, and I can pick 6 of them to give to Craig. Since the number of outcomes at each stage is independent of previous choices, I can employ the Multiplication Principle. Thus I get that my answer is \({12 \choose 3} \cdot {9 \choose 6} = 18,480\).

6. We have 6 Moms, 6 Dads, and 8 children to choose from. We need to make a
committee of size 7, with exactly 2 Dads, 3 Moms, and 2 children. How many ways
are there to do this?

Solve the following Parson’s problem to create code that solves this problem.

Arrange the lines below to create code to count the number of ways to make the committee specified in the problem.

We can first pick 2 of the 6 Dads, then 3 of the 6 Moms, then 2 of the 8 children. Since the number of options at each stage is independent of any particular choice, we can employ the multiplication principle. We get an expression of \({6 \choose 2} \cdot {6 \choose 3} \cdot {8 \choose 2} = 8,400\).

You have attempted of activities on this page