Skip to main content
Logo image

Discrete Mathematics An Open Introduction, 4th Edition

Oscar Levin

Section 3.4 Combinations and Permutations

Subsection Section Preview

Investigate!
You have decided to decorate your magic wand with bands of different colored tape. You have 10 different colors to choose from, and you will use five of them to create five different stripes of color. How many different wand designs are possible?
🔗
🔗
The product principle gives us a way to count the number of outcomes when each outcome is made by combining smaller pieces. A typical example of this is to count the number of three-letter “words”; each outcome (word) we count is made up of a combination of three smaller pieces (letters). Since there are 26 choices for each smaller piece, there are 26⋅26⋅26=263 possible outcomes.
🔗
The product principle does not require that each piece that is being combined be chosen from a set of the same size. We will use this observation to create a standard way to count outcomes when the pieces are chosen from a fixed set, but without allowing for any piece to be used more than once. For example, we can ask how many 3-letter words there are that contain distinct letters.
🔗
These arrangements are called permutations. We will also consider another counting technique where we count combinations, which is related but counts something different. We will explore how these two counting techniques are related and how they can be used to solve a wide range of counting problems.
🔗

Worksheet Preview Activity
A4US

You have a bunch of poker chips that come in five different colors: red, blue, green, purple, and yellow.
🔗
1.
How many two-chip stacks are possible where the bottom chip must be red or blue?
🔗
(a)
List all possible two-chip stacks. For example, the stack with a red chip on bottom and a green chip on top can be listed as “RG”.
🔗
(b)
Using the additive principle, we notice that there are stacks that have blue on the bottom, another stacks that have red on the bottom, so there are a total of possible stacks.
🔗
(c)
If we use the multiplicative principle, then there are choices for the bottom chip and choices for the top chip, so there are possible stacks.
🔗
🔗
2.
How many different three-chip stacks are possible if the bottom chip must be red or blue and the top chip must be green, purple, or yellow?
🔗
Hint.
How does this question relate to the previous question? Is there something we can do to the 10 two-chip stacks to make them into three-chip stacks?
🔗
3.
How many different three-chip stacks are there in which no color is repeated?
🔗
(a)
First, how many three-chip stacks with no repeated color have blue on the bottom and green in the middle?
🔗
And how many three-chip stacks with no repeated color have blue on the bottom and yellow in the middle?
🔗
In fact, for any stack with blue on the bottom and some other color in the middle, there are possible stacks.
🔗
(b)
If we insist that blue is on the bottom, how many choices do we have for the color of the middle chip?
🔗
Combining this with the answer from the previous question, how many three-chip stacks with no repeated color have blue on the bottom?
🔗
(c)
Of course, we didn’t need to start with blue on the bottom. How many choices do we have for the color of the bottom chip?
🔗
So how many three-chip stacks with no repeated color are there?
🔗
(d)
How many four-chip sticks are there with no repeated color?
🔗
🔗
4.
Suppose you wanted to take three chips with different colors and put them in your pocket.
🔗
(a)
One outcome is taking the blue, green, and purple chips. How many of the three-chip stacks of different color chips correspond to this single pocketful?
🔗
Hint.
With these three colors, how many choices do you have for which chip is on the bottom? In the middle? On top?
(b)
How many different stacks of chips would result in picking up the red, yellow, and green chips?
🔗
(c)
So of the possible three-chip stacks, we can group the chips into groups of size , where each group corresponds to the same pocketful of chips. How many different pocketfuls of chips are there?
🔗
(d)
How many different pocketfuls of chips are there if you take four chips?
🔗
🔗
🔗
🔗

Subsection Counting Sequences

A permutation is a (possible) rearrangement of objects. For example, there are 6 permutations of the letters a, b, c:
🔗
abc,  acb,  bac,  bca,  cab,  cba.
In terms of our discrete structures, each permutation is really a sequence or tuple of a fixed length.
🔗
🔗
We know that we have them all listed above —there are 3 choices for which letter we put first, then 2 choices for which letter comes next, which leaves only 1 choice for the last letter. The multiplicative principle says we multiply 3⋅2⋅1.
🔗

Example 3.4.1.

