Combinations and Permutations

Section1.3Combinations and Permutations

Investigate!8

You have a bunch of chips which come in five different colors: red, blue, green, purple and yellow.

How many different two-chip stacks can you make if the bottom chip must be red or blue? Explain your answer using both the additive and multiplicative principles.
How many different three-chip stacks can you make if the bottom chip must be red or blue and the top chip must be green, purple or yellow? How does this problem relate to the previous one?
How many different three-chip stacks are there in which no color is repeated? What about four-chip stacks?
Suppose you wanted to take three different colored chips and put them in your pocket. How many different choices do you have? What if you wanted four different colored chips? How do these problems relate to the previous one?

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. \end{equation*}

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{.}\)

Example1.3.1

How many permutations are there of the letters a, b, c, d, e, f?

Solution

We do NOT want to try to list all of these out. 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 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 permutation 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:

Permutations of \(n\) elements

There are \(n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1\) permutations of \(n\) (distinct) elements.

Example1.3.2Counting 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} \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.

Example1.3.3

How many 4 letter “words” can you make from the letters a through f, with no repeated letters?

Solution

This is just like the problem of permuting 4 letters, only now we have more choices for each letter. For the first letter, there are 6 choices. For each of those, there are 5 choices for the second letter. Then there are 4 choices for the third letter, and 3 choices for the last letter. The total number of words is \(6\cdot 5\cdot 4 \cdot 3 = 360\text{.}\) This is not \(6!\) because we never multiplied by 2 and 1. We could start with \(6!\) and then cancel the 2 and 1, and thus write \(\frac{6!}{2!}\text{.}\)

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 = 6\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. \end{equation*}

Notice again 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!}. \end{equation*}

Careful: The factorial in the denominator is not \(4!\) but rather \((10-4)!\text{.}\)

\(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.

\begin{equation*} P(n,k) = \frac{n!}{(n-k)!}. \end{equation*}

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.

Example1.3.4Counting 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{.}\)

