Combinatorics

This lesson covers the topics of combinatorics (combinations, permutations with and without repetitions, circular and constrained permutations). It will equip you with all the necessary theoretical knowledge on the topic, and show how it is applied in standardized test problems.

Factorial

The factorial of an integer n is defined as the successive product of all the positive integers from n down to 1:

n! = n × (n − 1) × (n − 2) × (n − 3) × . . . 1

By convention, 0! = 1.

0! and 1! are the only two factorials that are odd; the rest have a factor of 2 in them.

• 1! = 1
• 2! = 2 × 1 = 2
• 3! = 3 × 2 × 1 = 6
• 4! = 4 × 3 × 2 × 1 = 24
• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040

 

On most of the tests, you won’t need to calculate large factorials. Most of the time you will be able to reduce them or simplify the expression.

For example: Find the value of 23!/21!

1. 21
2. 23
3. 462
4. 506
5. 10626

 

If you write down all the factors, you will see the trend:

(23 × 22 ×21 × 20 × 19 × 18…..1) / (22 × 21 × 20 × 19 × 18…1).

You can cancel all the numbers in the numerator against the same numbers in the denominator except the 23×22 in the numerator. So,

23!/21! = 23 × 22 = 506.

Combinations

Combinations mean groupings of elements in which the order of the elements does not matter.

The main formula for combinations is

where nC_k is the number of possible combinations of k elements, taken from the broader set of n elements.

Example: A box contains seven cubes, each one of a different color. If you take two cubes out of the box, how many different color combinations are possible?

1. 12
2. 17
3. 21
4. 38
5. 42

Here,

Hint: you can easily see that if you need to pick one element out of the set of n elements, there are n ways to do it. (E.g. pick one day out of 365 – there are 365 ways to pick it). If you need to pick two elements, the formula

This is just the same formula as above, only simplified for the case of two elements. You can remember it, or you can use the general formula, whichever is more convenient for you.

Permutations

Permutations are ordered arrangements of elements. The number of possible ordered permutations is almost always larger than the number of unordered combinations of the same set of elements.

The formula for permutations is

where nP_k is the number of possible ordered arrangements of k elements from a larger set of n elements.

Example: There are seven cubes of different colors in a box. If you take two cubes out of the box, one with your right hand and another one with your left hand, and the place in one or the other hand is important, how many different combinations can be made?

1. 12
2. 17
3. 21
4. 38
5. 42

Here,

These permutations are also called permutations without repetition.

Example: How many different ways can four doctors be assigned to four patients if each doctor gets one patient? The first doctor has four choices, the second doctor then has three choices,   the third doctor has two choices, and the fourth has just one choice. Then, the total number of arrangements is

4×3×2×1 = 4! = 24.

If there are still 4 patients but more doctors, say 6, then you have permutations of a subset. Let’s find the number of ways 6 doctors can be assigned to 4 patients. The first patient can get any of the 6 doctors, so there are 6 options. The second patient can be treated by any of the  5 remaining doctors (since the same 6th doctor cannot have 2 patients), so there are 5 options. Then, there are 4 options to assign a doctor to the third patient and 3 options for the 4thpatient. The total number of options is the product of the options for each patient

= 6 × 5 × 4 × 3 = 360 ways.

Another example: What is the number of the possible three-letter arrangements of letters K, L, M, N.

There are 4 options for the first letter, 3 for the second, and 2 for the third,

So, there are 4 × 3 × 2 = 24 options in total.

Permutations with Repetitions

If you need to rearrange a set that has repeating elements, you need to adjust the formula for these repetitions.

Example: In how many ways can the letters of the word SOLO be rearranged?

The formula to use is

where n is the number of elements in the original set, in which there are j different repeating elements, and r is the number of times each element repeats.

 

Returning to the SOLO example, there are 4 letters in total, so

n = 4,

and there is one repeating letter, so

j = 1.

Then, the number of repetitions of the letter O is 2, so

r1 = 2.

 

Plug this into the formula:

Permutations with Combinations

To take a broader view of permutations and combinations, you need to understand how they relate to each other. We have said that permutations are basically the same as combinations, but with the order of elements taken into account.

This is reflected by the extra element in the denominator in the combinations’ formula:

Here’s an example to clarify this.

You need to select four bands to perform at a concert from a total of 8 available bands, and you need to decide on the order in which they perform.

The usual way to do this is the same as in the above example with doctors and patients: there are 8 options for the first slot in the concert, 7 options for the second slot, 6 for the third and 5 for the last. This makes a total of   8 × 7 × 6 × 5 = 1680 possible options.