How many sequences (permutations) are there of the letters a, b, c, d, e, f?
🔗
Solution.
We do NOT want to try to list all of the length 6 sequences of these letters. However, if we did, we would need to pick a letter to write down first. There are 6 choices for that letter. For each choice of the first letter, there are 5 choices for the second letter (we cannot repeat the first letter; we are rearranging letters and only have one of each), and for each of those, there are 4 choices for the third, 3 choices for the fourth, 2 choices for the fifth, and finally only 1 choice for the last letter. So there are 6⋅5⋅4⋅3⋅2⋅1=720 permutations of the 6 letters.
🔗
A piece of notation is helpful here: n!, read “n factorial”, is the product of all positive integers less than or equal to n (for reasons of convenience, we also define 0! to be 1). So the number of permutations of 6 letters, as seen in the previous example is 6!=6⋅5⋅4⋅3⋅2⋅1. This generalizes:
🔗

Example 3.4.3. Counting Bijective Functions.

How many functions f:{1,2,…,8}→{1,2,…,8} are bijective?
🔗
Solution.
Remember what it means for a function to be bijective: Each element in the codomain must be the image of exactly one element of the domain. Using two-line notation, we could write one of these bijections as
f=(1234567831587624).
What we are really doing is just rearranging the elements of the codomain, so we are creating a permutation of 8 elements. In fact, “permutation” is another term used to describe bijective functions from a finite set to itself.
If you believe this, then you see the answer must be 8!=8⋅7⋅⋯⋅1=40320. You can see this directly as well: For each element of the domain, we must pick a distinct element of the codomain to map to. There are 8 choices for where to send 1, then 7 choices for where to send 2, and so on. We multiply using the multiplicative principle.
🔗
Sometimes we do not want to permute all of the letters/numbers/elements we are given.
🔗

Example 3.4.4.

How many four-letter “words” can you make from the letters a through g, with no repeated letters?
🔗
Solution.
This is just like the problem of permuting four letters, only now we have more choices for each letter. For the first letter, there are 7 choices. For each of those, there are 6 choices for the second letter. Then there are 5 choices for the third letter and 4 choices for the last letter. The total number of words is 7⋅6⋅5⋅4=840.
This is not 7! because we never multiplied by 3, 2, or 1. We could write it using 7! though, if we cancel the 3, 2, and 1. Thus we could write the answer as
7!3!=7⋅6⋅5⋅4⋅3⋅2⋅13⋅2⋅1=7⋅6⋅5⋅4.
🔗
In general, we can ask how many permutations exist of k objects choosing those objects from a larger collection of n objects. (In the example above, k=4, and n=7.) We write this number P(n,k) and sometimes call it a k-permutation of n elements.
🔗
From the example above, we see that to compute P(n,k) we must apply the multiplicative principle to k numbers, starting with n and counting backwards. For example
🔗
P(10,4)=10⋅9⋅8⋅7.
🔗
Notice that P(10,4) starts out looking like 10!, but we stop after 7. We can formally account for this “stopping” by dividing away the part of the factorial we do not want:
🔗
P(10,4)=10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅16⋅5⋅4⋅3⋅2⋅1=10!6!.
🔗
Careful: The factorial in the denominator is not 4! but rather (10−4)!.
🔗

Definition 3.4.5. k-permutations of n elements.

P(n,k) is the number of k-permutations of n elements, the number of ways to arrange k objects chosen from n distinct objects.
🔗
🔗
Note that when n=k, we have P(n,n)=n!(n−n)!=n! (since we defined 0! to be 1). This makes sense —we already know n! gives the number of permutations of all n objects.
🔗

Example 3.4.7. Counting injective functions.

How many functions f:{1,2,3}→{1,2,3,4,5,6,7,8} are injective?
🔗
Solution.
Note that it doesn’t make sense to ask for the number of bijections here, as there are none (because the codomain is larger than the domain, there are no surjections). But for a function to be injective, we just can’t use an element of the codomain more than once.
We need to pick an element from the codomain to be the image of 1. There are 8 choices. Then we need to pick one of the remaining 7 elements to be the image of 2. Finally, one of the remaining 6 elements must be the image of 3. So the total number of functions is 8⋅7⋅6=P(8,3).
What this demonstrates in general is that the number of injections f:A→B, where |A|=k and |B|=n, is P(n,k).
🔗
🔗

