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\cdot 26\cdot 26 = 26^3\) 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

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”.
🔗
Answer.
\(\text{RB}, \text{RG}, \text{RY}, \text{RP}, \text{RR}, \text{BB}, \text{BG}, \text{BY}, \text{BP}, \text{BR}\)
🔗
🔗
🔗
(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.
🔗
Answer 1.
\(5\)
🔗
🔗
Answer 2.
\(5\)
🔗
🔗
Answer 3.
\(10\)
🔗
🔗
🔗
(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.
🔗
Answer 1.
\(2\)
🔗
🔗
Answer 2.
\(5\)
🔗
🔗
Answer 3.
\(10\)
🔗
🔗
🔗
🔗
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?
🔗
🔗
Answer.
\(30\)
🔗
🔗
🔗
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.
🔗
Answer 1.
\(3\)
🔗
🔗
Answer 2.
\(3\)
🔗
🔗
Answer 3.
\(3\)
🔗
🔗
🔗
(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?
🔗
Answer 1.
\(4\)
🔗
🔗
Answer 2.
\(12\)
🔗
🔗
🔗
(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?
🔗
Answer 1.
\(5\)
🔗
🔗
Answer 2.
\(60\)
🔗
🔗
🔗
(d)
How many four-chip sticks are there with no repeated color?
🔗
Answer.
\(120\)
🔗
🔗
🔗
🔗
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?
🔗
🔗
Answer.
\(6\)
🔗
🔗
🔗
(b)
How many different stacks of chips would result in picking up the red, yellow, and green chips?
🔗
Answer.
\(6\)
🔗
🔗
🔗
(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?
🔗
Answer 1.
\(60\)
🔗
🔗
Answer 2.
\(6\)
🔗
🔗
Answer 3.
\(10\)
🔗
🔗
🔗
(d)
How many different pocketfuls of chips are there if you take four chips?
🔗
Answer.
\(5\)
🔗
🔗
🔗
🔗
🔗
🔗

Subsection Counting Sequences

A permutation is a (possible) rearrangement of objects. For example, there are 6 permutations of the letters a, b, c:
\begin{equation*} abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba\text{.} \end{equation*}
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\cdot 2 \cdot 1\text{.}\)
🔗

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 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\) permutations of the 6 letters.
🔗
🔗
🔗
A piece of notation is helpful here: \(n!\text{,}\) 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\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text{.}\) This generalizes:
🔗

Example 3.4.3. Counting Bijective Functions.

How many functions \(f:\{1,2,\ldots,8\} \to \{1,2,\ldots, 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
\begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8} {3 \amp 1 \amp 5 \amp 8 \amp 7 \amp 6 \amp 2 \amp 4}\text{.} \end{equation*}
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 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}\) 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\cdot 6\cdot 5 \cdot 4 = 840\text{.}\)
🔗
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
\begin{equation*} \frac{7!}{3!} = \frac{7\cdot 6\cdot 5\cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = 7 \cdot 6 \cdot 5 \cdot 4\text{.} \end{equation*}
🔗
🔗
🔗
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\text{,}\) and \(n = 7\text{.}\)) 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
\begin{equation*} P(10, 4) = 10\cdot 9 \cdot 8 \cdot 7\text{.} \end{equation*}
🔗
Notice that \(P(10,4)\) starts out looking like \(10!\text{,}\) but we stop after 7. We can formally account for this “stopping” by dividing away the part of the factorial we do not want:
\begin{equation*} P(10,4) = \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{10!}{6!}\text{.} \end{equation*}
🔗
Careful: The factorial in the denominator is not \(4!\) but rather \((10-4)!\text{.}\)
🔗

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\text{,}\) we have \(P(n,n) = \frac{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\} \to \{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\cdot 7 \cdot 6 = P(8,3)\text{.}\)
🔗
What this demonstrates in general is that the number of injections \(f:A \to B\text{,}\) where \(\card{A} = k\) and \(\card{B} = n\text{,}\) is \(P(n,k)\text{.}\)
🔗
🔗
🔗
🔗

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 \(\binom{12}{5}\) 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\cdot 4\cdot 3\cdot 2\cdot 1 = 5!\) ways to arrange the players. So the total number of ways to pick five players for the five positions is
\begin{equation*} \binom{12}{5}\cdot 5! = 792\cdot 120 = 95,040\text{.} \end{equation*}
🔗
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
\begin{equation*} P(12,5) = 12\cdot 11\cdot 10\cdot 9\cdot 8 = 95,040\text{.} \end{equation*}
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\text{?}\) You have \(n\) objects, and you need to choose \(k\) of them. You can do that in \(\binom{n}{k}\) ways.
🔗
Using the multiplicative principle to combine the two steps, we get another formula for \(P(n,k)\text{:}\)
\begin{equation*} P(n,k) = \binom{n }{ k}\cdot k!\text{.} \end{equation*}
🔗
This is HUGE!
🔗
We have a closed formula for \(P(n,k)\) already. We can substitute that in:
\begin{equation*} \frac{n!}{(n-k)!} = \binom{n}{k} \cdot k!\text{.} \end{equation*}
🔗
If we then divide both sides by \(k!\text{,}\) we get a closed formula for \(\binom{n}{k}\text{.}\)
🔗
Another name for the collections of things that \(\binom{n}{k}\) counts is combinations. We say that \(\binom{n}{k}\) counts the number of \(k\)-element combinations of \(n\) elements. Sometimes we even use the notation \(C(n,k)\) instead of \(\binom{n}{k}\text{.}\)
🔗
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 \(\binom{n}{k}\text{.}\) That extra \(k!\) accounts for the fact that \(\binom{n}{k}\) 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 \(\binom{14}{6}\) ways. We can find this number either by using Pascal’s triangle or the closed formula: \(\frac{14!}{8!\cdot 6!} = 3003\text{.}\)
    🔗
    🔗
  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)\text{,}\) which can be calculated as \(\frac{14!}{8!} = 2162160\text{.}\)
    🔗
    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 \(\binom{14}{6}\text{.}\) This makes sense. \(\binom{14}{6}\) 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\cdot 6!\) choices and that is exactly \(2162160\text{.}\)
