5.03 Combinations

Counting methods

When calculating probabilities, there is often a need to count the number of outcomes. This can be done 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 there are $52$52 options and then each of these has $51$51 options, so this would need a list of $2652$2652 options! Instead, it is more efficient to 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. 

Here, the focus is 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, first consider how many ways there are to arrange $n$n objects.

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

List them for this case and think about how to count this if there were more letters.

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

There are $6$6 choices in total, but can this be calculated another way? This could be thought of diagrammatically by creating a box for each letter in the arrangement and then writing the number of options in each box.

There are $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, this is the total number of arrangements, $6$6. Imagine a corresponding 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.

To arrange $5$5 letters, 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. 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.

This product is referred to 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, knowing that 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?

Start with the three boxes again:

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

Hence, there are $7\times6\times5=210$7×6×5=210 options to select and arrange three items out of a set of seven. How can a formula be created for this? Notice that the start looks like $7!$7!, with the $7\times6\times5$7×6×5, but is missing the rest $4\times3\times2\times1$4×3×2×1. That is, it is 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

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)​.

Another consideration is for 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, consider the selection $ABC$ABC the same as $BCA$BCA. Or, if counting the number of different selections of two scoops of ice-cream for a bowl, consider the combination chocolate and strawberry the same combination as strawberry and chocolate. 

From the formula for selecting and arranging $r$r objects from $n$n objects, this situation requires removing all the options 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 requires dividing by the number of ways to arrange $3$3 objects. Here, 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)!​
	$=$=	$81455060$81455060

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