Subsection Counting Sets

Let’s consider another way to count sequences: First count sets, then arrange them.
🔗

Example 3.4.8.

Your basketball team has 12 players. Assuming everyone can play every position, how many ways can you choose 5 players to be on the court at the same time?
🔗
Solution.
This question is actually too vague. Do we mean how many ways can we select five players? Or do we mean how many ways can we pick five players to fill the five positions?
 2 
I’m told the five positions are called point guard, shooting guard, small forward, power forward, and center. Who knew?
Let’s answer both of these questions.
First, if we just want to select five out of the 12 players, that is just like picking five out of 12 pizza toppings (although less delicious). We know that there are (125) ways to do this, and from Pascal’s triangle we know that this is 792.
On the other hand, if we wanted to pick five players for the five different positions,... well, we could start by picking one of the 792 different sets of five players, and then permute them into the five positions. Of the five players on the court, we pick one of the five to be the point guard, then one of the remaining four to be the shooting guard, and so on. This gives us 5⋅4⋅3⋅2⋅1=5! ways to arrange the players. So the total number of ways to pick five players for the five positions is
(125)⋅5!=792⋅120=95,040.
Wait. We could have found that number directly. Without choosing the five players first, we have 12 choices for the point guard, then 11 choices for the shooting guard, and so on. So the total number of ways to pick five players for the five positions is simply the permutation
P(12,5)=12⋅11⋅10⋅9⋅8=95,040.
Thank goodness that is the same answer!
🔗
The example above illustrates a second way to compute the number of k-permutations of n elements: First select which k elements will be in the permutation, then count how many ways there are to arrange them. Once you have selected the set of k objects, we know there are k! ways to arrange (permute) them. But how do you select k objects from the n? You have n objects, and you need to choose k of them. You can do that in (nk) ways.
🔗
Using the multiplicative principle to combine the two steps, we get another formula for P(n,k):
🔗
P(n,k)=(nk)⋅k!.
🔗
This is HUGE!
🔗
We have a closed formula for P(n,k) already. We can substitute that in:
🔗
n!(n−k)!=(nk)⋅k!.
🔗
If we then divide both sides by k!, we get a closed formula for (nk).
🔗
Another name for the collections of things that (nk) counts is combinations. We say that (nk) counts the number of k-element combinations of n elements. Sometimes we even use the notation C(n,k) instead of (nk).
🔗
Clearly combinations and permutations are very closely related. The formulas to count each are very similar; there is just an extra k! in the denominator of (nk). That extra k! accounts for the fact that (nk) does not distinguish between the different orders that the k objects can appear in. We are just selecting (or choosing) the k objects, not arranging them.
🔗

Example 3.4.10.

You decide to have a dinner party. Even though you are incredibly popular and have 14 different friends, you only have enough chairs to invite 6 of them.
🔗
  1. How many choices do you have for which 6 friends to invite?
  2. What if you need to decide not only which friends to invite but also where to seat them along your long table? How many choices do you have then?
🔗
Solution.
  1. You must simply choose 6 friends from a group of 14. This can be done in (146) ways. We can find this number either by using Pascal’s triangle or the closed formula: 14!8!⋅6!=3003.
  2. Here you must count all the ways you can permute 6 friends chosen from a group of 14. So the answer is P(14,6), which can be calculated as 14!8!=2162160.
    Notice that we can think of this counting problem as a question about counting functions: How many injective functions are there from your set of 6 chairs to your set of 14 friends (the functions are injective because you can’t have a single chair go to two of your friends).
How are these numbers related? Notice that P(14,6) is much larger than (146). This makes sense. (146) picks 6 friends, but P(14,6) arranges the 6 friends as well as picks them. In fact, we can say exactly how much larger P(14,6) is. In both counting problems we choose 6 out of 14 friends. For the first one, we stop there, at 3003 ways. But for the second counting problem, each of those 3003 choices of 6 friends can be arranged in exactly 6! ways. So now we have 3003⋅6! choices and that is exactly 2162160.
Alternatively, look at the first problem another way. We want to select 6 out of 14 friends, but we do not care about the order they are selected in. To select 6 out of 14 friends, we might try this:
14⋅13⋅12⋅11⋅10⋅9.
This is a reasonable guess, since we have 14 choices for the first guest, then 13 for the second, and so on. But the guess is wrong (in fact, that product is exactly 2162160=P(14,6)). It distinguishes between the different orders in which we could invite the guests. To correct for this, we could divide by the number of different arrangements of the 6 guests (so that all of these would count as just one outcome). There are precisely 6! ways to arrange 6 guests, so the correct answer to the first question is
14⋅13⋅12⋅11⋅10⋅96!.
Note that another way to write this is
14!8!⋅6!.
which is what we had originally.
🔗
Perhaps “combination” is a misleading label. We don’t mean it like a combination lock (where the order would definitely matter). Perhaps a better metaphor is a combination of flavors — you just need to decide which flavors to combine, not the order in which to combine them.
🔗
So how do you know when to use a combination and when to use a permutation?
🔗

Does order matter?

Almost every source you look at about combinations and permutations will make some variation of the following claim.
🔗
Use a permutation when the order matters, and use a combination when the order does not matter.
🔗
What does this even mean? And why is it an absolutely awful way to distinguish between the two counting techniques? Let’s explore with an example.
🔗
Suppose you are proposing a new lottery game. In the game, five numbered balls will be randomly shot out of the machine that holds balls numbered 1 to 50. If a player correctly picks the five numbers that come out, they win the jackpot.
🔗
Of course, we want to know the odds of winning this lottery game, which requires us to know how many different outcomes there are. The balls fly out of the machine randomly, so one result might be to get the balls
🔗
26,5,42,17,33.
If you were holding the ticket that had numbers 5,17,26,33,47, do you expect to have won? Most lottery games would say you have, since you have the same numbers, just in a different order.
🔗
🔗
In this sense, the order of the numbers does not matter. A better way to say this is that any order of the same numbers is considered the same outcome, and is counted only once. So really, we are counting the sets of five numbers, not the sequences of five numbers. Each outcome is a combination, so the number of outcomes should be C(52,5)=(525).
🔗
On the other hand, if we must pick the numbers in the same order they come out of the machine, then we are really matching a sequence of numbers to a sequence of numbers. The number of sequences is P(52,5). In this case, we would say that the order matters.
🔗
Okay, so far so good. But what about the following example?
🔗
Example 3.4.11.
How many three letter “words” are there in which
🔗
  1. the letters appear in alphabetical order?
  2. the letters in the word can come in any order?
🔗
Solution.
Does “order matter” for the first question? In some sense, absolutely! We only want to count words where the letters are in the correct order. But from the standard combination/permutation sense of order mattering, it does not.
Much better would be to ask ourselves whether we should represent each outcome as a set of letters or a sequence of letters. It is true that words are a sequence of letters, but are we counting all possible sequences? Nope, just one sequence for each set of letters. Ah, yes, set of letters. Each outcome corresponds exactly to one set of three letters. We are counting sets, so we count combinations. The number of outcomes is C(26,3)=(263).
For the second question, it might look like the order shouldn’t matter. Well, it doesn’t matter to the machine spitting out the letters, but it would matter if we were trying to match the letters. No, let’s think about it like this: Are we counting every possible sequence of letters? Yes! So these are permutations, and the number of outcomes is P(26,3).
🔗
Another deceptive use of order appears when counting bit strings. Recall that an n-bit string of weight k is a string of n bits (0s and 1s) in which k of the bits are 1s. For example, the 4-bit strings of weight 2 are
🔗
1100,  1010,  1001,  0110,  0101,  0011.
Does order matter for bit strings? Of course it does! It is the only thing that matters. All of the strings above contain exactly the same number of 0s and 1s; they are only distinguished by the order of the bits.
🔗
🔗
And yet, the number of n-bit strings of weight k is (nk) and NOT a permutation. What is going on here?
🔗
Nothing is broken; we are just not thinking about the right objects about which to consider the order. When we choose k out of n things for a bit string, it is the positions we are choosing (to fill with 1s, say). It does not matter in what order we choose those positions, just what set of positions we choose. That is, the bit string 1001 is the result of choosing positions 1 and 4 to put 1s into. If we chose positions 4 and then 1, we would get the same bit string.
🔗
To summarize, the question of whether order matters can lead us astray when deciding between a combination and a permutation. Instead, we should decide whether the outcomes we are counting are sets or sequences. If we are counting sets, think combination. If we are counting sequences, think permutation.
🔗
🔗
🔗

