Explained: Permutations vs. Combinations

Benchmarked Path
Sep 10 · 7 min read

Yeah, I’m talking about those mystical buttons on your calculator (nCr and nPr) that you graciously hit and out spews the correct answer. Magic.

The two concepts are pretty straightforward so it shouldn’t take too long to explain. I am going to explain the differences; when to use them; and what exactly your calculator is computing when you enter them (the equation).

So the best way to illustrate their use case is through two examples:

Example 1: There are 10 athletes competing in a race where the first-place winner will receive a gold medal, the second-place winner will receive a silver medal, and the third-place winner will receive a bronze medal. If they win a medal they get to be on the tiered podium. The rest receive nothing.. not even a participation trophy…cause this is America..and if you ain’t first you’re last.

Question 1: how many possibilities are there for the podium?

Question 2: how many possibilities are there for who wins a medal?

When do you use nPr and when do you use nCr?

The Answer:

When to use them:

the two questions may appear similar, but there is a fundamental difference which will dictate which equation to use.

Question 1 (podium) factors in the relevancy of order:

If Bob, Lacy, and Sarah are on the podium, Bob coming in first is not the same as Bob coming in second. This is a different outcome. Order is relevant, so you will use nPr.

nPr (permutations) is used when order matters.

Question 2 does not factor in the order of the podium, it is simply asking who wins a medal. The question is not delineating between gold, silver, or bronze, they are all medals and that is all that matters. When the order does not matter, you use nCr.

nCr (combinations) is used when order does not matter.

What they actually do:

Now that you hopefully understand when to use which one, let’s move on to what they actually do.

nPr
As mentioned, nPr is finding all of the permutations that exist within a given set for a given subset. In our particular example, it will look at how many different outcomes can result from the race which would result in a podium permutation (different order).

there are 2730 different outcomes that can occur with the podium
this is the equation you’re calculator is computing. n is the number of contestants in the race, and r is the number that makes it to the podium

In our race:

15 -3 = 12

Okay, so we’ve broken the magical button a little bit more down, but you might be asking yourself now…why is this the equation, and why are all the numbers yelling at me!!!! — what does the ! mean

! or otherwise known as factorial is simply a convenient way to express a series of multiplication.

In particular:

This is saying that n! = n x (n-1) x (n-2) (n-2)…and so on until you get all the way to the bottom — but not zero because when you multiple by zero the answer becomes zero

Let’s illustrate by going back to our example:

n = 15 (because there are 15 athletes)

n! = 15! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

This is what your calculator is computing when you enter the !button.

15! = 1 307 674 368 000

this number represents the maximum number of different orders that can occur from a list. Our list is 15 runners, and there are 1 307 674 368 000 different ways their placement can be arranged. The multiplied number is decreasing because as a number is placed, that spot is now taken up.

If Runner 1 places in 15th, there are only 14 other places to land for all remaining runners, if Runner 2 places in 14th, there are now only 13 spots left for all runners. Like most things, its more easily explained by scaling the numbers:

Simpler Example (can skip if you already grasp):

Let’s say there are four available seats, and 4 friends looking to sit. For the first seat, there are four potential outcomes (any one of the four friends can grab it), once it has been taken, the second seat only has three different potential outcomes (any one of the 3 unseated friends can grab it), the third seat only has two possibilities, and the last seat by default only has one option — the poor sucker that hasn’t sat yet.

As a result, mathematically, there is 4 x 3 x 2 x 1 potential outcomes.

If the race was simply asking how many different ways can the order of the race change, we wouldn’t use nPr, we would use factorial(!)…but it’s not…it’s asking how many times the podium can change which is specifically looking at the top three runners, not all of them. As a result, we don’t use factorial. Factorial is too wide a scope.

Because it is too wide, we need to reduce it. We are only examining the first three positions, not the remaining 12. Stated differently, if the order of the first three changes, then it is considered a new permutation, but if the order of the first three stays the same, (even if the order of the remaining 12 changes) then we don’t consider it a new permutation.

Because 12 positions are irrelevant we need to reduce their importance in the equation.

This is why we get

The easiest way to remove the relevance of the remaining 12 positions is to divide the full possibility number(!) by the possible number for irrelevant positions. As previously stated, there are 12 positions that are irrelevant to our podium.

so 15! divided by (15 -3)!

12 because it is the number of runners whose order we don’t care about

This equates to writing out:

which equates to 15 x 14 x 13 because all of the rest of the numbers cancel themselves out.

15 x 14 x 13 also = 2730

Now let’s look at nCr:

Whew, that took a long time to get through permutations, this round should be quicker because I’ve already talked about factorials now.

As mentioned, nCr, is finding all of the combinations that exist within a given set for a given subset when order doesn’t matter. In our example, it looks at the number of different combinations that can occur for winning the medal (i.e. finishing in the top three)

15c3 is usually written in the bracket form but means the same thing

Now right off the bat, you’ll notice that there is less combinations then there are permutations (455 < 2730). This makes sense because combinations is marking ABC and ACB as the same, whereas permutation differentiates between the two. Let’s examine what your calculator is doing when you hit the button.

equation for nCr

Now the first thing you should notice is that the equation is pretty similar to the permutations equation, except there is more added to the denominator (it is k!(n-r)!, not just (n-r)!

According to the previous statement, this makes sense as adding more to the denominator will result in a smaller outcome (e.g. 10/2) < 10/5), and we’ve established that combinations will be smaller than permutations.

If you paid attention/my writing makes any sense, we should already know why you add (n-r)! to the equation. If you don’t, ctrl/command +f “too wide a scope” and read that passage again.

We add r! to the denominator because there are r! ways that the medal winners stay the same, while the order of them switches.

For each set of three medal winners, they can be shuffled around 3! times to create a new permutation (3! = 6 times)…but we don’t care about this permutation. Those 6 different permutations are really just one combination of athletes, so we want to pull it from our answer. The easiest way to do this is to add it to the denominator so that it is pulled out of numerator.

= 455

It’s no coincidence that 455 x 3! = 2730.

Anyways, that’s all I’ve got for today. Hopefully, that makes sense.

Ciao,

Benchmarked Path

Written by

On a journey to master data science…starting from scratch. I’ll be posting along the way to help my absorption, and hopefully, help you too.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade