6.07 Combinations

Counting methods

In our calculations for probabilities we often needed to count the number of outcomes. We could do this by writing down all the outcomes in a list, table or by drawing a tree diagram. However, often the sample space is very large or complex and these methods quickly become unmanageable. Think of trying to list the sample space or drawing a tree diagram for selecting $2$2 cards from a deck without replacement. On the first selection we have $52$52 options and then each of these has $51$51 options, so we would need to list $2652$2652 options. We can use counting methods to count the number of options without listing them all. Patterns often arise in the number of outcomes in a given problem and counting techniques were developed to create shortcuts for counting outcomes in different types of problems. 

We are going to focus on problems that involve combinations and how to count them. For example:

• How many different selections can be made of two scoops of ice-cream from $8$8 flavours?
• How many different committees can be formed when choosing four people from a class of $25$25?
• How many different lottery outcomes are there of six balls chosen from $45$45 balls?
• How many different fruit smoothies can be made from a combination of banana, strawberry, watermelon and blueberries?

To understand how the formula for combinations comes about, let's first consider how many ways there are to arrange $n$n objects.

For example, if we have the letters $A$A, $B$B and $C$C, how many different arrangements can be made?

Let's list them for this case and think about how we can count this if there were more letters.

$ABC$ABC	$BAC$BAC	$CAB$CAB
$ACB$ACB	$BCA$BCA	$CBA$CBA

We can see there are $6$6 choices in total, can we calculate this another way? We could think about this diagrammatically by creating a box for each letter in our arrangement and then writing the number of options in each box.

We have $3$3 options for the first box, then $2$2 letters left to select from for the second box and then only $1$1 letter left to complete the arrangement.

Multiplying the options, we get our total number of arrangements, $6$6. You could imagine a tree diagram would have three branches for the initial selection, then two for the second selection and one for the final selection, making $6$6 final outcome branches.

If we were to arrange $5$5 letters we can count the number of arrangements in the same way by drawing five boxes, the first would have $5$5 options, the next $4$4 and so forth. So the number of arrangements must be $5\times4\times3\times2\times1=120$5×4×3×2×1=120. And in general the number of ways to arrange $n$n objects is $n\times\left(n-1\right)\times\left(n-2\right)\times\left(n-3\right)\times......\times3\times2\times1$n×(n−1)×(n−2)×(n−3)×......×3×2×1. Have you seen expressions like this before? This type of descending multiplication arises frequently in Mathematics and has its own notation.

We refer to the product as $n$n factorial and  it has the notation $n!$n!. So $4!=4\times3\times2\times1=24$4!=4×3×2×1=24 and $6!=6\times5\times4\times3\times2\times1=720$6!=6×5×4×3×2×1=720. 

Factorials grow quickly. For example, $18!=6402373705728000$18!=6402373705728000. In fact, the number $61!$61! is larger than the current estimate of atoms in the universe! Can you work out how many zeros there would be at the end of $100!$100!?

So now we know there are $n!$n! ways to arrange $n$n objects. What if we only wanted to arrange $3$3 letters out of a set of $7$7 letters? How many arrangements are there?

We can start with our three boxes again:

This time we have $7$7 options for the first box, $6$6 options left for the second box and $5$5 options for the final box.

Hence, we have $7\times6\times5=210$7×6×5=210 options to select and arrange three items out of a set of seven. How do we create a formula for this? Notice that the start looks like $7!$7!, we have the $7\times6\times5$7×6×5 but we are missing the rest $4\times3\times2\times1$4×3×2×1, we are missing $4!$4!. This could be achieved by dividing $7!$7! by $4!$4! and dividing out common factors:

$\frac{7!}{4!}$7!4!​	$=$=	$\frac{7\times6\times5\times4\times3\times2\times1}{4\times3\times2\times1}$7×6×5×4×3×2×14×3×2×1​
	$=$=	$7\times6\times5$7×6×5

