Whether the ORDER is important or not. Obviously for the salad, it doesn't matter which order the ingredients go in - but it is a very different story for the lock. Any other order like $853$853 or $385$385 for example will not open the lock.

This is the difference between our permutations and combinations. Permutations is like the lock, the order matters and we treat the $853$853 as different to $358$358. Combinations are where the order doesn't matter so we treat the lettuce, tomato and onion salad as the same as a salad with onion, lettuce and tomato.

As we have already looked at Permutations and a way to calculate total possible arrangements, we can consider permutations as an ORDERED version of a combination.

Let's look at our example using coloured spots.

If I have a red dot, blue dot and green dot; then I could choose any two of them and end up with the following options.

You'll notice also that in this example, that I have listed out 6 possible selections of 2 spots. We are yet to determine if the order matters. That is, does the answer of a red and green spot, mean exactly the same thing as a green and red spot?

If the answer is NO. That RED, GREEN is different to GREEN, RED, then the order matters and we have a permutation and the answer is 6.

If the answer is YES. That RED, GREEN is the same as GREEN, RED, then the order DOESN'T matter and we have a combination and the answer would be 3.

This idea of counting how many possible different combinations there are is part of a mathematical topic called Counting Techniques. For small sets like the one above, it's quite simple to write down all the choices and add them up. But for larger sets, like imagine we had $8$8 colours and wanted to see how many different combinations of $5$5 colours there are - we need a more efficient method of counting.

Lotto

The lotto (or lottery) is an example of a combination. It doesn't matter what order the balls are drawn, or what order you picked your numbers as long as at the end of the draw, the numbers on your ticket match the numbers that were drawn.

Let's work through an example of a very simple lotto game. There are $10$10 balls and we can win $\$400$$400 if the $3$3 numbers we choose are drawn.

How many arrangements?

How many possible ways can we draw $3$3 balls from $10$10?

$10$10	$9$9	$8$8

We have $10$10 possibilities for the first ball, then $9$9 for the second and then finally $8$8 for the third.

The answer to this is $P(10,3)=10\times9\times8=720$P(10,3)=10×9×8=720

So there are $720$720 arrangements. But in this list would be options like

$5,6,7$5,6,7 and $5,7,6$5,7,6 and $6,7,5$6,7,5 and $6,5,7$6,5,7 and $7,5,6$7,5,6 and $7,6,5$7,6,5..... all of which are actually the same with regards to our lotto game.

So what we want to do is remove all these possible double ups.

As we are choosing $3$3 balls, there are $3!=3\times2\times1=6$3!=3×2×1=6 times as many arrangements than we need.

So we take our permutations formula $\frac{n!}{(n-r)!}$n!(n−r)! and divide through by $r!$r! (to remove the double ups).

Thus creating our combination formula for choosing $r$r objects from $n$n.

$C(n,r)=\frac{n!}{r!(n-r!)}$C(n,r)=n!r!(n−r!)

So for our lotto game,

$C\left(10,3\right)=\frac{10!}{3!7!}=\frac{10\times9\times8\times7!}{3!7!}=\frac{10\times9\times8}{3\times2}=\frac{720}{6}=120$C(10,3)=10!3!7!=10×9×8×7!3!7!=10×9×83×2=7206=120 different combinations.

So we have a $1$1 in $120$120 chance of winning.

Notation for Combinations

$C(n,r)$C(n,r)

The symbol $C(n,r)$C(n,r) with $r\le n$r≤n is a short hand notation for the expression $\frac{n!}{r!\left(n-r\right)!}$n!r!(n−r)!.

For example $C\left(5,2\right)=\frac{5!}{2!\times3!}=\frac{5\times4\times3!}{\left(2\times1\right)\times3!}=\frac{5\times4}{2}=10$C(5,2)=5!2!×3!=5×4×3!(2×1)×3!=5×42=10.

Note that $C\left(n,r\right)=\frac{n!}{r!\times\left(n-r\right)!}=\frac{n!}{\left(n-r\right)!\times r!}=C\left(n,n-r\right)$C(n,r)=n!r!×(n−r)!=n!(n−r)!×r!=C(n,n−r). This means for example that $C(12,4)=C(12,8)$C(12,4)=C(12,8) and $C(7,1)=C(7,6)$C(7,1)=C(7,6). There is a nice symmetry with this expression.

Since $0!=1$0!=1 and $1!=1$1!=1, we have by definition that $C\left(n,0\right)=\frac{n!}{0!\times\left(n-0\right)!}=\frac{n!}{1\times n!}=1$C(n,0)=n!0!×(n−0)!=n!1×n!=1.

For example, $C\left(5,0\right)=1$C(5,0)=1 and $C\left(12,0\right)=1$C(12,0)=1.

Finally we can form a relationship between $C(n,r)$C(n,r) and the previous $P(n,r)$P(n,r) as follows:

$C\left(n,r\right)$`C`(`n`,`r`)	$=$=	$\frac{n!}{r!\times\left(n-r\right)!}$`n`!`r`!×(`n`−`r`)!
	$=$=	$\frac{n\times\left(n-1\right)\times\left(n-2\right)\times...\times\left(n-r+1\right)\times\left(n-r\right)!}{r!\times\left(n-r\right)!}$`n`×(`n`−1)×(`n`−2)×...×(`n`−`r`+1)×(`n`−`r`)!`r`!×(`n`−`r`)!
	$=$=	$\frac{n\times\left(n-1\right)\times\left(n-2\right)\times...\times\left(n-r+1\right)}{r!}$`n`×(`n`−1)×(`n`−2)×...×(`n`−`r`+1)`r`!
	$=$=	$\frac{P\left(n,r\right)}{r!}$`P`(`n`,`r`)`r`!

So $C\left(n,r\right)=\frac{P\left(n,r\right)}{r!}$C(n,r)=P(n,r)r! and this is another important mathematical result in the study of probability.

Another type of notation that is used in combinations is ⁿC_r it means the same as $C(n,r)$C(n,r).

We can also write it as $\binom{n}{r}$(nr)

Worked Examples

QUESTION 1

Evaluate $\nCr{7}{2}$7C2.

QUESTION 2

A $boss$ wants to select one group of $4$4 people from his $28$28 $staff$ .

How many different groups are possible?

Outcomes

11.A.PC.1

Fundamental principle of counting. Factorial n. Permutations and combinations, derivation of formulae and their connections, simple applications.

Introduction to Combinations

Combinations