Combinatorics and Probability

How to Count

This might seem like a silly section title; counting, after all, is something that you learned how to do at a very young age! So let’s clarify what we mean by “counting.”

On one hand, it is easy to see that there are four elements in a set like

A = \{3,5,7, \textrm{Snape}\}.

We’re not going to practice counting things like this! Instead, consider the following four exercises:

Exercise 3.1. How many strings of five letters are palindromes (i.e. can be read the same way forwards and backwards?)

Exercise 3.2. A lattice path in the plane $\mathbb{R}^2$ is a path joining integer points via steps of length 1 either upward or rightward. How many lattice paths are there from $(0,0)$ to $(3,3)$ ?

Exercise 3.3. How many seven-digit phone numbers exist in which the digits are all nondecreasing?

Exercise 3.4. In how many ways can you roll a six-sided die three times and get different values each time?

All of these are “counting” problems, in that they’re asking you to figure out how many objects of a specific kind exist. However, because the sets in question are trickily defined, these problems are much harder than our “how many elements are in $\{3,5,7,$ Snape $\}$ question.

To approach them, we’ll need some new counting techniques! This is the goal of this chapter: we’re going to study combinatorics, the art of counting, and develop techniques for solving problems like the ones above.

Let’s start off with a simple task:

Problem 3.1. Suppose that we have $3$ different postcards and $2$ friends. In how many ways can we mail out all of our postcards to our friends while we’re on vacation?

Answer. Let’s give our cards names $A,B,C$ , and also give our friends names $X$ and $Y$ , for easy reference.

In the setup above, a valid “way” to mail postcards to friends is some way to assign each postcard to a friend (because we’re mailing out all three of our postcards.) To do this, think of going through each card $A,B,C$ one-by-one and choosing a friend $X,Y$ for each card.

By using brute-force, we can just enumerate all of the possibilities:

$X$ gets $A,B,C$ , $Y$ gets nothing.
$X$ gets $A,B$ , $Y$ gets $C$ .
$X$ gets $A,C$ , $Y$ gets $B$ .
$X$ gets $B,C$ , $Y$ gets $A$ .
$X$ gets $A$ , $Y$ gets $B,C$ .
$X$ gets $B$ , $Y$ gets $A,C$ .
$X$ gets $C$ , $Y$ gets $A,B$ .
$X$ gets nothing, $Y$ gets $A,B,C$ .

This works, and tells us that there are $\boxed{8}$ different ways to do this. However, if we had more cards this brute-force process seems like a bad idea:

Problem 3.2. Suppose that we have $10$ different postcards and $4$ friends. In how many ways can we mail out all of our postcards to our friends while we’re on vacation?

Answer. We could try a brute-force approach like before. It would work, if you had enough time! However, if you start doing this you’ll quickly find yourself bored out of your mind; there are tons of ways to do this, and just trying to list all of them is exhausting.

Instead, to do this, let’s think about a process to generate ways to send out cards. That is: think about going through each card one-by-one and choosing a friend for each card:

\underbrace{\fbox{4 \textrm{possible friends}}}_{\textrm{card }1} ~ \underbrace{\fbox{4 \textrm{possible friends}}}_{\textrm{card }2} ~\ldots~\underbrace{\fbox{4 \textrm{possible friends}}}_{\textrm{card }10}

When doing this process, we have 4 choices of friend for each card, and any combination of those choices will give us a valid way to send out cards. Therefore, we should have

