Counting techniques
When calculating probabilities we often needed to count the number of outcomes. We can do this by writing down all the outcomes in a list, table or 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. Counting techniques are short cut ways to count the number of options without listing them all.
We are going to focus on problems that involve combinations. 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?
Number of ways to arrange $n$n objects - order important.
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. 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.
Ways to select and arrange $r$r objects from $n$n objects - order important.
What if we only wanted to select and arrange $3$3 letters from a set of $7$7 letters? How many arrangements are there if we consider an arrangement of $ABC$ABC to be different from $BAC$BAC? In other words order is important.
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).
Ways to select and arrange $r$r objects from $n$n objects - order not important.
Consider the problem of selecting $3$3 letters from the letters $A$A, $B$B, $C$C and $D$D, where we consider the selection $ABC$ABC to be the same as $BCA$BCA. In this case the order is not important. For example: 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 the $3$3 objects which 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)!.
There are $n!$n! ways to arrange $n$n objects if order is important ($ABC$ABC is different from $BAC$BAC).
The number of ways to select and arrange $r$r objects from $n$n objects if order is important is $\frac{n!}{\left(n-r\right)}$n!(n−r).
The number of ways to select $r$r objects from $n$n objects if order is not important ($ABC$ABC is the same as $BAC$BAC) is $\frac{n!}{r!\left(n-r\right)!}$n!r!(n−r)!
Combinations
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.
The number of combinations of $r$r objects from $n$n distinct objects is:
$^nC_r=\frac{n!}{r!\left(n-r\right)!}$nCr=n!r!(n−r)!
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 and for each draw six balls are selected. How many combinations are possible?
Think: Identify $n$n and $r$r for the formula and use your calculator. We are selecting $6$6 balls from $45$45.
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. We are selecting $2$2 from $8$8 or $3$3 from $8$8.
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
A boss wants to select one group of $4$4 people from his $28$28 staff.
How many different groups are possible?
QUESTION 2
A tea shop sells $10$10 different types of tea and $7$7 different sets of teacups, and has room to display $6$6 types of tea and $3$3 sets of teacups. The owner changes the display each month. How many different display combinations of tea and tea cups are possible?
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 is 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
Evaluate $\nCr{7}{2}$7C2.
QUESTION 4
Out of a $16$16-man cricket touring squad, $12$12 are to be selected for the team.
How many different teams can be made?
Two opening batsmen are to be selected from among the $12$12 chosen players. How many combinations of opening batsmen are possible?
QUESTION 5
$5$5 boys and $6$6 girls are part of the debate team. $4$4 of them must represent the school at the upcoming debate tournament. In how many ways can the team of $4$4 be formed if:
it must contain $2$2 boys and $2$2 girls?
it must contain at least $1$1 boy and $1$1 girl?