In this explainer, we will learn how to use combinations to count with repetition where order does not matter.
There is a number of key considerations when we are seeking to count the number of possible outcomes. The first is the concept of counting with, or without, repetition. If we are forming a 4-digit number from the digits 1β9, the question of repetition is whether or not we can use the same digit multiple times. Hence, if we allow repetition, we can choose a number like 1βββ111. However, if we do not allow repetition, each digit will be distinct.
The second important consideration is whether order matters or not. For example, when picking 4-digit numbers, we consider 1234 to be different form 4321. However, order is not always important. For instance, we might want to know the number of ways we can choose four sandwiches from a sandwich shop. Here, order does not matter, since choosing the cheese then choosing the chicken is the same as choosing the chicken then choosing the cheese. In both cases, we have two sandwiches, one cheese and one chicken. Assuming there is no shortage of different sandwiches, this is an example of counting with repetition where order does not matter. In this explainer, we will learn how to count the number of possible outcomes in problems like this.
| Without Repetition | With Repetition | |
|---|---|---|
| Order Matters | ||
| Order Does Not Matter |
Initially, problems of this type seem difficult to understand how to approach. However, restating the problem in a slightly different way leads to an understanding of how to address problems like this. We will begin by demonstrating how to think about problems of this type so that we can derive a general formula for solving them.
Example 1: Counting with Repetition Where Order Does Not Matter
Sally is buying an ice cream cone and is able to pick two scoops from four flavors: chocolate, banana, strawberry, and vanilla. How many different ways can she pick two scoops from the four flavors?
Answer
Firstly, we notice what type of counting problem we have. Since she can have two scoops of the same flavor, we are counting with replacement. Furthermore, order does not matter. To understand how to solve this problem, we will present a new way to restate the problem to help see how to solve it.
Imagine that the shop attendant starts by pointing at the first flavor and asks whether Sally would like that flavor. She can reply either βyesβ or βnext flavor.β She will then go through this process until she gets to the end of the four flavors and has said βyesβ twice and βnext flavorβ three times.
Hence, if the flavors were ordered chocolate, banana, strawberry, vanilla, the choice of chocolate and banana would be represented: where represents her saying βyesβ and represents her saying βnext flavor.β If Sally wanted two scoops of strawberry, this would be represented by
In this way, we can represent all possible choices of two scoops of ice cream from four flavors. Hence, our problem reduces how many ways we can arrange three s and two s. This is the same problem as choosing two objects to mark with a from a set of five where the order does not matter, since choosing the second element and then the fourth is the same as choosing the fourth and then the second. In this way, we have reduced the problem to one of choosing without repetition where order does not matterβa problem we know how to solve. Hence, the number of possible ways that Sally can choose ice cream flavors is
The technique we used in the last example demonstrates that by restating the problem in a new way, we are able to reduce it to a problem we know how to solve. This is often a very useful skill in combinatorics problems. Often, changing the way we are thinking about a problem can help us restate it as a problem we already know how to solve. We will demonstrate how useful this can be in a number of the examples.
Returning to this specific example, the particular technique we usedβto restate the problem in the form of a choice without repetition where order does not matterβgeneralizes to all problems that involve repetition where order does not matter. A careful examination of the previous question will help us find the general formula for this.
We were looking to choose 2 things from 4. Therefore, we set and . We found that to reformulate the problem, we formed a sequence of three s and two s. Obviously, the two s simply generalize to the number of choices , whereas, regarding the s, we only had three s. This is because we only had to say βnextβ three times to have the possibility of choosing from any of the four flavors. Therefore, in a general problem, we would need s. In this way, we can transform a problem of choosing things with repetition from options where order does not matter to a problem of choosing things without repetition from a set of options where order does not matter. Hence, the number of possibilities is .
Counting with Repetition Where Order Does Not Matter
The number of possible ways to choose things with repetition from a set of choices where order does not matter is given by
Now that we know the general formula, we will be able to apply it to other problems of this type. However, whenever we approach a counting problem, we need to be careful to categorize it properly to ensure we use use the correct formula.
Example 2: Choosing Dishes from a Menu with Repetition
Three friends are in a tapas restaurant. They would like to order 6 dishes to share. There are 15 different options on the menu. Given that they can choose multiple dishes of the same type, how many different possible ways can they order 6 dishes to share?
Answer
Firstly, we notice what type of counting problem we have. Since they can choose multiple dishes of the same type, we are counting with replacement. Furthermore, the order of their choices does not matter. Therefore, we have a problem of choosing 6 items with replacement from a set of 15 options where order does not matter. Therefore, the number of possibilities will be given by
Example 3: Counting the Number of Integer Solutions
How many nonnegative integer solutions are there to the equation ?
Answer
At first glance, a problem like this seems difficult to solve. However, we would like to see if there is a way we can reformulate this problem into something we know how to solve.
We begin by thinking of the number 40 being represented by forty vertical bars, as shown below.
Then, the problem of finding five positive integers that sum to forty is the same as finding a partition of this set of bars into five different sets. We can think of this as adding four partition marks to separate this set into five distinct groups, where the number of bars in each group represents the number. For example,
is interpreted as
which represents the sum . Similarly,
is interpreted as
which represents the sum . Using this formulation, all possible nonnegative integer solutions to this problem can be thought of as being equivalent to a representation of this type. Hence, the problem of counting the number of nonnegative integer solutions to the given equation is equivalent to the problem of arranging 40 bars and four pluses . We have, therefore, successfully reformulated the problem into a problem we know how to solve. The number of ways we can arrange 40 bars and four pluses is given by .
At first glance, the previous example may not appear to be related to the idea of counting with repetition where order does not matter. However, by reformulating the problem, we found that these two problems are equivalent. An alternative way to reformulate this problem is choosing forty units from five boxes with replacement. Then, the number chosen from each box represents the integer .
The next example will look at a similar problem with the added complexity of different constraints for the integers.
Example 4: Number of Solutions with Constraints
How many integer solutions are there for the equation , given that , , and ?
Answer
We would like to find a way to reformulate this problem into one we know how to solve. The easiest way to accomplish this is to find a way to normalize our variables so they can all take values between 0 and some constant . This can be achieved by making substitutions. If we let be defined by the equation , the condition is equivalent to . Similarly, we can let and be defined by the equations and . Then, the conditions, and are equivalent to . Substituting these definitions into the equation gives
This simplifies to finding the integer solutions to where . In this way, we have successfully reformulated the problem into one we know how to solve. This is the problem of choosing 26 units from 3 boxes with replacement where order does not matter. Hence, the total number of integer solutions to given that , , and is .
As we have seen, one important skill in dealing with combinatorics questions is being able to reformulate problems into ones we have already solved. One specific aspect of this is being able to easily identify whether we are dealing with combinations or permutations and whether we are counting with or without replacement. In the last two examples, we will look at two combinatorics problems where the main skill is finding the best way to think about the problem.
Example 5: Using Different Techniques to Count
How many possible diagonals can be drawn in a regular -gon?
Answer
We will look at two possible ways to think about and solve this problem. The first we will consider from first principles, then we will use a more combinatorial argument. We let the number of diagonals of an -gon be denoted .
If we consider a single vertex in the -gon, there are possible vertices that we can connect it to. However, we would like to discard two of these, since they are the edges of the -gon and, therefore, not diagonals. Hence, the number of diagonals from a single vertex is . If we multiply by the number of vertices, we will have counted every diagonal twice, once for each end of the diagonal. Therefore, we should divide this number by two. Hence, the general formula for the total number of diagonals is
The alternative way to approach this problem is by considering the number of ways we can choose two vertices from a set of . This corresponds to the number of line segments that connect points. Notice that this is an example of counting without replacement where order does not matter. Hence, we can find this using combinations, and the total number will be given by . This, however, is not our final answer, because we have counted the edges of the polygon. Since we would only like the diagonals, we would like to subtract the edges of the polygon, which gives us a final answer of
This is a different formula from the one we derived from the first principles. However, the two formulas are equivalent, as we will show. Using the definition of the combination , we can rewrite as
This simplifies to
We can now express this as a single fraction as follows:
Example 6: Shuttle Bus Problem
Twenty passengers get on an airport shuttle. The shuttle route includes six hotels, and each passenger gets off the shuttle at his/her hotel. The driver records how many passengers leave the shuttle at each hotel. How many different possibilities exist?
Answer
We let the number of passengers who get off at each hotel be denoted by . Since every passenger will get of the bus at one of the hotels, the sum of will be equal to the total number of people. Hence,
Hence, we have successfully restated the problem in terms of a problem we know how to solve: finding the number of positive integer solutions to this equation. The number of possibilities is given by .
As we have seen in the last couple of examples, a lot of the skill in combinatorics is finding the best way to think about a problem. Sometimes this is to help us formulate it into a problem we know now to solve or to find an appropriate way to count what we are interested in.
Key Points
- When seeking to solve combinatorics problems, we often need to identify whether we are
dealing with counting with or without replacement and whether or not order matters. Once
we have done this, we can apply the appropriate formula summarized in the table below.
Without Repetition With Repetition Order Matters Order Does Not Matter - Much of the skill in combinatorics is mapping new problems to ones we have already solved or know how to solve. This is how we derive the general formula for counting with repetition where order does not matter. However, this is a useful skill to apply in general to mathematical problems and the problems that arise in other scientific disciplines.
