Interview Cake
Permutations—Order Matters
A permutation is a way of ordering items.
Say you were running a bakery that sold five different cakes and you were working on a big menu to put over the register. You're having trouble deciding which should come first, second, and so on. How many different ways could you arrange the cakes on the menu?
Well, there are five options for the cake that appears at the top of the menu.
For each possible choice for the first cake, you have four options for the second cake (because you already used one cake for the first slot).
For each pair of choices for the first and second cakes, you have three cake options left for the third slot on the menu.
And so on, until we only have one option for the last cake on the menu.
To get the total number of possible orderings, we multiply the number of choices for each slot together:
We can also write this as:
That "!" means "factorial. n! is the product of all the numbers from 1 to n.
In general, the number of ways to order n items is:
In other words, a set of n items has n! different permutations.
Permutations where you don't use every item
What if the bakery had made 25 cakes and featured 5 of them on a flyer. How many orderings of 5 cakes could we have on the flyer?
We'll use a similar approach to the menu problem above: take the number of options for each slot and multiply them together.
We have 25 options for the first cake, 24 for the second, 23 for the third, 22 for the fourth, and 21 for the fifth. Multiplying those together, we've got:
Sometimes, you'll see this written as a fraction of two factorials:
If you write it out, you can see how most of the factors cancel out to give us our original product:
In general, the number of possible permutations of k items from a larger set of n items is:
We can apply this formula to the menu problem above.
In that case, k=n, so our denominator becomes:
Why is 0!=1? That's just how it's defined—it's kind of like how x^0=1.
Permutations are sometimes written as:
Combinations—Order Doesn't Matter
A combination is a way of grouping items where order doesn't matter.
Going back to our bakery, say that the head baker chooses 15 cakes from our set of 25 to bake each day. How many different combinations of cakes are there?
Initially, the head chef has 25 cakes to choose from. After he picks one, he's got 24. Then 23. And so on, until he picks his 15th cake to bake and has 10 left over.
Mathematically, we've got something like this:
We also could've gotten this by using our permutations formula:
One issue: that formula assumes we care about the ordering. In this case, we don't.
We've over-counted. We're treating [A,B,C] and [C,B,A] as separate combinations, but they're not. They're separate permutations, but they're the same combination.
To account for this, we'll divide by the number of times we've over-counted each combination.
How many times is that? Well, each possible combination of 15 cakes has 15! permutations, and we've included all of them in our count so far.
So we'll divide by 15!:
If you're unconvinced, try writing it out with a smaller number of cakes. Say we had four cakes—A, B, C, D—and we were choosing three of them.
There are 4 * 3 * 2 = 24 different permutations:
- ABC, ABD, ACB, ACB, ADB, ADC
- BAC, BAD, BCA, BCD, BDA, BDC
- CAB, CAD, CBA, CBD, CDA, CDB
- DAB, DAC, DBA, DBC, DCA, DCB
But in those 24 permutations, the combination ABC appears six times, since there are 3 * 2 * 1 = 6 ways to order the three cakes:
- ABC, ABD, ACB, ACD, ADB, ADC
- BAC, BAD, BCA, BCD, BDA, BDC
- CAB, CAD, CBA, CBD, CDA, CDB
- DAB, DAC, DBA, DBC, DCA, DCB
Same thing for all the other sets. In total, we're overcounting by a factor of six, and we need to divide to eliminate those repetitions.
Once that's done, we're left with four possible combinations: ABC, ABD, ACD, BCD.
Whenever we divide a fraction by another fraction, we can rewrite it as as a product like this:
Generalizing this approach, if we are choosing a combination of k items from n items, the number of possible combinations is:
Combinations are sometimes written as:
or
This is read, "n choose k."
One thing to notice is that \binom{n}{k} is the same as \binom{n}{n - k}:
This makes sense intuitively: if we're choosing k items from a group of n to include, we can just as easily choose n - k items to exclude to get the same result.
With our example above of choosing 3 cakes out of a set of 4 (A, B, C, D), each choice of 3 is simply a choice of which one to exclude. So it makes sense that our final number of combinations was 4--one for each possible choice for which cake to leave out.
We can also show this with math:
Permutations with Unlimited Repetitions
You get to the bakery early one morning, before your boss arrives, and the door is locked. Eager to get a jump on baking prep, you start fiddling with the pinpad on the door lock. The code is 4 numbers between 1 and 9.
How many different 4-digit codes are possible?
Confusingly, in English we often use the word "combination" to describe the code you enter on a lock . . . but in the combinatorics sense it's actually a permutation, not a combination, because the order matters.
There are 9 possibilities for the first number, 9 possibilities for the second, 9 possibilities for the third, and 9 possibilities for the fourth. Multiplying these together, we've got:
Why not 9 * 8 * 7 * 6, like in the menu problem? In the menu problem we had one fewer possibility for each slot, since we'd already used one of our options. But in this case, using a 5 for our first digit in the code doesn't mean we can't use a 5 for the next digit. So each slot in our code has the full 9 possibilities.
In general, the number of ways to order k items from a set of n items, if each item can repeat any number of times, is:
Permutations with Specific Repetitions
While your boss is putting up the menu, they have to run to the back to take an important phone call. So you decide to try to finish the job for them.
The menu is spelled out with magnetic letters, and it's almost done. There's just one last row with the word "RED" and 6 letters on the counter ready to be put up: "EEVVTL"
You're pretty sure these letters are supposed to spell out one word, but you're not sure what it is. How many different permutations can you make with these 6 letters?
This scenario is like a hybrid of combinations and permutations, since order sometimes matters. "VEVTEL" is a different permutation than "LEVTEV." But what if we took "LEVTEV" and swapped the first E and ... the second E? We'd still have the same ordering: "LEVTEV."
We'll do something like what we did for combinations—we'll start by calculating the number of possible permutations, and then we'll divide to eliminate identical permutations from our count.
How many permutations of the 6 letters are there? Easy—6!.
Now to remove duplicates. We have two V's and two E's. First, let's look at our two V's—call them V1 and V2. In our set of 6! permutations, we'll have both LEV1TEV2 and LEV2TEV1. That means that the two V's cause the LEVTEV permutation to get counted twice. In fact, every anagram will get counted twice—once with V1 as the first V and once with V2 as the first V.
To account for this, we need to divide the number of permutations in half.
By similar logic, we'll need to divide in half again for the duplicate E's, since we'll count LE1VTE2V and LE2VTE1V as separate permutations even though they're the same anagram.
Putting things together, the number of anagrams of "EEVVTL" is:
You might think that the formula is to just divide by two for each item that can repeat. But it's a bit more complicated.
What if we had three E's in our word instead of two? Then, we'd be counting each anagram six times, since the E's could be ordered 123, 132, 213, 231, 312, or 321. That makes sense—3! possible orderings of 3 items.
In general, if we have x repeats of something, we'll have to divide the number of permutations by x! to account for that.
So, if we have k groups of identical items (E's, V's, etc.), and we want to take n total items, and x_i items come from the ith group, then the number of ways to order all the items is:
If you didn't figure it out: the word was "VELVET," as in "RED VELVET."
Dividing Identical Items
Your boss wants you to experiment with putting different numbers of raspberries on cakes to see what looks best.
Say we've got 12 raspberries that we'd like to use to decorate 5 different cakes. How many different ways can we split up the raspberries between the cakes?
Unlike before, where we had lots of different types of items, now we only have one type (all the raspberries are the same).
To solve this one, we'll use a trick called balls and walls.
First, imagine we've got 12 balls (or raspberries):
To break our balls into five groups, we can think of adding in four walls to separate them:
Here's the trick: we can think of this as ordering 16 total items—12 balls and 4 walls. Ordering matters, but all the balls are the same and all the walls are the same, so we can use the "permutations with specific repetitions" formula from the last problem:
In this case, we have 16 total items (n = 16) coming from two groups: balls and walls. We'll take 12 balls (x_1 = 12) and 4 walls (x_2 = 4). Plugging in, we have:
Generalizing this approach, the number of ways to divide n identical items between k groups is:
Heads up! This approach only works if we're not dividing between identical groups.
In our raspberries example, this means that putting all the raspberries on the chocolate cake is different than putting them all on the pound cake. But what if we just had 5 chocolate cakes that we treat as identical? In this case, putting all 12 raspberries on the first cake (12, 0, 0, 0, 0) is the same as putting them all on the last cake (0, 0, 0, 0, 12).
Can you figure out how many ways there are to divide the 12 raspberries into five cakes if we don't differentiate one cake from another?
It's tricky! And, it turns out that there isn't a known formula for the general case of n items and k groups.