And in general the number of ways to select and arrange $r$r objects from $n$n objects is $\frac{n!}{\left(n-r\right)}$n!(n−r)​.

Almost there... the type of problem we are concerned with are selections where order is not important. For example for a question involving how many combinations of letters can be made by selecting $3$3 letters from the letters $A$A, $B$B, $C$C and $D$D, we would consider the selection $ABC$ABC the same as $BCA$BCA. Or if we were counting the number of different selections of two scoops of ice-cream for a bowl, we would consider the combination chocolate and strawberry the same combination as strawberry and chocolate. 

From our formula for selecting and arranging $r$r objects from $n$n objects we need to remove all the options we counted more than once. If we were selecting $3$3 objects from $5$5 objects then we have counted each arrangement of $3$3 objects separately. To get just the number or selections, counting only $1$1 arrangement of each selection we need to divide by the number of ways to arrange $3$3 objects. Well that is $3!$3!. So the number of ways to select $3$3 objects from $5$5 objects is $\frac{5!}{3!\times2!}=10$5!3!×2!​=10.

In general, the number of ways to select $r$r objects from $n$n objects is $\frac{n!}{r!\left(n-r\right)!}$n!r!(n−r)!​. 

Combination

In Mathematics, a combination is a selection of some or all of the elements of a set with no regard for order. The number of selections of $r$r objects from a set of $n$n distinct objects is given the notation $^nC_r$nCr​ or$\binom{n}{r}$(nr) or $C_r^n$Cnr​ or sometimes even $C\left(n,r\right)$C(n,r).

$^nC_r$nCr​ is often read as "$n$n choose $r$r". Since we are choosing $r$r objects from $n$n objects.

Your calculator will have options to calculate factorials and combinations. Ask your teacher if you are unsure where to find these options on your calculator.

Worked example 

Example 1

In a lottery the balls are numbered $1$1 to $45$45, for each draw six balls are selected. How many combinations are possible?

Think: Identify $n$n and $r$r for our formula and use your calculator.

Do: $n=45$n=45 and $r=6$r=6, 

$^{45}C_6$45C6​	$=$=	$\frac{45!}{6!\left(45-6\right)!}$45!6!(45−6)!​
	$=$=	$8145060$8145060

Reflect: Do these numbers reflect a real life lottery? How small are the chances of selecting a winning number?

Example 2

How many different combinations of two or three flavours of ice-cream can be selected from $8$8 possible flavours?

Think: We have an or statement, we need to add the combinations of two scoops to the number of combinations with three scoops.

Do: 

$^8C_2+^8C_3$8C2​+8C3​	$=$=	$\frac{8!}{2!\left(6\right)!}+\frac{8!}{3!\left(5\right)!}$8!2!(6)!​+8!3!(5)!​
	$=$=	$28+56$28+56
	$=$=	$84$84

Caution: Watch for statements including 'and' or 'or'. Generally, 'and' means we need to multiply the options and 'or' means we need to add the options.

Practice questions

QUESTION 1

QUESTION 2

Combinations with restrictions

Let's now look at examples which have restrictions imposed to the combinations.

Worked example

Example 3

A selection of $4$4 people are to be chosen from a group of $9$9 people.  How many selections are possible if the youngest or oldest is included but not both? 

$4$4 people can be chosen from $9$9 in $^9C_4$9C4​ ways, which is $\frac{9!}{4!5!}=126$9!4!5!​=126 ways.

BUT, we have a restriction regarding the oldest or youngest.  

So what we have here is two possible situations to consider. We have the combinations where the youngest is selected plus the combinations where the oldest is selected. One of the $4$4 positions will be taken by this person, this leaves $3$3 positions to fill.  Both youngest and oldest get removed from the $9$9 people since their selections are already known.  This means that there will be $7$7 people left to choose from.  

This results in: 

$^7C_3+^7C_3=70$7C3​+7C3​=70.  

So there are $70$70 ways this selection can be made. 

Practice questions

QUESTION 3

QUESTION 4