5.01a, 5.01b - Probability with permutations and combinations

5.01a, 5.01b - Probability with permutations and combinations

Count outcomes before calculating their probabilities. You will distinguish ordered arrangements from unordered selections, handle repeated objects, and turn restrictions such as “together” or “not next to one another” into counts you can justify.

Ordered choices and permutations

Shuffle the six letter tiles of BANANA thoroughly and lay them in a line. Which is more likely: all three As together, or no two As next to one another? The two conditions look very different. By the end of the lesson you will count both, rather than trust a guess.

You already know

For equally likely elementary outcomes, a probability is the number of favourable outcomes divided by the total number of outcomes. Conditional probability restricts the sample space to the given event. These probability ideas come from A-level Mathematics; the new work here is counting the outcomes reliably.

Start with three distinct cards, A, B and C. Choosing a first card and then a second, without replacement, gives AB, AC, BA, BC, CA and CB. There are three choices followed by two choices: 3×2=63\times2=6. AB and BA count separately because the positions have different roles.

Permutation

A permutation is an ordered arrangement. The notation nPr{}^nP_r, also written nPrnP_r, counts ordered arrangements of rr objects chosen without replacement from nn distinct objects. For example, AB and BA are different permutations of two cards. Choosing the pair {A,B}\{\mathrm{A},\mathrm{B}\} without assigning positions is not a permutation.

Each first choice leaves the same number of second choices in the card example. More generally, multiply the numbers of choices at successive stages when every partial outcome has the stated number of continuations. If restrictions change that number, split into cases first.

Counting ordered choices

For integers n≥0n\geq0 and 0≤r≤n0\leq r\leq n:

n!=n(n−1)⋯2×1(n≥1),0!=1nPr=n(n−1)⋯(n−r+1)=n!(n−r)!\begin{aligned} n!&=n(n-1)\cdots2\times1\quad(n\geq1),\qquad 0!=1 \\ {}^nP_r&=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!} \end{aligned}

In particular, all nn distinct objects can be arranged in a line in n!n! ways. There is one empty arrangement when r=0r=0.
Not in the formula booklet: learn it.

Counting gives a probability only after you identify outcomes that really are equally likely. Uniformly assigning distinct runners to finishing positions supplies such a model; “each runner is equally strong” on its own would not specify every joint finishing order.

Worked example 1: three ordered places

Question. Six named runners are assigned gold, silver and bronze at random, with every ordered assignment equally likely. Find the probability that Ada receives one of the medals.

Plan. Count all ordered assignments, then choose Ada's position and fill the other two positions.

N=6P3=6×5×4=120three distinct positionsN(Ada has a medal)=3×5P2=3×20=60choose her position firstP(Ada has a medal)=60120=12equally likely assignments\begin{aligned} N&={}^6P_3=6\times5\times4=120 &&\text{three distinct positions} \\ N(\text{Ada has a medal})&=3\times{}^5P_2=3\times20=60 &&\text{choose her position first} \\ \mathrm{P}(\text{Ada has a medal})&=\frac{60}{120}=\frac12 &&\text{equally likely assignments} \end{aligned}

Why this step? Ada can occupy exactly one of the three positions, so the three position cases are disjoint and each leaves 5×45\times4 assignments.

Answer. 12\frac12

Check. Three of the six runners receive medals, and symmetry gives each runner probability 3/6=1/23/6=1/2.

Change one feature: Ada must now receive a particular medal. Fixing a position removes the factor of three; it does not remove a runner from the total sample space.

Worked example 2: one specified place

Question. In the same random assignment, find the probability that Ada receives gold.

Plan. Keep the same denominator and count assignments with Ada fixed in the gold position.

N=6P3=120all assignmentsN(Ada receives gold)=5P2=20fill silver and bronzeP(Ada receives gold)=20120=16divide the counts\begin{aligned} N&={}^6P_3=120 &&\text{all assignments} \\ N(\text{Ada receives gold})&={}^5P_2=20 &&\text{fill silver and bronze} \\ \mathrm{P}(\text{Ada receives gold})&=\frac{20}{120}=\frac16 &&\text{divide the counts} \end{aligned}