🔗
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:
\begin{equation*} 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \text{.} \end{equation*}
🔗
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
\begin{equation*} \frac{14 \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9}{6!} \text{.} \end{equation*}
🔗
Note that another way to write this is
\begin{equation*} \frac{14!}{8!\cdot 6!}\text{.} \end{equation*}
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
\begin{equation*} 26, 5, 42, 17, 33\text{.} \end{equation*}
If you were holding the ticket that had numbers \(5, 17, 26, 33, 47\text{,}\) 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) = \binom{52}{5}\text{.}\)
🔗
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)\text{.}\) 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) = \binom{26}{3}\text{.}\)
🔗
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)\text{.}\)
🔗
🔗
🔗
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
\begin{equation*} 1100, ~~ 1010, ~~ 1001, ~~ 0110, ~~ 0101, ~~ 0011\text{.} \end{equation*}
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 \(\binom{n}{k}\) 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,
\begin{equation*} P(n,k) = \binom{n}{k} \cdot k! \end{equation*}
which can be rewritten as,
\begin{equation*} \binom{n}{k} = \frac{P(n,k)}{k!}\text{.} \end{equation*}
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 \div 6 = 4\text{,}\) 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\text{.}\) We know the number of such words is \(P(4,3) = 4\cdot 3 \cdot 2 = 24\text{.}\) 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\text{.}\) 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 \div 6 = 4\) rows. And of course, we are not surprised because \(\binom{4}{3} = 4\text{.}\)
🔗
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\cdot 9\cdot 8\cdot 7\cdot 6 = 30,240\text{.}\) 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,
\begin{equation*} \frac{P(10,5)}{2} = \frac{10\cdot 9\cdot 8\cdot 7\cdot 6}{2} = 15,120\text{.} \end{equation*}
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?
    🔗
    🔗
🔗
Answer 1.
\(\mathop{\rm C}\nolimits\mathopen{}\left(8,4\right)\)
🔗
🔗
Answer 2.
\(2^{8}\)
🔗
🔗
Answer 3.
\(\mathop{\rm P}\nolimits\mathopen{}\left(8,4\right)\)
🔗
🔗
Solution.
  1. \({8 \choose 4} = {70}\) pizzas. We must choose (in no particular order) 4 out of the 8 toppings.
    🔗
    🔗
  2. \(2^{8} = {256}\) pizzas. Say yes or no to each topping.
    🔗
    🔗
  3. \(P(8,4) = {1680}\) ways. Assign each of the 4 spots in the left column to a unique pizza topping.
    🔗
    🔗
