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?
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.
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).
In our race:
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.
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)!
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)
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.
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.
It’s no coincidence that 455 x 3! = 2730.
Anyways, that’s all I’ve got for today. Hopefully, that makes sense.