Subsection The Quotient Principle

We have two ways to write the numerical relationship between the numbers of combinations and permutations. Using the product principle, we have,
🔗
P(n,k)=(nk)⋅k!
which can be rewritten as,
🔗
(nk)=P(n,k)k!.
This second formula suggests that there might be a quotient principle that we could use to justify it.
🔗
🔗
Let’s think about what division means. One way to think of the division problem 24÷6=4, for example, is saying that if you have 24 things that you divide into groups of size 6, the number of groups will be 4.
 3 
The other way to interpret this statement is that if you divide 24 things into six groups, then each group will have size 4, but this is less useful for what we will do.
🔗
Now let’s look at all the 3-permutations of a set of size 4: For example, all the ways to make 3-letter words using the letters a,b,c,d. We know the number of such words is P(4,3)=4⋅3⋅2=24. It is helpful to actually list all these out.
🔗
abc acb bac bca cab cba
abd adb bad bda dab dba
acd adc cad cda dac dca
bcd bdc cbd cdb dbc dcb
Look at the first row. What do all these permutations have in common? These are exactly the permutations that use the letters a,b,c in different orders. It is not surprising that there are 6 of these, since the number of ways to arrange three elements is 3!=6. Similarly, the second row has 6 permutations that use the letters a,b,d in different orders, and so on.
🔗
The point is, if we wanted to just count how many sets of three of the four letters we have, each set corresponds exactly to one of the rows in the table. There are 24 elements in the table, and 6 elements in each row, so there must be 24÷6=4 rows. And of course, we are not surprised because (43)=4.
🔗
A more mathematically rigorous explanation for this phenomenon is to use the language of equivalence relations and partitions from Section 2.6. We start with permutations, and then we define an equivalence relation on the permutations by saying two permutations are equivalent provided they contain exactly the same elements. From the equivalence relation we get a partition of our set of permutations into equivalence classes. The combinations we want to count are precisely the equivalence classes. Since each equivalence class has the same size, we can find the number of classes by dividing the number of permutations by the size of each class.
🔗
This sort of quotient principle is also useful for solving questions where the answer isn’t obviously either a permutation or combination.
🔗

Example 3.4.12.

You have decided to decorate your magic wand with bands of different colored tape. You have 10 different colors to choose from, and you will use five of them to create five different stripes of color. How many different wand designs are possible?
🔗
Solution.
Our first attempt to solve this problem might be to think of each outcome we are trying to count as a 5-permutation of 10 colors. That would give us an answer of P(10,5)=10⋅9⋅8⋅7⋅6=30,240. So why is this not correct? Let’s start making a list of the outcomes that are possible.
  1. Red, blue, green, yellow, orange.
  2. Red, blue, green, yellow, purple.
  3. Blue, green, red, yellow, orange.
  4. Orange, yellow, green, blue, red.
  5. etc.
While starting this list, perhaps we asked ourselves whether red, red, blue, blue, red should be on the list, and recognized that it shouldn’t. Another thing we might have considered is whether items 1 and 3 are really different. They are, since one wand has red as an outside color while the other one does not.
But what about items 1 and 4? They have the same five colors, but in a different order. However, if you were to spin the magic wand around, like magicians are apt to do, you could easily end up with wand 4 from wand 1. Aha! We see that each wand is counted exactly twice in our list of permutations: two permutations are equivalent if they are just the reverse of each other.
Since we can group the permutations into groups of size 2, and each group corresponds to a single wand, we see that the correct answer is,
P(10,5)2=10⋅9⋅8⋅7⋅62=15,120.
Tada!
🔗
🔗

Reading Questions Reading Questions

1.

True or false: The number of sequences of two distinct digits from 0-9 is twice the number of sets of two distinct digits from 0-9. Briefly explain.
🔗
🔗

2.

