Lesson 6 of 8 · 18 min

Combinations: choosing without order

Count unordered selections with nCr, see how combinations come from permutations, and decide which one a problem needs.

What you will be able to do

  • Define a combination as a selection where order does not matter.
  • Use nCr=(nr)=n!r!(n−r)!{}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}, and explain how it follows from nPr{}^nP_r.
  • Use (nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r} to simplify calculations.
  • Decide whether a problem needs a permutation or a combination, and solve problems with combinations.

A coach picks 3 of 5 players (Ana, Bo, Cai, Dev and Eli) for a training drill. Picking Ana, Bo and Cai gives the same drill group as picking Cai, Ana and Bo. Order does not matter: this is a selection, not an arrangement.

Definition

Combination

A combination is a selection of objects in which order does not matter. The number of combinations of rr objects chosen from nn distinct objects is written (nr)\binom{n}{r} or nCr{}^nC_r, read "nn choose rr".

Count the ordered line-ups first: 5P3=5×4×3=60{}^5P_3 = 5 \times 4 \times 3 = 60. Every group of 3 players appears in 3!=63! = 6 different orders among those 60. So the number of different groups is 606=10\frac{60}{6} = 10.

The permutations count each group of 3 players 3!=63! = 6 times.
GroupIts 6 orders
{A,B,C}\{A, B, C\}ABC, ACB, BAC, BCA, CAB, CBA
{A,B,D}\{A, B, D\}ABD, ADB, BAD, BDA, DAB, DBA
⋮\vdots⋮\vdots
10 groups10×6=6010 \times 6 = 60 orders

Key idea

The combinations formula

nCr=(nr)=nPrr!=n!r! (n−r)!{}^nC_r = \binom{n}{r} = \frac{{}^nP_r}{r!} = \frac{n!}{r!\,(n-r)!}

Choosing rr objects and then arranging them produces every permutation exactly once, so nPr=r!×nCr{}^nP_r = r! \times {}^nC_r.

Interactive

Groups, not orders

Choose 3 players. Reordering them does not change the group, so there are only 5C3=10{}^5C_3 = 10 different groups.

Evaluate (83)\binom{8}{3} without a calculator.

Worked example

A squad or a relay team?

  • Simple familiar

A coach has 10 swimmers.

(a) In how many ways can she choose a squad of 4 to travel to a carnival?

(b) In how many ways can she choose a relay team of 4 and decide who swims each of the four legs?

(c) Explain the connection between your answers.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Ask: does swapping two chosen objects change the outcome?

  2. No: use (nr)\binom{n}{r}. Yes: use nPr{}^nP_r.

  3. nPr=r!×(nr){}^nP_r = r! \times \binom{n}{r} links the two.

Watch out for

  • Using 10P4{}^{10}P_4 for the squad, which counts each squad 24 times.

Symmetry. Choosing the 3 players who train is the same as choosing the 2 who rest. So (53)=(52)=10\binom{5}{3} = \binom{5}{2} = 10. In general:

Choosing rr objects to take is the same as choosing n−rn - r to leave behind.
(nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r}
Interactive

Pascal's triangle holds every combination

Row nn, entry rr (both counted from 0) is (nr)\binom{n}{r}. The highlighted entry is (83)=56\binom{8}{3} = 56. Each row reads the same forwards and backwards, which is the symmetry (nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r}.

Note

Values worth knowing

(n0)=(nn)=1\binom{n}{0} = \binom{n}{n} = 1 (one way to choose nothing, or everything), (n1)=n\binom{n}{1} = n, and (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}.

Pascal's rule: each entry is the sum of the two above it

Pick one particular object, say Ana. Every selection of rr objects from nn either includes Ana or does not. These two cases cannot overlap, so by the addition principle:

  • selections that include Ana: choose the other r−1r - 1 from the remaining n−1n - 1, in (n−1r−1)\binom{n-1}{r-1} ways;
  • selections that leave Ana out: choose all rr from the remaining n−1n - 1, in (n−1r)\binom{n-1}{r} ways.
(nr)=(n−1r−1)+(n−1r)\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}

That is exactly how each row of Pascal's triangle is built from the row above. Mathematical Methods links the triangle to the binomial theorem.

Order matters: permutation

Arrangements, rankings, different roles, codes, seating.

A president, secretary and treasurer from 12 members: 12P3=1320{}^{12}P_3 = 1320.

Order does not matter: combination

Groups, teams, committees, hands of cards, toppings.

A committee of 3 from 12 members: (123)=220\binom{12}{3} = 220.

Which of these is counted by (204)\binom{20}{4}?

Choose one answer

Worked example

Working backwards from the number of handshakes

  • Complex familiar
  • Technology free

At a meeting, every person shakes hands with every other person exactly once. There are 66 handshakes. How many people are at the meeting?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Decide whether the count is a permutation or a combination, and write it in terms of nn.

  2. Simplify the factorials to a polynomial.

  3. Solve, and keep only positive integer solutions.

Watch out for

  • Writing (n2)=n(n−1)\binom{n}{2} = n(n-1), which forgets to divide by 2 and counts ordered pairs.

  • Leaving n=−11n = -11 in the answer.

Common mistake

Using a permutation for a committee

A committee of 3 has no first, second or third member. Using 12P3=1320{}^{12}P_3 = 1320 counts each committee 3!=63! = 6 times. Ask yourself: if I swap two of the chosen objects, is it a different outcome? If not, use combinations.

Without technology

Cancel before multiplying:

(123)=12×11×103×2×1=220\binom{12}{3} = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = 220

Use symmetry first if it helps: (1210)=(122)=66\binom{12}{10} = \binom{12}{2} = 66.

With technology

Enter 12, nCr, 3 in the probability menu. For large values such as (456)=8 145 060\binom{45}{6} = 8\,145\,060, technology is the sensible choice. Still write the expression.

Summary

  • A combination is a selection where order does not matter.

  • nCr=(nr)=n!r! (n−r)!=nPrr!{}^nC_r = \binom{n}{r} = \frac{n!}{r!\,(n-r)!} = \frac{{}^nP_r}{r!}, because each selection of rr appears r!r! times among the permutations.

  • (nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r}: choosing what to take is choosing what to leave.

  • Useful values: (n0)=(nn)=1\binom{n}{0} = \binom{n}{n} = 1, (n1)=n\binom{n}{1} = n, (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}.

  • Test for order: if swapping two chosen objects gives a different outcome, use a permutation; if not, a combination.

Finished the lesson?

Try the 2 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 6 of 80% read

Save your progress with a free account