FP2 5.7 - Permutations and combinations

FP2 5.7 - Permutations and combinations

Distinguish ordered selections from unordered selections, use permutations and combinations, and combine them with restrictions and case counts. Explain why each arrangement is counted once, especially when a code's characters can move between positions.

Ask whether swapping two selected objects creates a new outcome

Does selecting eleven players from a squad of twenty-one give the same count as assigning players to eleven distinct positions? The same eleven people can fill those positions in 39 916 80039\,916\,800 ways. That is almost forty million line-ups before changing a single player! Assume every player is eligible for every position; we will calculate both counts and explain the enormous difference.

You already know

Use the multiplication principle for successive choices, and add disjoint cases. From A-level Mathematics binomial expansions, n!n! is a factorial, 0!=10!=1, and nCr=n!/[r!(n−r)!]{}^nC_r=n!/[r!(n-r)!] is a binomial coefficient. Here we interpret those coefficients as counts of unordered selections.

Choosing A,BA,B as a two-person team is the same outcome as choosing B,AB,A. Assigning AA as captain and BB as deputy differs from reversing their roles. The objects are the same; what matters is whether the roles or positions distinguish outcomes.

Permutations and combinations

A permutation is an ordered selection of distinct objects. A combination is an unordered selection of distinct objects.

The notation nPr{}^nP_r counts ordered selections of rr objects from nn, without repetition. The notation nCr{}^nC_r counts selections of rr objects without repetition when order does not matter.

[DIAGRAM: asset_name: Three teams and six ordered allocations; asset_slug: 9fm0-fp286-ordered-unordered; caption: Each two-person team gives two different allocations to named roles; description: Three rows show unordered teams {A,B}, {A,C}, {B,C} on the left. Each row has two arrows to ordered captain-deputy pairs on the right: (A,B) and (B,A); (A,C) and (C,A); (B,C) and (C,B). Headings say unordered team and ordered named roles. A note states three teams times two orders equals six allocations. All labels are dark ink and arrows clear.]
Each two-person team gives two different allocations to named roles

The permutation and combination meanings are not separately stated in the formula booklet; the coefficient formula is printed, as noted below. Decide what an outcome means before choosing the button on a calculator.

Key idea

Swap two selected objects. If the outcome changes, order matters; if it stays the same, the selection is unordered.

Apply that test to two descriptions of the same people.

Count permutations by filling distinct positions

Fill the first position in nn ways, the next in n−1n-1, and continue until rr positions are filled. Each selected object is unavailable for later positions because repetition is forbidden.

Permutations without repetition

For integers 0≤r≤n0\le r\le n,

nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}

For r≥1r\ge1, this is the product n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1). In particular, arranging all nn distinct objects gives n!n!, and nP0=1{}^nP_0=1.

Not in the formula booklet: learn it.

The last factor is n−r+1n-r+1, not n−rn-r: there must be exactly rr factors. If repetition is allowed instead, each of rr positions has nn choices, giving nrn^r, the multiplication principle rather than nPr{}^nP_r.

Worked example 1: three named roles

Question. Six students are eligible for chair, secretary and treasurer. No student may hold two roles. Find the number of allocations.

Plan. Fill the three distinct roles successively, removing each selected student.

6P3=6×5×4three positions, no repetition=120multiply the choices\begin{aligned} {}^6P_3&=6\times5\times4 && \text{three positions, no repetition}\\ &=120 && \text{multiply the choices} \end{aligned}

Why this step? Selecting the same three people for different roles changes the allocation, so do not divide by their internal orders.

Answer. 120120 allocations.

Check. The factorial form gives 6!/(6−3)!=720/6=1206!/(6-3)!=720/6=120.

Keep the same six students; change only the number of distinct roles from three to four.

Worked example 2: one more distinct role

Question. Add a fourth role, events organiser. How many allocations are possible if all four role holders differ?

Plan. Add one more stage to the ordered selection.

6P4=6×5×4×3four successive choices=360each previous allocation has three continuations\begin{aligned} {}^6P_4&=6\times5\times4\times3 && \text{four successive choices}\\ &=360 && \text{each previous allocation has three continuations} \end{aligned}