True or false: The number of sequences of three distinct digits from 0-9 is 3 times the number of sets of three distinct digits from 0-9. Briefly explain.
🔗
🔗

3.

What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
🔗
🔗
🔗

Exercises Practice Problems

1.

A pizza parlor offers 8 toppings.
🔗
  1. How many 4-topping pizzas could they put on their menu? Assume double toppings are not allowed.
  2. How many total pizzas are possible, with between zero and 8 toppings (but not double toppings) allowed?
  3. The pizza parlor will list the 8 toppings in two equal-sized columns on their menu. How many ways can they arrange the toppings in the left column?
🔗
🔗

2.

A combination lock consists of a dial with 45 numbers on it. To open the lock, you turn the dial to the right until you reach the first number, then to the left until you get to the second number, then to the right again to the third number. The numbers must be distinct. How many different combinations are possible?
🔗
🔗

3.

Using the digits 2 through 9, find the number of different 3-digit numbers such that:
🔗
  1. Digits can be used more than once.
  2. Digits cannot be repeated, but can come in any order.
  3. Digits cannot be repeated and must be written in increasing order.
🔗
🔗

4.

In an attempt to clean up your room, you have purchased a new floating shelf to put some of your 18 books you have stacked in a corner. These books are all by different authors. The new book shelf is large enough to hold 14 of the books. Careful: Before answering the next two questions, ask yourself which answer should be larger.
🔗
  1. How many ways can you select and arrange 14 of the 18 books on the shelf? Notice that here we will allow the books to end up in any order.
  2. How many ways can you arrange 14 of the 18 books on the shelf if you insist they must be arranged alphabetically by author?
🔗
🔗

5.

An anagram of a word is just a rearrangement of its letters. How many different anagrams of “troublemakings” are there?
🔗
🔗

6.

How many anagrams are there of the word “voodoo” that start with the letter “v”?
🔗
🔗

7.

How many anagrams are there of “academia”?
🔗
🔗

8.

On a business retreat, your company of 24 businessmen and businesswomen goes golfing.
🔗
  1. You need to divide up into foursomes (groups of 4 people): a first foursome, a second foursome, and so on. How many ways can you do this?
  2. After all your hard work, you realize that in fact, you want each foursome to include one of the 6 Board members. How many ways can you do this?
🔗
🔗

9.

How many different seating arrangements are possible for King Arthur and his 16 knights around their round table?
🔗
🔗

10.

Consider sets A and B with |A|=14 and |B|=21.
🔗
  1. How many functions f:A→B are there?
  2. How many functions f:A→B are injective?
🔗
🔗

11.

Consider functions f:{1,2,3,4,5,6}→{1,2,3,4,5,6,7}.
🔗
  1. How many functions are there total?
  2. How many functions are injective?
  3. How many of the injective functions are increasing? To be increasing means that if a<b then f(a)<f(b), or in other words, the outputs get larger as the inputs get larger.
🔗
🔗
🔗

Exercises Additional Exercises

1.

How many triangles are there with vertices from the points shown below? Note that we are not allowing degenerate triangles – ones with all three vertices on the same line – but we do allow non-right triangles. Explain why your answer is correct.
🔗
Five equally spaced dots in a vertical line and six additional equally spaced dots extending to the right in a horizontal line from the lowest dot (forming a right angle).
Hint.
If you pick any three points, you can get a triangle, unless those three points are all on the x-axis or on the y-axis. There are other ways to start this as well, and any correct method should give the same answer.
🔗

2.

We have seen that the formula for P(n,k) is n!(n−k)!. Your task here is to explain why this is the right formula.
🔗
  1. Suppose you have 12 chips, each a different color. How many different stacks of 5 chips can you make? Explain your answer and why it is the same as using the formula for P(12,5).
  2. Using the scenario of the 12 chips again, what does 12! count? What does 7! count? Explain.
  3. Explain why it makes sense to divide 12! by 7! when computing P(12,5) (in terms of the chips).
  4. Does your explanation work for numbers other than 12 and 5? Explain the formula P(n,k)=n!(n−k)! using the variables n and k.
🔗
🔗
🔗
You have attempted 1 of 19 activities on this page.
🔗
PrevTopNext