\underbrace{4 \cdot 4 \cdot \ldots \cdot 4}_{10 ~4's} = \boxed{4^{10}}

total ways in which we can send out our cards.

This looks like an excellent answer to a counting problem, and also a much better method than our first approach!

Alongside our answer, we also came up with a fairly interesting method for counting at the same time. Specifically, we had a set $A$ of the following form:

Each element $f$ of $A$ could be constructed by making $k$ choices in a row.
There was a fixed number $n_i$ of possibilities for the $i$ -th choice made in constructing any such element of $A.$

By “fixed,” we mean the following: the number of such choices is not affected by our other choices. That is, we’ll always have $n_i$ options for our $i$ -th choice, no matter what our earlier choices actually were.

Therefore, we had $\underbrace{n_1 \cdot n_2 \cdot \ldots \cdot n_k}_{k ~n's}$ total elements in $A$ .

You’ll see this called the multiplication principle in other combinatorics resources online!

To get some practice with this principle, we study a number of examples of it in action:

Problem 3.3. How many binary strings of length 5 exist?

Answer. A binary string of length 5 has five characters in it, each of which is 0 or 1. Therefore, making such a string is the same thing as making five choices in a row, each of which has two options:

\underbrace{\fbox{0 \textrm{ or }1}}_{\textrm{entry }1} ~ \underbrace{\fbox{0 \textrm{ or }1}}_{\textrm{entry }2} ~\underbrace{\fbox{0 \textrm{ or }1}}_{\textrm{entry }3} ~\underbrace{\fbox{0 \textrm{ or }1}}_{\textrm{entry }4} ~\underbrace{\fbox{0 \textrm{ or }1}}_{\textrm{entry }5}

By the multiplication principle, this can be done in $\boxed{2^5}$ ways.

Problem 3.4. Take a six-sided die, and roll it twice in a row. In how many ways can you do this and not see the same value repeat?

Answer. We can again think of this process as making two choices in a row:

\underbrace{\boxed{1,2,3,4,5\textrm{ or }6}}_{\textrm{roll }1} ~ \underbrace{\boxed{1,2,3,4,5\textrm{ or }6, \neq\textrm{ roll 1}}}_{\textrm{roll }2}

There are 6 possibilities for the first roll. Once this is done, there are 5 possibilities for the second roll, as we can have any value show up other than the one that occurs in the first roll. Therefore, there are $6 \cdot 5 = \boxed{30}$ possibilities in total by the multiplication principle.

It is worth noting that the multiplication principle does not apply to all possible situations! Consider the following counting problem:

Problem 3.5. How many binary strings of length at most 3 exist?

Answer. Using the same logic as in Problem 3.3, we know that

There are $2^3 = 8$ binary strings of length exactly 3,
there are $2^2 = 4$ binary strings of length exactly 2, and
there are $2^1 = 2$ binary strings of length exactly 1.

Also, we know that there is one binary string of length 0, namely the empty string $\lambda$ .

Therefore, in total, there are $8+4+2+1 = \boxed{15}$ strings in total.

Notice how at the end of the process above, we didn’t multiply these numbers together! This is because the numbers $8,4,2,1$ aren’t all part of creating one giant mega-string. Instead, they each came from disjoint processes: that is, the strings of length 3 have no overlap with the strings of length 2, and so on/so forth. As such, we added them together!

You’ll sometimes see this “add disjoint things” process referred to as the addition principle.

To get some practice with spotting places where we use addition in counting, let’s look at another problem:

Problem 3.6. Suppose that you have four friends Aang, Korra, Zuko, and Toph. In how many ways can you arrange them in a row, if Aang and Zuko are currently fighting and can’t be placed next to each other?

Answer. If we just had the problem “In how many ways can we arrange Aang, Korra, Zuko, and Toph in a row,” our problem is pretty straightforward! By using our multiple-choice framework from before,

\underbrace{\fbox{A,K,Z,T}}_{\textrm{friend }1} ~ \underbrace{\fbox{A,K,Z,T}}_{\textrm{friend }2} ~ \underbrace{\fbox{A,K,Z,T}}_{\textrm{friend }3} ~ \underbrace{\fbox{A,K,Z,T}}_{\textrm{friend }4}

we can see that we have 4 choices for the first friend in our order, 3 for our second (as we can’t repeat a friend), 2 for our third (can’t choose any of the two previously-placed friends), and 1 for our last (everyone else is already in place!) So, in total, we have $4\cdot 3 \cdot 2 \cdot 1 = 24$ ways to do this.

However, in this process we’ve allowed all of the possible arrangements, including ones like “A,Z,T,K” where Aang and Zuko are together. How do we correct for this?

Well, let’s try to count all of the ways in which Aang and Zuko could be placed together! There are two ways in which this can happen:

Aang and Zuko are placed in the order “AZ.” To find all of the arrangements where this could happen, think of all of the ways to place three things $\fbox{T}$ , $\fbox{K}$ , $\fbox{AZ}$ in order! There are $3 \cdot 2 \cdot 1 = 6$ ways to do this, by the same reasoning as above.
Aang and Zuko are placed in the order “ZA.” To find all of the arrangements where this could happen, think of all of the ways to place three things $\fbox{T}$ , $\fbox{K}$ , $\fbox{ZA}$ in order! There are again $3 \cdot 2 \cdot 1 = 6$ ways to do this.

Because the “AZ” and “ZA” cases are completely distinct, we add them to get that there are $6+6 = 12$ ways for Aang and Zuko to be placed together in either order.

Finally, in any way of arranging our friends at all, we either have Aang and Zuko together or not. Therefore, we add these situations together, to get

\boxed{\textrm{all arrangements}~(24)}=\boxed{\textrm{arrangements with Aang and Zuko together}~(12)}+\boxed{\textrm{arrangements with Aang and Zuko separate}}

In other words, there are $24-12 = \boxed{12}$ arrangements where Aang and Zuko are separate!

One particularly useful thing we can do with counting arguments is measure probability. That is: suppose that we have an experiment in which all of the individual outcomes are

equally likely, and
mutually exclusive.

To give some examples of experiments like this:

Suppose that you were rolling a fair 6-sided die. In this case, there are 6 outcomes: the die could show a 1,2,3,4,5, or 6. These outcomes are all equally likely if our die is fair: they’re also all mutually exclusive, as a die can only show one number at a time.
Suppose that you flipped a fair coin. In this case, there are 2 outcomes: heads or tails. They’re equally likely if the coin is fair, and they’re both mutually exclusive, as a coin cannot simultaneously be both heads and tails.
Suppose that you have a standard 52-card deck, and reveal the top card. In this case, there are 52 possible outcomes, i.e. the 52 possible cards in the deck, and each of them are mutually exclusive (because you’re only revealing one card).
Suppose that you have a bag containing 12 cookies, and you take one cookie out. In this case, there are 12 events (the 12 possible cookies you could have picked) and they’re all mutually exclusive (because you are only taking one cookie).

In situations like this, we have the following very useful observation:

Observation 3.5. Take any experiment in which all of the individual outcomes are equally likely and mutually exclusive. Let $n$ be the number of all possible outcomes. Then, the probability that any individual outcome happens when you run that experiment is $\boxed{\frac{1}{n}}$ .
More generally, take any set $A$ of outcomes and let $a$ denote the number of elements in $A$ . Then the probability of running your experiment and having an outcome from $A$ happening is $\boxed{\frac{a}{n}}$ .

This is very useful! By using our newfound ability to count complicated objects, we can now determine the likelihood of various events happening.

This probably feels somewhat abstract, so let’s illustrate this with a few examples:

Problem 3.7. Take two fair 6-sided dice and roll them. What is the probability that the sum of these dice is 7?

Answer. On one hand, we know that there are six possible ways for our dice to sum to 7: the six pairs $(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)$ each correspond for a way for to roll two dice and get a 7. (Notice that we count $(1,6)$ and $(6,1)$ differently! This is because our two dice are different, and so rolling a 1 on the first die and a a 6 on the second is a different event than rolling a 6 followed by a 1.)

On the other hand, we know that there are $36$ possible outcomes for a given roll of our two dice; this is because there are 6 choices for what the first die can be, 6 for the second, and we multiply these together.

Thus, the odds that we roll two dice and they sum to 7 is $\frac{6}{36} = \frac{1}{6}$ .

Problem 3.8. You and three of your friends are graduating. At graduation, you each throw your hats in the air to celebrate! At the end, you each pick up a hat from the ground. What are the odds that each of you pick up your own hat? (Assume that you’re picking up hats at random, i.e. you’re as likely to pick up your own hat as anyone else’s hat: also assume that for some reason no-one else is graduating, and so there are only four possible hats to pick up.)

Answer. It takes a bit more thought to come up with the experiment structure here. To do so, let’s label you and your friends 1,2,3 and 4, and similarly label the hats 1,2,3 and 4. If we do so, then we can describe any way for you and your friends to pick up hats by just listing the numbers 1,2,3,4 in some order: that is, $(2,1,3,4)$ would describe the situation where 1 has 2’s hat, 2 has 1’s hat, and 3 and 4 have their own hats.

In this setting, there are as many ways to pick up hats as there are ways to write the numbers 1,2,3,4 in some order. We know from our work earlier that there are $24$ ways for this to happen in (it’s the same thing as ordering our four friends in Problem 3.6!)

There is also only one way for everyone to get their own hat: namely, the ordering (1,2,3,4). Therefore the probability that everyone picks up their own hat is $\frac{1}{24}$ .

Ordered Choice

A special case of the counting processes we studied earlier is the following:

Observation 3.6. (Ordered choice with repetition.) Suppose that you are choosing $k$ objects from a set of $n$ things, where you care about the order in which you choose your objects and can repeatedly pick the same thing if desired. There are $\boxed{n^k}$ many ways to make such a choice.

This principle is remarkably handy! We can use it to answer one of our problems from the start of this chapter:

Answer to Exercise 3.1. In this problem, we’re trying to count the number of five-letter strings that are palindromes (i.e. can be read the same way forwards and backwards).

To do this, start by noticing that any five-letter palindrome can be constructed by taking an arbitrary three-letter string and sticking its second and first characters at the end of the string: e.g. you can transform “rad” to “radar”, “ten” to “tenet” and “eev” to “eevee.” This process is clearly reversible: i.e. you can take any five-letter palindrome and cut off its last two letters to get a 3-letter string.

Any such three-letter string is formed by making three choices in a row, and we have 26 choices for each letter; this gives us $\boxed{26^3}$ many such strings, and thus $26^3$ many five-letter palindromes.

This can get a bit more complex, however. Let’s try changing our postcard problem a bit from before:

Problem 3.9. Suppose that we have $k$ different kinds of postcards, $n$ friends, and that we want to mail these postcards to our friends. Last time, however, it was possible that we just mailed all of our postcards to the same friend. That’s a bit silly, so let’s add in a new restriction: let’s never send any friend more than one postcard.

In how many ways can we mail out postcards now?

Answer.

We can still describe each way of sending postcards as a sequence of choices:

\underbrace{\fbox{? \textrm{choices}} \cdot \fbox{? \textrm{choices}} \cdot \ldots \cdot \fbox{? \textrm{choices}} }_{k \textrm{ total slots}}

As before, we still have $n$ possibilities for who we can send our first card to. However, the “ordered choice with repetition” principle doesn’t immediately apply here: because we don’t want to repeat any of our friends, we only have $n-1$ choices for our second slot, instead of $n$ as before! In general, we have the following sequence of choices:

\underbrace{\boxed{n~\textrm{choices}} \cdot \boxed{n-1~\textrm{choices}} \cdot \boxed{n-2~\textrm{choices}} \cdot \ldots \cdot \boxed{n-(k-1)~\textrm{choices}} }_{k \textrm{ total slots}},

which translates into

n \cdot (n-1) \cdot (n-2)\cdot \ldots \cdot (n - (k-1))

many choices in total.

A common question students ask about this calculation: why do we go to $n-1$ and not $n$ in the product above? Well: we have $k$ total slots. In the first slot, none of our choices were eliminated yet! In the second slot, however, we’ve eliminated one choice with our first slot. By the third slot we’ve eliminated two possibilities, by the fourth we’ve eliminated three possibilities, and in general in the $i$ -th slot we’ve eliminated $i-1$ possibilities. This leaves us with $k-1$ possibilities eliminated by the time we get to the $k$ -th slot!

We can simplify this expression considerably by introducing a useful function:

Definition 3.1. For any nonnegative integer $n$ , we define the factorial of $n$ , written $n!$ , as the following product:
$n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot n$

If $n=0$ , we think of this as the “empty product,” and say that $0! = 1$ .

With this notation in mind, we can simplify our answer to the postcard problem considerably: notice that

n \cdot (n-1) \cdot \ldots \cdot (n - (k-1)) = \frac{\Big(n \cdot (n-1) \cdot \ldots \cdot (n - (k-1)) \Big)\cdot \Big( (n-k) \cdot (n-(k+1)) \cdot \ldots \cdot 3 \cdot 2 \cdot 1 \Big)}{\Big( (n-k) \cdot (n-(k+1)) \cdot \ldots \cdot 3 \cdot 2 \cdot 1 \Big)} =\boxed{\frac{n!}{(n-k)!}}.

We can use this idea to describe another counting method:

Observation 3.7. (Ordered choice without repetition.) Suppose that you are choosing $k$ objects from a set of $n$ things, where you care about the order in which you choose your objects, but can only pick an object at most once. There are $\boxed{\dfrac{n!}{(n-k)!}}$ many ways to make such a choice if $k \leq n$ , and 0 ways otherwise (as we’ll run out of choices!)

To practice using this observation, let’s work a pair of problems:

Problem 3.10. If you take a six-sided die and roll it three times, what is the probability that you get different values each time?

Answer.

If we keep track of what our first/second/third roll of our die is, then there are $6^3$ many possible ways for us to roll a 6-sided die three times: we have 6 possible outcomes, we’re choosing one of those outcomes 3 times, and the order matters + repeats are allowed.

Conversely, if we want to know the number of ways to roll a 6-sided die and have no repeated values, this is $\dfrac{6!}{3!} = 6\cdot 5 \cdot 4$ , by our order matters + no repeats process described above. (Note that this answers Exercise 3.4!)

Therefore, in total, we have a $\frac{6\cdot5\cdot4}{6^3}\approx 0.56 = \boxed{56\%}$ chance of this happening.

Problem 3.11. Suppose that you have six lightbulbs: two identical red bulbs, and one green / one blue / one white / one pink.

In how many ways can you screw these bulbs into a string of six lightbulb sockets? (Assume that the order in which we string these bulbs matter: i.e. we consider ” $RRGBWP$ ” and ” $PWBGRR$ ” to be different.)

Answer.

First, we notice that if we could distinguish between our two red bulbs, this problem is a straightforward ordered choice without repetition problem: we would have 6 different bulbs, 6 sockets, and thus $6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 6!$ ways to do this.

However, these red bulbs are identical! This creates a bit of a problem: if we label our red bulbs $R_1, R_2$ , then the method above thinks that ” $R_1WGR_2BP$ ” and ” $R_2WGR_1BP$ ” are different strings, even though to us they are identical.

How can we correct for this? Well, just notice the following: given any string where our red bulbs are not labeled, there are exactly two ways to label them: either label the leftmost red bulb ” $R_1$ ” and the other ” $R_2$ ”, or vice-versa. In other words, there are twice as many strings where we have labelings as strings where we don’t!

Therefore, we can just divide our earlier answer by 2 to get $\boxed{\frac{6!}{2}}$ as our final answer.

Unordered Choice

In the section above, we discussed how to choose things in situations where we both could and could not “repeat” our choice. In both scenarios, however, the order in which we made these choices mattered!

This does not always happen in real life. Consider the following example:

Problem 3.12. Suppose that we have just one friend that we want to send postcards to. We still have $n$ different kinds of postcards, but now want to send that one friend $k$ different postcards in a bundle (say as a gift!) In how many ways can we pick out a set of $k$ cards to send our friend?

In this problem, we have $n$ different kinds of postcards, and we want to find out how many ways to send $k$ different cards to a given friend. At first glance, you might think that this is the same as the answer to our second puzzle: i.e.\ we have $k$ slots, and we clearly have $n$ choices for the first slot, $n-1$ choices for the second slot, and so on/so forth until we have $n-(k-1)$ choices for our last slot.

In mathematics: whenever you have a problem at hand, constantly look for modifications like these to make to the problem! If you’re stuck, it can give you different avenues to approach or think about the problem; conversely, if you think you understand the problem, this can be a way to test and deepen that understanding.

This would certainly seem to indicate that there are $\dfrac{n!}{(n-k)!}$ many ways to assign cards. However, our situation from before is not quite the same as the one we have now! In particular: notice that the order in which we pick our postcards to send to this one friend does not matter to our friend, as they will receive them all at once anyways! Therefore, our process above is over-counting the total number of ways to send out postcards: it would think that sending card $X$ and $Y$ is a different action to sending card $Y$ and card $X$ !

To fix this, we need to correct for our over-counting errors above. Notice that for any given set of $k$ distinct cards, there are $k!$ different ways to order that set: this is because in ordering a set of $k$ things, you make $k$ choices for where to place the first element, $k-1$ choices for where to place the 2nd element, and so on / so forth until you have just 1 choice for the $k$ -th element.

Therefore, if we are looking at the collection of ordered length- $k$ sequences of cards, each unordered sequence of $k$ cards corresponds to $k!$ elements in this ordered sequence! That is, we have the following equality:

\boxed{\begin{array}{c} \textrm{Unordered ways to} \\ \textrm{pick } k \textrm{ cards} \\ \textrm{from } n \textrm{ choices} \end{array}}

\cdot k! =

\boxed{\begin{array}{c} \textrm{Ordered ways to} \\ \textrm{pick } k \textrm{ cards} \\ \textrm{from } n \textrm{ choices} \end{array}}

= \dfrac{n!}{(n-k)!}

Therefore, if we want to only count the number of unordered ways to pick $k$ cards from $n$ choices, we can simply divide both sides of the above equation by $k!$ , to get

\boxed{\begin{array}{c} \textrm{Unordered ways to} \\ \textrm{pick } k \textrm{ cards} \\ \textrm{from } n \textrm{ choices} \end{array}}

= \dfrac{n!}{(n-k)!}

This concept --- given a set of $n$ things, in how many ways can we pick $k$ of them, if we don’t care about the order in which we pick those elements --- is an incredibly useful one, and as such leads itself to the following definition:

Definition 3.2. (Unordered choice without repetition.) The binomial coefficient $\binom{n}{k}$ is the number of ways to choose $k$ things from $n$ choices, if repeated choices are not allowed and the order of those choices does not matter.

Observation 3.8. By the working above, we can see that $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$ for any natural numbers $k, n$ with $k \leq n$ . For $k > n$ , we have $\binom{n}{k} = 0$ by the same reasoning as before: we cannot choose more than $n$ distinct things from a set of $n$ possibilities!

This observation lets us solve a few more problems:

Answer to Exercise 3.2. In this problem, we’re trying to count the number of lattice paths from $(0,0)$ to $(3,3)$ . How can we do this?

Well: notice that any path from $(0,0)$ to $(3,3)$ will need to take $6$ steps; of those $6$ steps, precisely $3$ must be to the right and the remaining 3 must be upward. Therefore, we can create any such path by just “choosing” $3$ out of our $6$ steps to be the rightward steps!

There are $\binom{6}{3}$ many ways to choose such a set of rightward steps; this is because we don’t repeat any of these choices (i.e. we have to pick three different places to go right), and because the order in which we decide which steps are rightward steps doesn’t matter (i.e. picking steps 2, 3 and 5 to be rightward steps is the same as picking steps 5, 2 and 3 to be rightward steps.) Therefore, we have our answer: it’s $\binom{6}{3} = \frac{6!}{3!3!} = \frac{6\cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = \boxed{20}$ .

Problem 3.13. Let’s return to Problem 3.8, and tweak its setup a bit: what’s the probability that no-one picks up their own hat?

Answer. Like in Problem 3.8, we still have the same universe of 24 possible ways for hats to be distributed. However, the set of situations in which no-one picks up their own hat is harder to measure!

One solution here could be to just list out via brute-force all of the possible ways to shuffle hats around without repeats. This could work; try it, if you want!

A second, clever trick (that would let us solve this problem for any number of friends) is the following:

\boxed{\begin{array}{c} \textrm{Ways in which for} \\ \textrm{no-one gets} \\ \textrm{their own hat} \end{array}}

=

\boxed{\begin{array}{c} \textrm{All ways} \\ \textrm{to return hats} \end{array}}

-

\boxed{\begin{array}{c} \textrm{All ways to} \\ \textrm{return hats where} \\ \textrm{someone gets their own hat} \end{array}}

On one hand, this is kind of a dumb observation: we’re just saying that the set of situations where our experiment succeeds is all of the possibilities where our experiment does not fail. On the other hand, though, this idea of “think about what happens where we do not succeed” has already been proven to be quite useful: both in Problem 3.6, and more generally when we’ve used the “suppose we’re wrong” argument method in our first chapter! It’s a good trick, and it will serve us well here.

In particular, suppose that we group our situations by cases, related to the number of people who get their own hats back:

4 hats back to original owners: There’s just \fbox1 way to do this, as noted in our previous problem.
3 hats back to original owners: This is impossible! If three people get their own hat back, then there’s only one hat left for the fourth person, i.e. their own hat. So there are \fbox0 ways for this to happen.
2 hats back to original owners: To count this, first count the number of ways to pick the lucky two people who get their own hat back. This is $\binom{4}{2} = \frac{4!}{2!2!} = 6$ , because we’re picking 2 people to get their hats back from a set of 4, and order doesn’t matter / we don’t repeat people.

With this done, there’s exactly one way for these hats to go back to their owners in the desired fashion for each such pair: the two chosen people get their own hat, and the other two swap hats. Therefore, there are \fbox6 ways for this to happen in total.
1 hat back to its original owner: We count this in the same way! There are 4 ways to pick a person to get their own hat back: just pick one of the four people.

With this done, in how many ways can our remaining people shuffle hats? Well: of the three remaining people, the first can choose either of the other two people’s hats. The person whose hat was not chosen then has no choice: to avoid taking their own hat, they must take the first person’s hat. This leaves the third person with no choice as well. Therefore, there are $2 \cdot 1 \cdot 1$ ways for this to happen for a given chosen person.

Across our four possible ways to choose people, then, there are \fbox $2 \cdot 4 = 8$ many ways for this to happen.

Therefore, the number of ways in which people get their own hats is $1+6+8 = 15$ , and so the number of ways in which this does not happen is $24-15 = 9$ . Thus, our probability is $\frac{9}{24} = \frac{3}{8}$ .

To illustrate one last counting process, we return to our postcard problem:

Problem 3.14. Suppose that we are at the shops and want to buy a bunch of postcards to send out to our friends. The shop sells $n$ different kinds of postcards, and has tons of each kind. We want to buy $k$ cards (possibly with repetitions, if there’s a specific card design we like and want to send to many people.) In how many ways can we pick out a set of $k$ cards to buy?

It first bears noting that this problem does not fall under the situations of our earlier problems. In this problem, our choices are unordered: i.e. we’re just picking out a bundle of cards to buy, and the order in which they’re bought is irrelevant. Therefore, we cannot use the “ordered choice with repetitions” observation we made earlier, as this would massively overcount things (i.e. we’d count orders of the same cards as different if the cashier rang things up in a different order, which is silly.)

However, unlike our two “ordered/unordered choice without repeats” situations, we can repeat choices! This means that this is not at all like those situations: in particular, $k$ can be larger than $n$ and we will still have lots of possibilities here, whereas in in the “without repeats” situations this was always impossible. So we need a new method!

To develop this method, think of the $n$ different kinds of postcards as $n$ “bins.” Here’s a visualization for when $n=5$ :

Picking out $k$ cards to buy, then, can be thought of as pulling a few cards from the first bin, a few from the second, and so on/so forth until we’ve pulled out k cards in total. In other words, this is the same problem as distributing $k$ balls amongst $n$ bins:

To do \textit task, replace the $n$ bins with $n-1$ “dividers” between our choices. This separates our choices just as well as the bins did, so this is still the same problem.

Now, forget the difference between objects and dividers! That is, take the diagram above and suppose that you cannot tell the difference between an object and a divider between our choices.

How can we return this back to a way to choose $k$ things from $n$ choices? Well: take the set of $k+(n-1)$ objects, of which $k$ used to be things and $n-1$ were dividers. Now choose $n-1$ of them to be dividers! This returns us back to a way to pick out $k$ things from $n$ choices.

In particular, note that given any set of $k+(n-1)$ placeholders, we can turn it into a way to choose $k$ things from $n$ choices with repetition by performing such a choice! Therefore, there are as many ways to make such choices as there are ways to choose $n-1$ things from a set of $k+(n-1)$ options to be placeholders. This second choice is unordered and without repetition (we want all of the placeholders to be different, and don’t care about the order in which we pick the placeholders: just the elements that are chosen!) Therefore, we can use our “unordered choice without repetition” principle to see that there are $\binom{k+n-1}{n-1}$ many ways to do this!

In other words, we have the following observation:

Observation 3.9. (Unordered choice with repetition.) The number of ways to choose $k$ things from $n$ choices, where we do not care about the order in which we make our choices but allow choices to be repeated, is $\binom{k+n-1}{n-1}$ .

To practice this, let’s answer our last two problems of this chapter:

Problem 3.15. Suppose that you have ten identical cookies, and want to distribute them to four of our friends, so that each friend gets at least one cookie. In how many ways can we do this?

Answer. First, if every friend gets at least one cookie, we can start by just distributing one cookie to each friend! This leaves us with 6 cookies left over to distribute further to our friends.

If we think of taking each cookie and “choosing” a friend to give it to, this is unordered choice with repetition: the order doesn’t matter because the cookies are identical, and repeats are allowed because we can give one friend multiple cookies.

By our formula above, then, there are $\binom{6+4-1}{4-1} = \binom{9}{3} = \frac{9\cdot 8 \cdot 7}{3\cdot 2} = \boxed{84}$ ways for this to happen.

Answer to Exercise 3.3. In this problem, we’re trying to determine how many seven-digit phone numbers exist, in which the digits are nondecreasing? (By “nondecreasing” here, we just mean that each digit is at least as big to the digit to its left; i.e. 122-2559 is a valid phone number, but 321-1234 would not be.)

With this understood, we claim that our problem can be reduced to an “unordered choice with repetition” task as follows: consider any way to choose seven numbers from the set of digits $\{0,1,\ldots 9\}$ , without caring about the order and with repetition allowed.

On one hand, we claim that any such choice can be turned into a nondecreasing phone number! Just list the digits here in order of their size; i.e. if you picked three 1’s, a 2, a 3, and two 5’s, write down 111-2355. This process also clearly generates any such phone number (just pick its digits!), and so the number of seven-digit nondecreasing phone numbers is just the number of unordered ways to choose seven things from the set of digits $\{0,1,\ldots 9\}$ with repetition.

By our above formula, there are $\binom{7 + 10-1}{10-1} = \binom{16}{9} = 11440$ many such numbers. Success!

Practice Problems

(-) How many binary strings of length 10 exist?
How many three-digit numbers exist where all of the digits are different? (Hint: the answer is not $10 \cdot 9 \cdot 8 \ldots$ )
You have ten indistinguishable cookies that you’ve baked for four of your friends Jianbei, Sione, Sina and Julia. You want to give away all ten of your cookies to your friends, and for each friend to get at least one cookie. You also know that Sione wants an even number of cookies, so he can share them with a friend. In how many ways can you give away your cookies?
You’re a Pokémon master! You have collected exactly one of all 151 Pokémon in the base game. You want to assemble a team to take on the Elite Four: doing this involves choosing a team of 6 Pokémon (in which the order does not matter) and then designating one of those six to be the “lead” on your team (i.e. the first one to go out.) In how many ways can you do this?
For any two natural numbers $n, k \in \mathbb{N}$ , let $C(n,k)$ denote the number of ways to choose $k$ unordered objects from a set of $n$ distinct objects without repeats, and let $P(n,k)$ denote the number of ways to choose $k$ ordered objects from a set of $n$ distinct objects without repeats. For what values of $n,k$ is $C(n,k) = P(n,k)$ ?
(-) Take the collection of all length-10 binary strings and pick one at random. What are the odds that the sum of all digits in your string is even? Does this change if you were looking at length-11 binary strings?
Take a standard 52-card deck of playing cards, shuffle it, and draw a hand of five cards. What is the probability that your hand has a three-of-a-kind?
Can you find three events $A,B,C$ such that

the probability of $A$ and $B$ happening at the same time is $\frac12$ ,
the probability of $A$ and $C$ happening at the same time is $\frac12$ ,
the probability of $B$ and $C$ happening at the same time is $\frac12$ , and yet somehow
the probability that all three of $A,B,C$ happening at the same time is 0?

(+) Suppose that there’s an election! Two candidates, Sherlock and Moriarty, are running for office. Suppose that Sherlock receives 8 votes and Moriarty receives 7 votes, and that these votes are being counted up one-by-one to create a running total. What is the probability that Sherlock is never behind in this running total? In general, if Sherlock got $s$ votes and Moriarty got $m$ votes, what is this probability?
(+) Auckland has about 1 million residents. Suppose each resident has a jar with 100 coins in it. Two jars are considered to be “equivalent” if they have the same number of 10c, 20c, 50c, $1 $2 coins in them. How many different (i.e. nonequivalent) jars of coins exist? Is it theoretically possible that every person in Auckland has a different jar of coins?