In this explainer, we will learn how to use combinations to solve counting problems.

Combinatorics is about counting possibilities. There are 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 1,234 to be different from 4,321. However, order is not always important. For example, you might want to ask how many ways you can choose two friends to go on a trip with you. It does not matter if you choose Mary then Peter or Peter then Mary, since you still end up with the same group going on the trip. This is an example of counting without repetition where order does not matter. This is what mathematicians call a combination.

### Definition: Combination

A combination is a selection of items chosen without repetition from a collection of items in which order does not matter.

Notice that the common usage of the word combination does not always agree with the mathematical definition. For example, usually we use the phrase combination lock to talk about a lock where we choose a code in which order matters. However, mathematically, this is not considered a combination.

Using the counting principle and permutations, we have learned to deal with counting problems with or without repetition where order matters. The focus of this explainer will be counting problems without repetition where order does not matter, known as combinations.

Without Repetition | With Repetition | |
---|---|---|

Order Matters | ||

Order Does Not Matter | Combinations |

We will use the next couple of examples to demonstrate how to calculate combinations.

### Example 1: Counting When Order Does Not Matter

A schoolβs administration is choosing the colors of its new logo. The logo is made of three letters: CHS. They would like to have a different color for each letter. The options for the colors are red, green, blue, yellow, orange, and purple.

- How many different ways can they color their logo?
- The school administration decided that instead of having a different color for each letter, they would buy three colors, mix them together, and then paint the whole logo in the resulting color. How many color options do they now have for their logo?

### Answer

**Part 1**

We are counting the number of ways in which we can order 3 different colors from a collection of six colors. Hence, we are counting without repetition where order matters, so the total number of ways in which we can do this will be given by the permutation .

**Part 2**

Given the decision of the school administration, we are now trying to count the number of different combinations of three colors where order does not matter since we will mix them together, so RGB will be the same as BGR. When we counted the number of ways to color a logo in part 1, we counted each of these colors differently because order mattered. The table below shows how many different ways we can count the three colors: red, green, and blue, when order matters and when it does not.

Order Matters | Order Does Not Matter |
---|---|

RGB | GRB |

RBG | |

BRG | |

BGR | |

GBR | |

GRB |

This means that in our answer to part 1, we have counted everything 6 times. Hence, the number of ways in which we can color the logo in a single color made from a mix of three colors is .

### Example 2: Combinations and Permutations

A companyβs security officers are ordering a new lock for the companyβs front door. They are concerned about security, so they would like a lock with at least 100,000 different possible codes. They bought a lock whose code is formed of six distinct digits chosen from 0β9, believing that the order in which the digits are entered matters.

- How many distinct possible door codes would such a lock have?
- Unfortunately, when it arrived, they discovered that it was a genuine combination lockβthat is, one for which order does not matter. How many distinct possible combinations does the lock have?

### Answer

**Part 1**

We need to calculate the number of ways in which we can choose 6 digits from a collection of 10 without repetition and where order matters. Hence, we can use the permutations formula with and to find the total number as follows:

**Part 2**

We have calculated the total number of codes where the order matters to be 151,200. This means that we have counted both 123,456 and 654,321 as different codes. However, if we want to consider each permutation of the same set of 6 numbers to be the same, we need to know how many times we have counted the same 6 numbers in different orders. We could therefore ask the question: for a collection of 6 distinct numbers, how many different ways can we arrange them? This is the same as the total number of permutations of 6 distinct digits, which can be calculated by evaluating . This means that, for every set of six distinct digits, we have counted different codes. Therefore, to find the total number of codes if order does not matter, we need to divide 151,200 by . Hence, the total number of different 6-digit combinations is given by

The previous examples demonstrate two important points related to combinations and permutations. Firstly, the number of permutations for a given and is generally much larger than the number of combinations. Secondly, to calculate the number of combinations of items from a collection of items, we can calculate the equivalent permutation and then divide by the redundancy . The redundancy is the number of excess times we have counted the same set of items due to the fact that the permutation counted each order as distinct. Putting this together, we arrive at the definition of .

### Definition: Number of Combinations of a Given Size

The number of combinations of size taken from a collection of items is given by

The notation can be read as -- or as choose and is also referred to as the binomial coefficient. Another extremely common notation for is ; however, there are also various other forms of notation commonly used such as , , , and .

