EN5 - Combinations (unordered selections)

EN5 - Combinations (unordered selections)

Choosing a team records who is in it, rather than an order for its members. You will count these unordered selections with nCr{}^nC_r, explain why the formula divides out repeated orders and combine choices from separate groups. You will also distinguish “exactly”, “at least” and alternative cases in selection problems.

Why reordering a team does not change it

A club has ten members. How many different two-person teams can it choose? Last lesson gave 10×9=9010\times9=90 allocations of two different roles, but a team has no first and second role. If Amira and Ben form the team, writing Ben before Amira does not create another one. Where is that repeated counting hidden?

With three people, A,B,CA, B, C, two different roles produce AB,BA,AC,CA,BC,CBAB, BA, AC, CA, BC, CB. Teams produce just {A,B},{A,C},{B,C}\{A, B\}, \{A, C\}, \{B, C\}. Each team has appeared twice in the ordered list.

You already know

Permutations record order: nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}. The same rr distinct people can be put into rr distinguished positions in r!r! ways.

For three-person teams the repeated count is larger. The team {A,B,C}\{A, B, C\} appears as ABC,ACB,BAC,BCA,CAB,CBAABC, ACB, BAC, BCA, CAB, CBA: six orders of the same three people. Dividing an ordered count by 33 would not remove all those repetitions; dividing by 3!=63!=6 does.

Combination

A combination of rr objects from nn distinct objects is an unordered selection without repetition. For example, a three-person committee with no distinguished roles is a combination. Allocating chair, secretary and treasurer is a permutation, because swapping the chosen people changes the outcome.

The objects are still distinct even though their order is ignored. Two people are not interchangeable as people; it is only the order of writing their names that makes no difference. Repeated selection of the same object is not allowed in this formula.

Key idea

If the same chosen objects in a different order give the same outcome, count the selection once.

Look for the situation where roles distinguish the positions.

Removing the repeated orders with factorials

Every selection of rr distinct objects generates exactly r!r! ordered selections, so divide the permutation count by r!r!. Thus nCr=nPrr!{}^nC_r=\frac{{}^nP_r}{r!}; this relationship is not printed on the formulae sheet, so learn its reasoning.

For example, from 55 people there are 5×4×3=605\times4\times3=60 ordered choices of three. The same three-person team appears 3!=63!=6 times, so there are 60÷6=1060\div6=10 teams. The division is fair because every team, not just some teams, has exactly six orders.

[DIAGRAM: asset_name: Six orders represent one three-person team; asset_slug: en5-six-orders-one-team; caption: Divide the ordered count by 3 factorial because each three-person team appears six times; description: Six pale blue boxes labelled ABC, ACB, BAC, BCA, CAB and CBA point to a single pale sage box containing the team A B C. A note states that the same three members occur in every ordering and that 3 factorial equals 6.]
Divide the ordered count by 3 factorial because each three-person team appears six times

Combinations of distinct objects

nCr=n!r!(n−r)!{}^nC_r=\frac{n!}{r!(n-r)!}

Here nn and rr are integers with 0≤r≤n0\le r\le n. Order is ignored and selection is without repetition. OCR also writes (nr)\binom nr.
On the formulae sheet.

The formula is printed with the binomial series on the formulae page in the question paper. It gives a count, not a probability. In a written solution, show the combination expression with its actual values of nn and rr.

Worked example 1: choosing a pair

Question. Two representatives are chosen from a group of 99 people. The representatives have identical roles. Find the number of possible selections.

Plan. Count unordered pairs, dividing the ordered count by the two orders of each pair.

N=9C2order is ignored=9!2!7!n=9, r=2=9×82×1=36cancel common factors\begin{aligned} N&={}^9C_2 && \text{order is ignored}\\ &=\frac{9!}{2!7!} && n=9,\ r=2\\ &=\frac{9\times8}{2\times1}=36 && \text{cancel common factors} \end{aligned}

Why divide by 2!2!? Each pair would otherwise be counted once in each name order.

Answer. 3636 selections.

Check. List the possible partners of the first person, then pairs not using that person: 8+7+6+5+4+3+2+1=368+7+6+5+4+3+2+1=36.

The next example changes only the number selected: three representatives are required.

Worked example 2: choosing a triple

Question. Three representatives with identical roles are chosen from the same group of 99 people. Find the number of possible selections.

Plan. Use r=3r=3, so each team has 3!=63!=6 orders to remove.

N=9C3three unordered members=9!3!6!n−r=6=9×8×73×2×1=84divide out six orders\begin{aligned} N&={}^9C_3 && \text{three unordered members}\\ &=\frac{9!}{3!6!} && n-r=6\\ &=\frac{9\times8\times7}{3\times2\times1}=84 && \text{divide out six orders} \end{aligned}

Why not divide by 33? A team of three has six possible orders, not three.

Answer. 8484 selections.

Check. 84×3!=84×6=504=9P384\times3!=84\times6=504={}^9P_3, recovering the ordered count.

Choosing the people to leave out gives the same count as choosing those to include: nCr=nCn−r{}^nC_r={}^nC_{n-r}. For instance, choosing 88 of 1010 people is equivalent to choosing the 22 excluded people. This symmetry is not separately printed on the formulae sheet: learn it. It also follows from the given formula because r!r! and (n−r)!(n-r)! swap places.

At the boundaries, nC0=nCn=1{}^nC_0={}^nC_n=1: there is one empty selection and one selection containing everyone. An rr larger than nn is impossible here, so do not enter it into the factorial formula.

Watch out

Wrong: 9×8×7=5049\times8\times7=504 teams of three. That counts orders, so each team occurs six times. Right: 9C3=504÷6=84{}^9C_3=504\div6=84. A count of teams should not be turned into a probability unless the question asks for one.

Change the number available while keeping a three-person selection.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account