4.2: Permutations and Combinations – Counting

4.2: Permutations and Combinations


Counting? It’s going to be okay. And maybe fun.

The Basics

This section will be a bunch of examples just to dust off the cobwebs from whatever high school background you have. If you don’t have that background, that’s okay, the examples are designed to give you some of that intuition. If you do, feel free to skim.

\refstepcounter{examplectr} Example [[counting_outfit_example]]{#counting_outfit_example label=“counting_outfit_example”} Every day, Bob wears a jacket, a shirt, and a pair of jeans. He has 3 different jackets, 4 different shirts, and 5 pairs of jeans, all of different washes (he’s really into jeans). (He also wears shoes but he only owns one pair). How many different outfit combinations are possible?

One way to think about this is say we know Bob is choosing one of three jackets—say he chooses the bomber jacket. Then he has four choices for shirts—say he chooses the white one. Then he has 5 choices for a pair of jeans. Since for every shirt there are 5 jean choices there are $4 \times 5 = 20$ choices of shirts and jeans. Since for every jacket there are 20 choices of shirts and jeans, then there are $3 \times 20 = 60$ choices for jackets, shirts, and jeans. And so Bob has $60$ options. $\square$

\refstepcounter{examplectr} Example Bob moves to Seattle and realizes that he has a different routine when choosing clothes for rainy days: he wears a raincoat, a jacket, a shirt, a pair of jeans, and rain boots. He has become a rain fashion connoisseur and owns 6 raincoats and 7 pairs of rain boots. Including his non-rainy day options, how many outfits does he own now? (He still has one pair of sneakers, 3 jackets, 4 shirts, and 5 pairs of jeans as in the previous example).

Here, we see that our scenario is split into two disjoint cases: when it’s rainy and when it’s not. What do we mean by disjoint? It means a day can’t be both rainy and not rainy, so we add the number of outfits in the two cases together.

Case 1 (Not Rainy): In this case, we simply take what we got from Example [counting_outfit_example]{reference-type=“ref” reference=“counting_outfit_example”}, since on fair days, Bob does not wear a raincoat or rain boots. Therefore there are $60$ options in this case.

Case 2 (Rainy): This is the same drill as example [counting_outfit_example]{reference-type=“ref” reference=“counting_outfit_example”}. 6 raincoats, 7 pairs of rain boots, 5 pairs of jeans, 4 shirts, and 3 jackets makes a total of $\begin{aligned} 6 \cdot 7 \cdot 5 \cdot 4 \cdot 3 = 2520 \text{ outfits} \end{aligned}$ We’re almost done! We just need to add everything together to get $60 + 2520 = \boxed{2480 \text{ outfits}}$ $\square$

Permutations and Combinations

Fancy word alert! (Sounds scarier than it is, I promise!)

\refstepcounter{examplectr} Example [[counting_five_letter_example]]{#counting_five_letter_example label=“counting_five_letter_example”} How many ways are there to rearrange the string $ABCDE$?

Let’s tackle the 5 letter one first. We can think of this this way (many problems in counting are easier if you can reframe them a certain way)—there are 5 spaces we would like to fill in:

\textunderscore
\textunderscore \textunderscore \textunderscore \textunderscore How many choices of letters do we have for the first blank? 5. How about the second? 4, after we filled something in the first blank. Third? 3. Fourth? 2. And the last one? 1. So our answer is $\label{five_factorial} 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

$\square$

The value expressed in equation [five_factorial]{reference-type=“ref” reference=“five_factorial”} is denoted $5!$ (read “five factorial”). In general $n! = \prod_{i=1}^{n} i = n (n-1) (n-2)\cdots (2)(1)$ and we define $0!$ as $1$. (A perhaps unsatisfactory “explanation” to why is that there is one way to rearrange $0$ letters in a $0$-length string—do nothing.)

\refstepcounter{examplectr} Example [[counting_five_friends_line]]{#counting_five_friends_line label=“counting_five_friends_line”} How many ways can five friends sit at a bar (i.e. in a line)?

We can represent this scenario like in example [counting_five_letter_example]{reference-type=“ref” reference=“counting_five_letter_example”}, with each friend being represented as a different letter in the string $ABCDE$. So the answer is the same, $5!$. $\square$

\refstepcounter{examplectr} Example How many ways can the the string of all 26 English letters (ABCDEFGHIJKLMNOPQRSTUVWXYZ) be rearranged?

We can naturally see that this is simply an extension of example [counting_five_letter_example]{reference-type=“ref” reference=“counting_five_letter_example”}. We now have a nice clean way to represent the solution—it is $\boxed{26!}$. $\square$

We can use this (not really that new) way of thinking to do something kind of different:

\refstepcounter{examplectr} Example [[electing_officers_numbers]]{#electing_officers_numbers label=“electing_officers_numbers”} Math Club has 20 members. There are three officers: President, Vice President, and Secretary. Every member may only hold at most one position. How many ways can we choose officers?

We can do the same visualization as in example [counting_five_letter_example]{reference-type=“ref” reference=“counting_five_letter_example”}: there are three spots for officers, with the first, second, and third spots representing President, Vice President, and Secretary respectively. How many for the first spot (president)? 20. For the second spot (vice president)? 19, since members cannot hold two positions. And the third? 18.

So there are $20 \cdot 19 \cdot 18$ ways of choosing officers. If we wanted to use the factorial notation we introduced earlier, we can express this as $\frac{20!}{17!}$. $\square$

\refstepcounter{examplectr} Example [[electing_officers_general]]{#electing_officers_general label=“electing_officers_general”} The same problem as above, but with $n$ members and $k$ officer positions, where $n \leq k$.

With the same logic as above, this comes to be $\frac{n!}{(n-k)!}$. Work this out if you don’t understand. $\square$

\refstepcounter{examplectr} Example How many ways can five friends sit at a round table? (Careful, rotations as in Figure [counting_rotations_figure]{reference-type=“ref” reference=“counting_rotations_figure”} are considered to be the same seating arrangement.)

[[counting_rotations_figure]]{#counting_rotations_figure label=“counting_rotations_figure”}

We may be tempted to draw parallels between the 5 people sitting in a line problem and the 5 people sitting in a circle problem. Let’s say we number each of the people sitting in a row 1 to 5 from left to right and map this to the same people sitting around a circle like so:

But because of the rotations, we can see for the arrangement in figure [counting_rotations_figure]{reference-type=“ref” reference=“counting_rotations_figure”}, there are 5 arrangements of those friends sitting in a line that correspond to the same arrangement: $ABCDE, BCDEA, CDEAB, DEABC, EABCD$. So out of the total $\square$

\refstepcounter{examplectr} Example Alice, Bob, Carol, Donald, and Emma are playing musical chairs. There are 3 chairs, arranged in a circle, and again, we treat rotations as the same arrangement. How many arrangements are there after the music stops?

We can try to draw parallels with the sitting in a row scenario again. When there are 5 people and 3 chairs this is like the electing officers problem with 5 club members and 3 positions. There are 5 choices for the leftmost seat, 4 for the middle seat, and 3 for the rightmost seat.

However, once again, we’ve overcounted. How big is every group of sequence of letters that correspond to the same arrangement? 3. So our final answer is $\frac{5\cdot 4 \cdot 3}{3} = 20$. $\square$

It may be helpful at this point to introduce the idea of an equivalence class. You might say that the following things are equivalent: the strings $ABC, ABC$; the numbers $2$ and $2$. Sometimes we want to expand our idea of what it means for two things to be the same.

It’s an abstraction that’s so convenient you do it all the time. Time itself is a good example; even though technically it’s two different times, in certain circumstances we overlook this technicality when talking about twelve o’clock in the afternoon today and twelve o’clock in the afternoon a week from today. Why? We may have a somewhat of a routine schedule; we can guess how light it is outside.

When reading, you see the following as the same letters: a, a, though they are of different fonts. Handwriting is an extension of this.

In both of the above examples, two slightly different things were seen as “equivalent”; we can say that they belong to the same equivalence class.

Getting back to counting, when we say we “overcounted” what we’re really saying is we’ve counted how many of some way of representing the things we’re counting but we consider some of those to be the same. When we count the number of ways $n$ people can sit on a round table, we instead count the number of ways those people can sit in a row. Then we note that every equivalence class of unique ways to seat those people on a round has a size of $n$. What we really want to is the number of equivalence classes, so we divide $n!$ by $n$ to get our desired answer.

\refstepcounter{examplectr} Example How many ways are there to pick out a committee of 3 people out of a 20-person club?

How is this different from Exercise [electing_officers_numbers]{reference-type=“ref” reference=“electing_officers_numbers”}? We don’t have the idea of positions—if we choose Alice, Bob, and Carol, in Exercise [electing_officers_numbers]{reference-type=“ref” reference=“electing_officers_numbers”}, we would still need to assign who is president, vice president, treasurer. So for every committee of 3 people there are $3! =6$ ways to convert them into officers.

Now we can use our answer from Exercise [electing_officers_numbers]{reference-type=“ref” reference=“electing_officers_numbers”}. We want our equivalence classes to represent unique committees and there are $3!$ officer assignments for every committee. So we take our answer and divide it by $3!$, giving us $\frac{20!}{3!17!}$. $\square$

\refstepcounter{examplectr} Example [[picking_committee_general]]{#picking_committee_general label=“picking_committee_general”} How many ways are there to pick a committee of $k$ people in an $n$-person club?

In the same way as the previous part, we take our answer from exercise [electing_officers_general]{reference-type=“ref” reference=“electing_officers_general”} and divide by $k!$, giving us $\frac{n}{(n-k)!k!}$. $\square$

\refstepcounter{definitionctr} Definition

The answer to the previous question is so commonly used we have notation for it. We define $\binom{n}{k} = \frac{n}{(n-k)!k!}.$ This is read “$n$ choose $k$”, because it represents the number of ways to choose a set of $k$ items from a set of $n$.

\refstepcounter{examplectr} Example There are 50 contestants on the blind auditions of the Voice. There are 4 coaches that want to form teams of 10. How many ways are there to form teams?

Coach 1 has to pick a set of 10 people. How many ways are there for coach 1 to do this? $\binom{50}{10}$. Coach 2 needs to do the same thing, but they can’t pick any of the people that Coach 1 chose. So there are $\binom{40}{10}$ ways for Coach 2 do pick their team. And so on, so the number of ways to form teams is $\binom{50}{10}\binom{40}{10}\binom{30}{10}\binom{20}{10}.$ $\square$

When learning counting for the first time, it may be tempting to try to put a method or a box around everything. When you’re first starting out, I encourage you to try not thinking about the “rules” too hard; with practice they will be natural and you’ll understand them deeply.

However, I do want to address the idea of “ordered” and “unordered,” because those terms are often thrown around. The difference between the two is the difference between Exercise [electing_officers_general]{reference-type=“ref” reference=“electing_officers_general”} and Exercise [picking_committee_general]{reference-type=“ref” reference=“picking_committee_general”}. In one we are counting the number of $k$-length strings over an $n$-length alphabet where no letter can be repeated; in the second we are counting the number of $k$-size subsets of a $n$-size set we can make. In other words, in the first, we count every “ordering” or “permutation” of the $k$-size subsets to be distinct.