Why this step? Silver and bronze still have different roles, so choosing two remaining runners is insufficient: their order matters.

Answer. 16\frac16

Check. There are six equally likely possible gold medallists.

The denominator describes the random experiment before the event is imposed. Restrict the numerator to the event, then divide.

Watch out

Wrong: P(Ada receives gold)=1/6P3\mathrm{P}(\text{Ada receives gold})=1/{}^6P_3. Fixing the gold medallist does not fix the silver and bronze medallists. There are 5P2{}^5P_2 favourable assignments, not one.

The same count works for ordered jobs, numbered seats or distinct prizes; read the roles before choosing the notation.

Unordered selections and combinations

When you select a group, choosing A then B produces the same group as choosing B then A. Count that group once.

For the three cards above, the six ordered pairs collapse into the three pairs {A,B}\{\mathrm{A},\mathrm{B}\}, {A,C}\{\mathrm{A},\mathrm{C}\} and {B,C}\{\mathrm{B},\mathrm{C}\}. Each pair appeared 2!2! times. A group of rr distinct objects appears r!r! times among the ordered arrangements, which explains the division below.

Combination

A combination is an unordered selection. The notation nCr{}^nC_r, also written nCrnC_r or (nr)\binom nr, counts selections of rr objects from nn distinct objects without replacement. A committee without assigned roles is a combination; a chair and a secretary are an ordered choice.

The division removes duplicate orders of each selected group, rather than changing which objects are available.

Counting unordered selections

For integers n≥0n\geq0 and 0≤r≤n0\leq r\leq n:

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

In the formula booklet.

Two consequences are nC0=nCn=1{}^nC_0={}^nC_n=1 and nCr=nCn−r{}^nC_r={}^nC_{n-r}: selecting a group also determines the group left behind. These consequences are not printed separately in the formula booklet; they follow from the displayed formula.

For a colour or letter question, temporarily label the physical objects. The two Os in a word are two available tiles even though they display the same letter. A uniform selection of tiles makes labelled subsets equally likely; it need not make displayed letter combinations equally likely. For example, choosing two tiles from MOM gives MM in one way and MO in two ways, so their probabilities are 1/31/3 and 2/32/3, not 1/21/2 each.

Worked example 3: exactly two vowels

Question. Four tiles are selected uniformly at random, without replacement, from the seven letter tiles of BALLOON. Find the probability that exactly two selected tiles are vowels.

Plan. Count unordered selections of two of the three vowel tiles and two of the four consonant tiles, then divide by all four-tile selections.

N=7C4=35all tile subsetsN(two vowels)=3C2 4C2=3×6=18choose both groupsP(two vowels)=1835equally likely subsets\begin{aligned} N&={}^7C_4=35 &&\text{all tile subsets} \\ N(\text{two vowels})&={}^3C_2\,{}^4C_2=3\times6=18 &&\text{choose both groups} \\ \mathrm{P}(\text{two vowels})&=\frac{18}{35} &&\text{equally likely subsets} \end{aligned}

Why this step? The vowels are the A tile and two separate O tiles. Selecting AO can happen in two ways, while selecting OO happens in only one way; counting tile subsets handles that weighting automatically.

Answer. 1835\frac{18}{35}

Check. The possible vowel counts are 0,1,2,30,1,2,3, with respectively 1,12,18,41,12,18,4 subsets. Their total is 3535.

Change only “exactly” to “at least”. This adds a second disjoint case, so add its count rather than multiply the case counts.

Worked example 4: at least two vowels

Question. With the same random selection from BALLOON, find the probability that at least two selected tiles are vowels.

Plan. Add the counts for exactly two and exactly three vowels.

N(two vowels)=3C2 4C2=18previous caseN(three vowels)=3C3 4C1=4the only further caseP(at least two vowels)=18+435=2235add disjoint cases\begin{aligned} N(\text{two vowels})&={}^3C_2\,{}^4C_2=18 &&\text{previous case} \\ N(\text{three vowels})&={}^3C_3\,{}^4C_1=4 &&\text{the only further case} \\ \mathrm{P}(\text{at least two vowels})&=\frac{18+4}{35}=\frac{22}{35} &&\text{add disjoint cases} \end{aligned}

