EN4 - Permutations (ordered selections)

EN4 - Permutations (ordered selections)

An ordered selection records both which objects are chosen and where they go. You will count permutations of distinct objects, derive the notation nPr{}^nP_r and handle restrictions on roles, positions and neighbouring objects. The starting question is always what makes two outcomes different.

When order changes the outcome

Ten finalists compete for a gold and a silver medal. Is the number of possible medal results the same as the number of possible pairs of medallists? Imagine that Amira wins gold and Ben wins silver. Swap their medals: the pair of people is unchanged, but the result certainly is not. By the end, you will count the medal results exactly.

For a smaller example, award two different roles to three people, A,B,CA, B, C, with nobody holding both roles. The outcomes are AB,AC,BA,BC,CA,CBAB, AC, BA, BC, CA, CB, where the first letter holds the first role. The names alone do not describe the outcome: the positions matter.

You already know

The product rule multiplies stage counts. A row containing all nn distinct objects has n!n! arrangements. If only some objects are used, stop multiplying once every required position is filled.

The word “ordered” includes named jobs and prizes. It does not mean you must physically arrange the objects from left to right: chair and secretary are distinguished positions too.

Permutation

A permutation of rr objects from nn distinct objects is an ordered selection without repetition. For example, choosing a first-prize winner and a different second-prize winner gives permutations. Choosing two representatives with identical roles is an unordered selection, so it is not counted in the same way.

Repeating an object is a different rule. A digit code allowing repeated digits is counted using the product rule with unchanged stage counts, rather than the distinct-object permutation formula.

Key idea

Ask whether swapping the same chosen objects changes the recorded outcome. If it does, order matters.

Use that test on four similar-looking choices.

Counting permutations with the factorial quotient

To fill rr distinguished positions from nn distinct objects, use the decreasing factors n,n−1,…n, n-1,\ldots and stop after exactly rr factors.

With 55 people and 22 roles, the count is 5×4=205\times4=20. The product 5!5! goes too far: it also orders the three people who were not given a role. Dividing by 3!3! removes that unnecessary ordering.

Permutations of distinct objects

nPr=n!(n−r)!=n(n−1)⋯(n−r+1){}^nP_r=\frac{n!}{(n-r)!} =n(n-1)\cdots(n-r+1)

Here nn and rr are integers with 0≤r≤n0\le r\le n. Select without repetition into rr distinguished positions. In particular, nP0=1{}^nP_0=1 and nPn=n!{}^nP_n=n!, using 0!=10!=1.
Not on the formulae sheet: learn it.

The factorial quotient is just cancellation: in n!n!, the unwanted factors from n−rn-r down to 11 form (n−r)!(n-r)!. On a calculator, write the mathematical expression as part of your solution rather than only a key sequence.

Worked example 1: two different roles

Question. A club has 88 members. A chair and a secretary are chosen, with different people holding the roles. Find the number of possible allocations.

Plan. Count 88 choices for chair, followed by 77 remaining choices for secretary.

N=8P2two distinguished roles=8!6!n−r=6=8×7=56cancel unused factors\begin{aligned} N&={}^8P_2 && \text{two distinguished roles}\\ &=\frac{8!}{6!} && n-r=6\\ &=8\times7=56 && \text{cancel unused factors} \end{aligned}

Why not 828^2? Once a person is chair, that person is not available for secretary.

Answer. 5656 allocations.

Check. Each possible chair is paired with 77 secretaries; eight groups of seven give 5656.

The next example changes only the number of roles: add a treasurer, still requiring a different person for every role.

Worked example 2: one more role

Question. The same club of 88 members chooses a chair, a secretary and a treasurer. Nobody can hold more than one role. Find the number of possible allocations.

Plan. Continue the decreasing product for a third position.

N=8P3three distinguished roles=8!5!n−r=5=8×7×6=336three factors\begin{aligned} N&={}^8P_3 && \text{three distinguished roles}\\ &=\frac{8!}{5!} && n-r=5\\ &=8\times7\times6=336 && \text{three factors} \end{aligned}

Why is the last factor 66? Two different people already hold roles, leaving 8−2=68-2=6 choices.

Answer. 336336 allocations.

Check. Each of the 5656 chair-secretary allocations from Worked example 1 has 66 possible treasurers: 56×6=33656\times6=336.

The opening medal question now has an answer: 10P2=10×9=90{}^{10}P_2=10\times9=90 gold-and-silver results. Add a bronze medal and the number becomes 10×9×8=72010\times9\times8=720: just one extra medal makes eight times as many results. Every pair of gold-and-silver medallists produces exactly two results, one for each way to allocate the medals. Next lesson, that repeated-count observation will count unordered selections.

Watch out

Wrong: 8P3=8!3!{}^8P_3=\frac{8!}{3!}. The denominator removes the unused positions, not the number selected. Right: 8P3=8!(8−3)!=8!5!{}^8P_3=\frac{8!}{(8-3)!}=\frac{8!}{5!}.

Change the size of the club while keeping the three roles.

Including a specified person in ordered roles

A specified person can have one fixed role or any one of several roles; count that person's possible positions before allocating the others.

Fixing the person and fixing the position are different restrictions. “Riya must win gold” gives one possible position for Riya. “Riya must win a medal” allows gold, silver or bronze. Once her position is chosen, the other positions are filled from the remaining people.

Worked example 3: a specified role

Question. Seven runners compete for gold, silver and bronze, with no ties. Riya must win gold. Find the number of possible medal results.

Plan. Fix Riya in the gold position and allocate silver and bronze to two of the other six runners.

Riya’s positions=1gold is fixedremaining allocations=6P2=6×5two different runnersN=1×30=30combine the stages\begin{aligned} \text{Riya's positions}&=1 && \text{gold is fixed}\\ \text{remaining allocations}&={}^6P_2=6\times5 && \text{two different runners}\\ N&=1\times30=30 && \text{combine the stages} \end{aligned}

Why not choose three runners from the remaining six? Riya has already filled one of the three medal positions.

Answer. 3030 results.

Check. For each silver medallist there are 55 bronze medallists, giving 6×5=306\times5=30.

Continue this lesson.

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

Create free account