🔗
🔗
🔗

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?
🔗
Answer.
\(\mathop{\rm P}\nolimits\mathopen{}\left(45,3\right)\)
🔗
🔗
Solution.
Despite its name, we are not looking for a combination here. The order in which the three numbers appear matters. There are \(P(45,3) = 45\cdot 44 \cdot 43\) different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be \(45^3\)).
🔗
🔗
🔗

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.
    🔗
    🔗
🔗
Answer 1.
\(8^{3}\)
🔗
🔗
Answer 2.
\(\mathop{\rm P}\nolimits\mathopen{}\left(8,3\right)\)
🔗
🔗
Answer 3.
\(\mathop{\rm C}\nolimits\mathopen{}\left(8,3\right)\)
🔗
🔗
Solution.
  1. This is just the multiplicative principle. There are 8 digits which we can select for each of the 3 positions, so we have \(8^3 = {512}\) such numbers.
    🔗
    🔗
  2. Now we have 8 choices for the first number, 7 for the second, etc. So there are \(8 \cdot 7 \cdot \dots \cdot 3 = P(8,3) = {336}\) such numbers.
    🔗
    🔗
  3. To build such a number we simply must select 3 different digits. After doing so, there will only be one way to arrange them into increasing order. Thus there are \({8 \choose 3} = {56}\) such numbers.
    🔗
    🔗
🔗
🔗
🔗

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?
    🔗
    🔗
🔗
Answer 1.
\(\mathop{\rm P}\nolimits\mathopen{}\left(18,14\right)\)
🔗
🔗
Answer 2.
\(\mathop{\rm C}\nolimits\mathopen{}\left(18,14\right)\)
🔗
🔗
Solution.
  1. We can write the answer as \(P(18,14) = 18 \cdot 17 \cdot 16 \cdot \dots \cdot 5\) , which is the same as \(\frac{18!}{4!}\) . Or, if you think of picking the 14 books and then arranging those 14, you can write this as \(\binom{18}{14}\cdot 14!\) . Note, that since any order is acceptable, we are distinguishing between different orders, so a permutation is appropriate here.
    🔗
    🔗
  2. Here we just need to select the books, and have no choice as how to arrange them. So the answer is just \(\binom{18}{14}\)
    🔗
    🔗
🔗
🔗
🔗

5.

An anagram of a word is just a rearrangement of its letters. How many different anagrams of “troublemakings” are there?
🔗
Answer.
\(14!\)
🔗
🔗
Solution.
Since there are 14 different letters in “troublemakings”, we have 14 choices for the first letter, 13 for the next, 12 for the next, and so on. Thus there are \(14!\) anagrams.
🔗
🔗
🔗

6.

How many anagrams are there of the word “voodoo” that start with the letter “v”?
🔗
Answer.
\(\mathop{\rm C}\nolimits\mathopen{}\left(5,1\right)\)
🔗
🔗
Solution.
After the first letter (namely, v), we must rearrange the remaining 5 letters. There are only two choices of letter now, so this is really just a bit-string question where one of the letters is 0, and the other letter is 1. Thus there are \({5 \choose 1} = {5}\) anagrams starting with “v”.
🔗
🔗
🔗

7.

How many anagrams are there of “academia”?
🔗
Answer.
\(\mathop{\rm C}\nolimits\mathopen{}\left(8,3\right)\mathopen{}\left(5!\right)\)
🔗
🔗
Solution.
First, decide where to put the “a”s. There are 8 positions, and we must choose 3 of them to fill with an “a”. This can be done in \(\binom{8}{3}\) ways. The remaining 5 spots all get a different letter, so there are \(5!\) ways to finish off the anagram. This gives a total of \(\binom{8}{3}\cdot 5!\) anagrams. Strangely enough, this is 6720, which is also equal to \(P(8,5)\text{.}\) To get the answer that way, start by picking one of the 8 positions to be filled by the first non-”a” letter, one of the remaining 7 positions to be filled by the next, and so on. Then put “a”s in the remaining 3 positions.
🔗
🔗
🔗

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 (who are among the 24 golfers already). How many ways can you do this?
    🔗
    🔗
