Introduction
Permutation and Combination is an important concept in statistics. The reason is because in order to know the probability of an event. we often have to calculate sample space.
Two words are essential regard to permutation and combination, one is order
another is replacement. One quick example will be the combination (general meaning)
of letters AB. If order matters AB and BA are different, we count them as 2,
but if order does not matter, we only count as 1. Next, if we take account of
replacement, we have AA, AB, BA, BB, we count to 4 in terms of order matters.
However, if we do not allow replacement, we only have AB and BA. Which we
can count to 2. The general idea behind it is that when we allow replacement and
order matters, there are more combinations (general meaning).
The main differece between permutation and combination is that permutaion order matters whereas combination does not.
Anatomy
We can create a table to cover the four cases
| case | replacement | order | outcome | calculation |
|---|---|---|---|---|
| 1 | 0 | 0 | (PI),(PN),(PG),(IN),(IG),(NG) | 3+2+1=6 |
| 2 | 0 | 1 | (PI),(PN),(PG),(IP),(IN),(IG),(NP),(NI),(NG),(GP),(GI),(GN) | 3+3+3+3=12 |
| 3 | 1 | 0 | (PP),(PI),(PN),(PG),(II),(IN),(IG),(NN),(NG),(GG) | 4+3+2+1=10 |
| 4 | 1 | 1 | (PP),(PI),(PN),(PG),(II),(IP),(IN),(IG),(NN),(NP),(NI),(NG),(GG),(GP),(GI),(GN) | 4x4=16 |
When we have the term replacement, it’s like we have a bag of balls. We can
draw a ball then put it back to the bag then draw another one. In terms of example
above, we can have the combination with itself. For term order, when order
matters, we are able to go backwards, like when we try to find the combination
for letter I, we are able to go backwards to letter P, which we have IP.
Whereas, when order does not matter, we can only move forward.
it seems there are centain patterns in the calculation like 3+2+1 and 4+3+2+1.
If there are certain patterns, we can find formulas to make calculation easier.
Formulas
the formulation for permutation \[ ^{n} P_{k} = \frac{n!}{(n-k)!} \] we read this as n choose k
and the formula for combination is \[ \left(\begin{array}{l}{n} \\ {k}\end{array}\right)=n C_{k}=\frac{n !}{k !(n-k) !} \]
Let’s calculate the result of above question by formulas. First of all, permutation
\[ \frac{4!}{(4-2)!} = 4\times 3=12 \]
the result matches the calculation above which is without replacement but order matters (case 2), then combination
\[ \frac{4!}{2!(4-2)!}=\frac{4\times 3}{2}=6 \]
Which also matches our case 1.
What is the formulas for case 3 and case 4? Which we take account of replacement. for case 3 we have \[ ^{n} C_{r}=\frac{(n+r-1) !}{r !(n-1) !} \]
Let’s further verify it \[ \frac{(4+2-1)!}{2!(4-1)!} = \frac{5!}{2!3!}=\frac{5\times 4}{2}=10 \]
it matches our result. Last one is permutation with replacement. \[ ^{n} P_{r}=n^{r} \]
Summary
Here is a summary table for the result
| case | replacement | order | formula |
|---|---|---|---|
| combination | 0 | 0 | \(\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=n C_{k}=\frac{n !}{k !(n-k) !}\) |
| permutation | 0 | 1 | \(^{n} P_{k} = \frac{n!}{(n-k)!}\) |
| combination | 1 | 0 | \(^{n} C_{r}=\frac{(n+r-1) !}{r !(n-1) !}\) |
| permutation | 1 | 1 | \(^{n} P_{r}=n^{r}\) |
as you can see above, when order is 0, we have combination. Whereas, when order is 1, we have permutation. This is the difference between permutation and combination we have discussed on section 1.