Another way to do this is to apply the permutations formula:

Here, n = 8 since there are 8 bands in total, k = 4 since you need to pick 4. Then

One more way of doing this is by breaking the problem down into two steps:

First, you need to identify the four bands, and then you need to arrange them in a certain order. This is a less convenient way of solving this particular problem, but you need to be familiar with the logic, as you might need it for more complex problems.

The first step is to select 4 bands out of 8, not taking order into account. This is done with the combinations formula

Where, again, n=8 and k = 4.

There are 4 × 3 × 2 × 1 = 24 ways to order this set. Now, you have 70 ways to select bands and 24 ways to order them. This makes 70 × 24 = 1680 ways to pick an ordered combination of bands. You have reached the same result. This should give you an idea of how combinations and permutations are related so that you could apply this logic to problems of any difficulty level.

Circular Permutations

In this problem type, objects are arranged around a circle. The difference as compared to linear permutations is that a circle does not have a clear beginning and end, like a line. So, although combinations ABCD and BCDA are two different options in a linear permutation, they are the same combination around a circle:

So, in a circle, only the distinct order of elements with respect to each other matters; it does not matter from which point on the circle we start counting them. We can start with A, resulting in ABCD, or we can start with C, resulting in CDAB – they are the same combination around a circle.

If you can arrange four elements in a line in 4! ways (4 options for the first place, 3 for the second, 2 for third, 1 for fourth

= 4 × 3 × 2 × 1 = 4! = 24,

there are fewer options for arranging the same four elements around a circle. We must exclude the identical combinations that were identified above. There are as many repeating combinations as there are slots around the circle. If ABCD is the same combination as BCDA, CDAB, and DABC, this makes four different linear options for everyone’s circular combination. (There are four different options to place the first element, A, without changing the order of the elements with respect to each other). So, in order to find the number of circular permutations, we should divide the number of linear permutations by the number of slots around the circle (or the number of possible ways to place the first element). So, the formula for circular permutations is

where m is the number of slots around the circle. In the case of four elements, there will be

Permutations with Constraints

Some permutations problems may have certain constraints, for example, a certain two elements cannot be placed next to each other. Let’s take an example: Given 5 elements to order, A, B, C, D, and E, with the constraint that elements A and E cannot be placed next to each other, how many ways are there to order the elements?

There are two ways to approach this. First is the classic way of multiplying the options: there are

5 options for placing the first element, A. (Let’s start with the one that is involved in the constraint.) This leaves either 3 or 2 options to place E (because if A is placed in the first or last place, there is only one place next to it that is not available for E; but if A is placed in one of the middle places, there are two places beside A that are closed for E).

There are two “edge” options for A, and three “middle” options for A. This means, that in 2/5 cases E will have 3 options, and in 3/5 cases E will have 2 options. After we’ve placed E, there are 3 options left for B, 2 for C, and 1 for D. Multiply the options:

5 × (2/5 × 3 + 3/5 × 2) × 3 × 2 × 1 = 72.

Now, there is another way to do this. Let’s count the total number of possible arrangements for   5 elements:

5! = 5 × 4 × 3 × 2 × 1 = 120.

Now, let’s exclude the options where A and E are placed together. There are 4 pairs of places that can be occupied by A and E, and 2 options per each place (AE or EA). This makes 8 options for A to be next to E.

If the two places for A and E are defined, there are 3! options to place the remaining elements B, C, and D. So the total number of combinations of 5 elements in which A and E are placed together, is

8 × 3! = 8 × 3 × 2 × 1 = 48.

Therefore, the total number of options to place 5 elements so that A and E are not placed together is

120 – 48 = 72.

Combinatorics and Probability

You might encounter a problem where it is convenient to use combinatorics to calculate probability.

Consider this example: There are 6 different cubes in a box: yellow, red, green, blue, orange, and purple. What is the probability that if you pick 4 cubes out of the box, a yellow and a blue one will be among them? Here, it is convenient to use the probability formula:

The total number of 4-cube combinations is

The number of 4-cube combinations that contain a yellow cube and a blue cube is

We are looking for 4-cube combinations in which 2 cubes are already chosen: a yellow one and a blue one. We need to select the other 2 cubes from the remaining 4 cubes in the box, and there are 4C₂ ways to do this.

Now calculate the probability:

P = 6/15 = 2/5.

 

Key Tips of the Lesson

1. Use the formula for combinations when the order does not matter, and the formula for permutations when the order matters.
2. Sometimes it is more convenient to calculate the probability of the event not occurring to answer the question.