🔗
Answer 1.
\(3.24668\times 10^{15}\mathop{\rm C}\nolimits\mathopen{}\left(4,4\right)\)
🔗
🔗
Answer 2.
\(6!\cdot 1.37225\times 10^{11}\)
🔗
🔗
Solution.
  1. \({24 \choose 4}\cdot {20 \choose 4} \cdot {16 \choose 4} \cdot \dots \cdot{4 \choose 4}\) ways. Pick 4 out of 24 people to be in the first foursome, then 4 of the remaining 20 for the second foursome, and so on (use the multiplicative principle to combine).
    🔗
    🔗
  2. \(6!{18 \choose 3}\cdot {15 \choose 3}\cdot {12 \choose 3} \cdot \dots \cdot {3 \choose 3}\) ways. First determine the tee time of the 6 board members, then select 3 of the 18 non-board members to golf with the first board member, then 3 of the remaining 15 to golf with the second, and so on.
    🔗
    🔗
🔗
🔗
🔗

9.

How many different seating arrangements are possible for King Arthur and his 16 knights around their round table?
🔗
Answer.
\(16!\)
🔗
🔗
Solution.
\(16!\text{.}\) There are 17 people seated around the table, but it does not matter where King Arthur sits, only who sits to his left, two seats to his left, and so on.
🔗
🔗
🔗

10.

Consider sets \(A\) and \(B\) with \(|A| = 14\) and \(|B| = 21\text{.}\)
  1. How many functions \(f: A \to B\) are there?
    🔗
    🔗
  2. How many functions \(f: A \to B\) are injective?
    🔗
    🔗
🔗
Answer 1.
\(21^{14}\)
🔗
🔗
Answer 2.
\(\mathop{\rm P}\nolimits\mathopen{}\left(21,14\right)\)
🔗
🔗
Solution.
  1. \(21^{14}\) functions. There are 21 choices for the image of each element in the domain.
    🔗
    🔗
  2. \(P(21, 14)=21\cdot20\cdot19\cdot \dots \cdot 7\) injective functions. There are 21 choices for the image of the first element of the domain, then only 20 choices for the second, 19 for the third, and so on.
    🔗
    🔗
🔗
🔗
🔗

11.

Consider functions \(f: {\left\{1,2,3,4,5,6\right\}}\to {\left\{1,2,3,4,5,6,7\right\}}\text{.}\)
  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 \(\renewcommand{\v}{\vtx{above}{}}a \lt b\) then \(\renewcommand{\v}{\vtx{above}{}}f(a) \lt f(b)\text{,}\) or in other words, the outputs get larger as the inputs get larger.
    🔗
    🔗
🔗
Answer 1.
\(7^{6}\)
🔗
🔗
Answer 2.
\(\mathop{\rm P}\nolimits\mathopen{}\left(7,6\right)\)
🔗
🔗
Answer 3.
\(\mathop{\rm C}\nolimits\mathopen{}\left(7,6\right)\)
🔗
🔗
Solution.
  1. \(7^{6} = {117649}\) functions, since there are 7 choices of where to send each of the 6 elements of the domain.
    🔗
    🔗
  2. \(P(7, 6) = 7\cdot 6 \cdot \cdots \cdot 2 = {5040}\) functions, since outputs cannot be repeated.
    🔗
    🔗
  3. \({7 \choose 6} = {7}\) functions. Since the function must be injective and increasing, we just need to select the 6 distinct elements of the range from the 7 elements of the codomain. Once these have been selected, we must put the smallest as the image of 1, the next smallest as the image of 2, and so on (doing this does not increase the number of functions, since there is one choice for how this event can occur).
    🔗
    🔗
🔗
🔗
🔗
🔗

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.
🔗
🔗
Solution.
120.
🔗
🔗
🔗

2.

We have seen that the formula for \(P(n,k)\) is \(\dfrac{n!}{(n-k)!}\text{.}\) 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)\text{.}\)
    🔗
    🔗
  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) = \frac{n!}{(n-k)!}\) using the variables \(n\) and \(k\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
🔗
PrevTopNext
Feedback