Here is another way to find 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 \(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 \({n \choose k}\) ways. Then for each choice of those \(k\) elements, we can permute them in \(k!\) ways. Using the multiplicative principle, we get another formula for \(P(n,k)\text{:}\)

\begin{equation*} P(n,k) = {n \choose k}\cdot k!. \end{equation*}

Now since we have a closed formula for \(P(n,k)\) already, we can substitute that in:

\begin{equation*} \frac{n!}{(n-k)!} = {n \choose k} \cdot k!. \end{equation*}

If we divide both sides by \(k!\) we get a closed formula for \({n \choose k}\text{.}\)

Closed formula for \({n \choose k}\)

\begin{equation*} {n \choose k} = \frac{n!}{(n-k)!k!} \end{equation*}

We say \(P(n,k)\) counts permutations, and \({n \choose k}\) counts combinations. The formulas for each are very similar, there is just an extra \(k!\) in the denominator of \({n \choose k}\text{.}\) That extra \(k!\) accounts for the fact that \({n \choose 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. 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.

To further illustrate the connection between combinations and permutations, we close with an example.

Example1.3.5

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.

How many choices do you have for which 6 friends to invite?
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

You must simply choose 6 friends from a group of 14. This can be done in \({14 \choose 6}\) ways. We can find this number either by using Pascal's triangle or the closed formula: \(\frac{14!}{8!\cdot 6!} = 3003\text{.}\)
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!} = 2192190\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 \({14 \choose 6}\text{.}\) This makes sense. \({14 \choose 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 \(2192190\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. \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 \(2192190 = 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!}. \end{equation*}

Note that another way to write this is

\begin{equation*} \frac{14!}{8!\cdot 6!}. \end{equation*}

which is what we had originally.

SubsectionExercises

1

A pizza parlor offers 10 toppings.

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

Solution

\({10 \choose 3} = 120\) pizzas. We must choose (in no particular order) 3 out of the 10 toppings.
\(2^{10} = 1024\) pizzas. Say yes or no to each topping.
\(P(10,5) = 30240\) ways. Assign each of the 5 spots in the left column to a unique pizza topping.

2

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

Solution

Despite its name, we are not looking for a combination here. The order in which the three numbers appears matters. There are \(P(40,3) = 40\cdot 39 \cdot 38\) different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be \(40^3\)).

3

Using the digits 2 through 8, find the number of different 5-digit numbers such that:

Digits can be used more than once.
Digits cannot be repeated, but can come in any order.
Digits cannot be repeated and must be written in increasing order.
Which of the above counting questions is a combination and which is a permutation? Explain why this makes sense.

4

How many triangles are there with vertices from the points shown below? Note, 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.

Hint

You need exactly two points on either the \(x\)- or \(y\)-axis, but don't over-count the right triangles.

5

How many quadrilaterals can you draw using the dots below as vertices (corners)?

Solution

\({7\choose 2}{7\choose 2} = 441\) quadrilaterals. We must pick two of the seven dots from the top row and two of the seven dots on the bottom row. However, it does not make a difference which of the two (on each row) we pick first because once these four dots are selected, there is exactly one quadrilateral that they determine.

6

How many of the quadrilaterals possible in the previous problem are:

Squares?
Rectangles?
Parallelograms?
Trapezoids?²Here, as in calculus, a trapezoid is defined as a quadrilateral with at least one pair of parallel sides. In particular, parallelograms are trapezoids.
Trapezoids that are not parallelograms?

Solution

5 squares. You need to skip exactly one dot on the top and on the bottom to make the side lengths equal. Once you pick a dot on the top, the other three dots are determined.
\({7 \choose 2}\) rectangles. Once you select the two dots on the top, the bottom two are determined.
This is tricky since you need to worry about running out of space. One way to count: break into cases by the location of the top left corner. You get \({7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\) parallelograms.
All of them
\({7\choose 2}{7\choose 2} - \left[ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right]\text{.}\) All of them, except the parallelograms.

7

An anagram of a word is just a rearrangement of its letters. How many different anagrams of “uncopyrightable” are there? (This happens to be the longest common English word without any repeated letters.)

8

How many anagrams are there of the word “assesses” that start with the letter “a”?

Solution

After the first letter (a), we must rearrange the remaining 7 letters. There are only two letters (s and e), so this is really just a bit-string question (think of s as 1 and e as 0). Thus there \({7 \choose 2} = 21\) anagrams starting with “a”.

9

How many anagrams are there of “anagram”?

10

On a business retreat, your company of 20 businessmen and businesswomen go golfing.

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?
After all your hard work, you realize that in fact, you want each foursome to include one of the five Board members. How many ways can you do this?

Solution

\({20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\) ways. Pick 4 out of 20 people to be in the first foursome, then 4 of the remaining 16 for the second foursome, and so on (use the multiplicative principle to combine).
\(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\) ways. First determine the tee time of the 5 board members, then select 3 of the 15 non board members to golf with the first board member, then 3 of the remaining 12 to golf with the second, and so on.

11

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

Solution

\(9!\) (there are 10 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).

12

Consider sets \(A\) and \(B\) with \(|A| = 10\) and \(|B| = 17\text{.}\)

How many functions \(f: A \to B\) are there?
How many functions \(f: A \to B\) are injective?

Solution

\(17^{10}\) functions. There are 17 choices for the image of each element in the domain.
\(P(17, 10)\) injective functions. There are 17 choices for image of the first element of the domain, then only 16 choices for the second, and so on.

13

Consider functions \(f: \{1,2,3,4\} \to \{1,2,3,4,5,6\}\text{.}\)

How many functions are there total?
How many functions are injective?
How many of the injective functions are increasing? To be increasing means that if \(a \lt b\) then \(f(a) \lt f(b)\text{,}\) or in other words, the outputs get larger as the inputs get larger.

14

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.

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{.}\)
Using the scenario of the 12 chips again, what does \(12!\) count? What does \(7!\) count? Explain.
Explain why it makes sense to divide \(12!\) by \(7!\) when computing \(P(12,5)\) (in terms of the chips).
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{.}\)