Having defined , we will now look at a number of examples in which we use combinations to solve real-world counting problems.

### Example 3: Counting the Number of Matches in a Tournament

A chess tournament is to be held where every player plays each of his opponents. Given that there are 11 participants, calculate the number of games that will be played.

### Answer

We would like to count the number of ways we can pair 11 players. This means that we are counting without repetition and order does not matter since player 1 versus player 2 will be the same as player 2 versus player 1. This means that we are counting the number of combinations of 2 players taken from the collection of 11 players. Hence, the total number will be given by . Using the formula we have

Using the property of the factorial that , we can expand as follows:

Canceling the common factor of from the numerator and denominator and simplifying, we have

Hence, the tournament will have 55 matches.

### Example 4: Counting in Context

Hannahβs teacher divided the class into groups of six, and she required that each member of a group meet with every other member of the same group. How many meetings will each group have?

### Answer

The challenge with an example like this is interpreting what we need to count. The first thing we need to notice is that each group has six people in it. Each person needs to meet with every other person in the group, and we need to count the total number of meetings. Therefore, we are looking at how many ways we can choose two different people from a group of six where the order of our choice does not matter. This indicates that we are talking about combinations and the total number of meetings will be given by . Using the formula we have

Using the property of the factorial that , we can expand as follows:

Canceling the common factor of from the numerator and denominator and simplifying, we have

Hence, each group will have 15 meetings.

In the last couple of examples, we have demonstrated how we can apply the formula for calculating permutations. However, it is also legitimate to use your calculatorβs built-in combinations function to find the value of certain combinations. However, we should not only rely on this method. As we will see, there are questions where we will not be able to use a calculator, and, hence, knowing how to work with the formula is essential.

### Example 5: Counting the Number of Elements of a Set Using Combinations

Let and . Determine the number of elements in .

### Answer

We would like to count the number of elements of which is formed of a set of two items taken from . Firstly, we need to count how many elements are in . Being careful to count both 10 and 16, and all the integers between them, we find that has 7 elements. Since the elements of are sets, , which means that we are counting the number of ways in which we can choose 2 different elements from where order does not matter. This means that we are counting the number of combinations. Hence, the total number of elements in will be given by . Using the formula or the combinations function on our calculator, we find that . Hence, the number of elements in is 21.

### Example 6: Counting the Number of Ways to Form Committees

A village has 2 committees, each containing 2 people. In how many ways can the committees be formed if the members are selected from 12 people with the condition that a person can only be chosen once?

### Answer

We begin by counting the number of ways in which we can fill one of the committees. We have to choose two people from a group of twelve, where the order is unimportant. This corresponds to the combination .

Since we used two people in choosing the first committee, and each person can only be chosen once, we now have 10 people left from which to choose a group of 2 people. Hence, the number of ways in which we can form the second committee is given by the combination . By the counting principle, we have ways to form the two committees.

### Example 7: Counting the Number of Possible Polygons

If the elements of the set are arranged on a circle such that no two elements coincide, determine the number of polygons which can be made using these points as vertices.

### Answer

A polygon must have at least three vertices. Since we have four points, then the polygons must have at most four vertices. Thus, we only need to count the number of polygons with three vertices and the number with four. Note that when forming a polygon, the order in which we choose the vertices is not important. Thus, we will be counting the number of combinations. There are ways to pick a polygon with four vertices, and there are ways to pick a polygon with three vertices. Thus, in total, we can form polygons.

For the final example, we will look at a problem where we need to find in when given both and the number of possible combinations.

### Example 8: Word Problems Involving Combinations

At a college, there were 120 ways to select 119 students to attend a seminar. Determine the number of students at the college.

### Answer

Let be the total number of students in the college. Since there are 120 ways to select 119 students, we have . Using the definition of combinations, we have that

Hence,

Multiplying both sides of the equation by , we get

Expanding each side of the equation gives us

Equating either the largest or smallest terms, we find that . Therefore, the number of students at the college is 120.

### Key Points

- Combinations are an unordered selection of items chosen without repetition from a collection of . The total number of combinations of length chosen from a set of items is given by
- To use combinations to count, we need to check that
- we are counting without repetition,
- order does not matter.

- A summary of the different ways to count and the formulas to use for each is given in
the table below (we have not yet covered the way to count with repetition when order does not matter).
Without Repetition With Repetition Order Matters Order Does Not Matter