Why this step? There are only three vowel tiles, so “at least two” means exactly two or exactly three. Those cases cannot overlap.

Answer. 2235\frac{22}{35}

Check. The complementary cases have 1+12=131+12=13 subsets, giving 1−13/35=22/351-13/35=22/35.

Ordered draws also work: each four-tile subset has exactly 4!4! orders, so using consistent ordered counts multiplies both numerator and denominator by the same factor and leaves the probability unchanged.

Watch out

Wrong: “There are two possible cases, two vowels or three vowels, so each has probability 1/21/2.” Cases need not be equally likely. Here their counts are 1818 and 44, and both are compared with the original total of 3535.

In an exam, one fully correct counting quotient can carry the whole method. Make its numerator show every admissible case.

Repeated objects in a line

A uniform shuffle of six physical tiles gives 6!6! equally likely labelled orders, but repeated letters can make several of those orders look identical.

For AAB, the six labelled orders of A1,A2,B\mathrm{A}_1,\mathrm{A}_2,\mathrm{B} produce only AAB, ABA and BAA. Each displayed order has 2!2! labelled versions. The number of displayed orders is therefore 3!/2!=33!/2!=3, and all three are equally likely under a uniform shuffle.

Arrangements with repetitions

If nn objects have kk types with multiplicities a1,…,aka_1,\ldots,a_k, where a1+⋯+ak=na_1+\cdots+a_k=n, their distinct arrangements in a line number

n!a1!a2!⋯ak!\frac{n!}{a_1!a_2!\cdots a_k!}

Under a uniform random permutation of the physical objects, every displayed arrangement has exactly a1!⋯ak!a_1!\cdots a_k! labelled versions and is equally likely.
Not in the formula booklet: learn it.

This constant number of labelled versions is why counting displayed arrangements works. It is different from the tile selections in the previous part: selected letter multisets can have different numbers of labelled versions. A single specified displayed word has probability the reciprocal of the displayed-arrangement count, provided the shuffle is uniform.

Worked example 5: a specified first letter

Question. The six tiles of PEPPER are shuffled uniformly at random and placed in a line. Find the probability that the first letter is P.

Plan. Divide the number of arrangements beginning with P by the total number of distinct displayed arrangements.

N=6!3!2!=60three Ps and two EsN(first P)=5!2!2!=30two Ps remainP(first P)=3060=12divide the counts\begin{aligned} N&=\frac{6!}{3!2!}=60 &&\text{three Ps and two Es} \\ N(\text{first P})&=\frac{5!}{2!2!}=30 &&\text{two Ps remain} \\ \mathrm{P}(\text{first P})&=\frac{30}{60}=\frac12 &&\text{divide the counts} \end{aligned}

Why this step? Fixing one P leaves two identical Ps, two identical Es and one R. The factorials in the numerator must describe those remaining letters.

Answer. 12\frac12

Check. Three of the six physical tiles are Ps, so the first tile is P with probability 3/6=1/23/6=1/2.

Change one feature: the fixed prefix now has two letters. The original sample space stays the same, but fewer Ps remain to be arranged.

Worked example 6: a specified two-letter prefix

Question. In the same random shuffle of PEPPER, find the probability that the first two letters are PP.

Plan. Fix PP, count arrangements of the four remaining tiles, and divide by 6060.

N(first PP)=4!1!2!=12one P, two Es, one RP(first PP)=1260=15same sample space\begin{aligned} N(\text{first PP})&=\frac{4!}{1!2!}=12 &&\text{one P, two Es, one R} \\ \mathrm{P}(\text{first PP})&=\frac{12}{60}=\frac15 &&\text{same sample space} \end{aligned}

Why this step? The two fixed Ps do not have an extra 2!2! order: exchanging identical Ps creates no new displayed arrangement.

Answer. 15\frac15

Check. Sequential drawing gives (3/6)(2/5)=1/5(3/6)(2/5)=1/5.

Continue this lesson.

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

Create free account