Why this step? Four people have four different jobs. The final factor is three choices for the fourth job, not two choices for an unfilled fifth job.

Answer. 360360.

Check. 6!/2!=720/2=3606!/2!=720/2=360, and the count is 33 times the earlier 120120.

When an ordinary integer must have a non-zero leading digit, treat that first position separately. For a code, a zero character may be entirely valid; the problem's definition decides.

Watch out

Wrong: use 646^4 while prohibiting repeated people. Right: the choices decrease after each selection, giving 6×5×4×36\times5\times4\times3.

Keep four roles and enlarge the eligible group by one.

Remove the orders that do not create new teams

An ordered selection of rr distinct people counts each unordered team r!r! times: once for every way to order that team's members. Divide by this common multiplicity. The division is justified because every team has exactly the same number of internal orders.

Combinations

For integers 0≤r≤n0\le r\le n,

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

This counts unordered selections of rr distinct objects from nn.

In the formula booklet.

The interpretation above gives nPr=nCr r!{}^nP_r={}^nC_r\,r!: choose the team, then assign its members to the distinct roles. This counting relationship is derived here, rather than printed as a separate result. There is one empty selection and one selection of the full set, so nC0=nCn=1{}^nC_0={}^nC_n=1, consistent with 0!=10!=1.

Worked example 3: the squad without positions

Question. Select a team of eleven from a squad of twenty-one. Ignoring positions, how many teams are possible?

Plan. Count unordered selections; each set of eleven players is one team.

21C11=21!11!10!divide out internal orders=352 716evaluate the coefficient\begin{aligned} {}^{21}C_{11}&=\frac{21!}{11!10!} && \text{divide out internal orders}\\ &=352\,716 && \text{evaluate the coefficient} \end{aligned}

Why this step? Listing a team's players in a different order does not create a different team. The divisor is 11!11!, not 1111.

Answer. 352 716352\,716 teams.

Check. Choosing the ten omitted players also identifies the team uniquely, giving 21C10=352 716{}^{21}C_{10}=352\,716.

Keep the squad and selected team size fixed; change only whether the eleven positions are distinct.

Worked example 4: the squad with named positions

Question. Each of eleven positions must be filled by a different player from the squad of twenty-one. Every player is eligible for every position. How many line-ups are possible?

Plan. Choose an unordered team, then assign its eleven players to the eleven distinct positions.

line-ups=21C11×11!team, then all its internal orders=352 716×39 916 800evaluate each factor=14 079 294 028 800multiply\begin{aligned} \text{line-ups}&={}^{21}C_{11}\times11! && \text{team, then all its internal orders}\\ &=352\,716\times39\,916\,800 && \text{evaluate each factor}\\ &=14\,079\,294\,028\,800 && \text{multiply} \end{aligned}

Why this step? Positions make each of the 11!11! internal orders a different outcome; dividing them out would lose valid line-ups.

Answer. 14 079 294 028 80014\,079\,294\,028\,800, equivalently 21P11=21!/10!{}^{21}P_{11}=21!/10!.

Check. Filling positions directly gives 21×20×⋯×11=21!/10!21\times20\times\cdots\times11=21!/10!, the same count. Their ratio to the team count is 11!=39 916 80011!=39\,916\,800.

The opening distinction is now resolved. A restriction on who may fill which role would change the available choices, so the eligibility assumption matters.

Watch out

Wrong: divide the ordered count by 1111 to obtain unordered teams. Right: divide by 11!11!, because each team has 11!11! internal orders. Keep those orders when the positions are distinct.

Name the outcomes in your working so the reason for retaining or removing orders is clear.

Exam tip

State whether order matters before choosing nPr{}^nP_r or nCr{}^nC_r. A calculator value alone does not explain which outcomes you have counted.

Change only the number of selected players.

Fix required or forbidden members before choosing the rest

For an unordered team with required members, put them in first and reduce both the remaining pool and the remaining team size. For forbidden members, remove them from the pool but do not reduce the required team size. These are applications of the combination count, not separate formula-booklet results.

Continue this lesson.

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

Create free account