# How/Why do nPr and nCr work?

## I know the formulas and how/when to use them, but why are they the way they are? Why do they work?

#### Explanation:

I answered a question similar to this a little while ago. Here's the link: https://socratic.org/questions/how-do-you-answer-something-like-7c3-for-a-combination-and-8p3-for-a-permutation405503

Here are the relevant bits from that answer:

Combinations, Permutations, and Factorials are used to help calculate the numbers of ways something can be done or ordered.

For instance, let's say we have 5 distinguishable books and want to arrange them on a shelf. How can we do this?

There are 5 books we can place in the first position, 4 in the second, 3 in the third, etc... and so we can express the number of ways we can order the books on the shelf by saying:

$5 \times 4 \times 3 \times 2 \times 1 = 120$

Because we do this so often in Permutation and Combination problems, it'd be convenient to have some sort of symbol to let us know that we want to multiply all the natural numbers up to a given value - and this is done via the Factorial :

5xx4xx3xx2xx1=5! = 120

Now let's say we have 7 books and want to arrange 5 on the shelf. We could use the same sort of logic as before, see that there are 7 books we can put in the first position, 6 in the second, 5 in the third, etc, all the way to 3 at the fifth and final book. I can write that as:

$7 \times 6 \times 5 \times 4 \times 3$

and I can sit down and multiply this out each time depending on the number of books available and the ones I intend to arrange. Or I can see that if I simply do this:

$\frac{7 \times 6 \times 5 \times 4 \times 3 \textcolor{red}{\times 2 \times 1}}{\textcolor{red}{2 \times 1}}$

I can now express this in terms of two factorials:

(7xx6xx5xx4xx3color(red)(xx2xx1))/color(red)(2xx1)=(7!)/(2!)

and I can even go one more step and see that I can express the denominator in terms of the number of books I have and the number of books on the shelf:

(7!)/(2!)=(7!)/((7-5)!)

And with this we have the general formula for a Permutation :

P_(n,k)=(n!)/((n-k)!); n="population", k="picks"

That equation works well if we care which book is in which position on the shelf. But what if we don't care? If we simply say that simply having the History book, the English book, and the Math book on the shelf together in any order counts as 1 way or ordering (this is much like a poker hand - we don't care in what order we draw the cards, we simply want the best hand possible)? To do this, we divide the Permutation by the number of items picked - we are essentially taking out the "repeats". Sticking with the 7 books available and 5 books to be placed on a shelf:

(7!)/((5!)(2!))=(7!)/(5!(7-5)!)

And with this we have the general formula for a Combination:

C_(n,k)=(n!)/((k!)(n-k)!)# with $n = \text{population", k="picks}$