P vs, C

Since that last post probably went over some heads (only John probably read the whole thing), I've decided to clarify my thinking on permutations and combinations. Apparently, my computer does not recognize the plural form of combination. Anyway, let's start with a permutation.

A permutation is just an ordering, really. Let's say we have two colors, red and blue. How can we order those? Well, (red, blue) is fine, and so is (blue, red), so we know that there are two permutations for two things. One way of expressing that would be P(2) = 2. What if we have five colors? We could list these out again, but common sense tells us that it's going to be quite a few things, and thus a formula would be much nicer. So, how do we get there?

Consider the first element of the order (permutation). There are five possibilities. For the next element, since we've already used one color, there are only four possibilities. So there are 5 x 4 = 20 ways of choosing the first two elements. Following this logic, there are three possibilities for the third element, two for the fourth, and one for the fifth, so we have

P(5) = 5 x 4 x 3 x 2 x 1 = 5! =120.

The exclamation point means factorial, and the definition of that should be obvious from that equation. Pistol Pete liked to just say things like "Five!" with the emphasis, as if it were an exclamation. Generalizing, we have

P(n) = n!

The next step is to think about not choosing all of the colors. That is, what if we wanted to know how many ways we could order two of the colors out of the five. The solution is actually pretty obvious, and we've done it before. You could think of it like this: for the first element, there are five choices, and for the second element there are four, so we have P(5, 2) = 5 x 4 = 20. What we want here is just the last n-r integers multiplied together. Here's another way of thinking of that. For every way of ordering the first two colors, there are 3 x 2 x 1 ways of choosing the last three, and ordering the first two and ordering the last three is the same as ordering all five. That is,

P(5, 2) x P(3) = P(5). Since we have a formula for P(n), we use algebra to get

P(5, 2) - P(5)/P(3); generalized,

P(n, r) = P(n)/P(n-r) = n!/(n-r)!

Now a note on notation. I am using P(n) to mean permutations of n things and P(n, r) to mean permutations of n things, r at a time. This is function notation, which makes sense because permutations are indeed functions (think about it if you aren't convinced), but permutations are often written in the form nPr. This is funny to fans of national public radio.

On to combinations. A combination is, in a way, simpler than a permutation. To continue with our color example, a combination of five colors two at a time would mean taking any two of the five colors (I did not specify colors here so that you can choose the ones you like), and not worry about the order. That is, if I choose my favorites, (green, yellow), and you choose (yellow, green), we have chosen the same combination and will only count that once. However, if you choose (green, blue), then we have chosen differently and will count that twice.

The easiest way (to my mind) of getting a formula for combinations is by looking at the formula for permutations. Again continuing our example, we had P(5, 2) = 5 x 4 = 2o ways of ordering two of the five colors at a time. But here, we don't care how they are ordered, only what colors we have chosen. So, the reasonable thing to do is divide by the number of ways of ordering the ones we have chosen. Fortunately, we already know how to do that. It should be 2! = 2 x 1 =2.
To generalize, we have

C(n, r) = P(n, r)/P(r) = n!/r!(n-r)!;

both those last two factors are in the denominator, if that wasn't clear. Again, I am using function notation, but nCr is also common, as well as just putting n over r (not division, there is no line) in parantheses following C. That is generally read "n choose r." And that's all there really is to it.