5.2 - Permutations and combinations

5.2 - Permutations and combinations

Choosing three people and giving those people three different jobs produce different counts. In this first part of 5.2, you will decide when order matters, count ordered and unordered selections, and combine simple restrictions without counting the same outcome twice.

Ordered selections

Seven people volunteer for captain, deputy and secretary. Is choosing a group of three enough to describe the result? No: the same three people can take the jobs in different ways. The roles make the order matter.

Start smaller. From Ada, Ben and Cara, choosing a captain and deputy gives AB, AC, BA, BC, CA and CB. AB and BA are different: Ada holds a different job. There are three choices for captain, then two remaining choices for deputy, giving 3×2=63\times2=6.

Permutation and combination

A permutation is an ordered selection or arrangement: changing the order can change the outcome. A combination is a selection in which order does not matter. A captain and deputy form an ordered selection; a two-person committee without roles forms an unordered selection.

For distinct objects chosen without replacement, each choice reduces the next number of available objects by one. Arranging all five distinct objects gives 5×4×3×2×1=5!5\times4\times3\times2\times1=5!. The exclamation mark denotes a factorial.

Ordered selections without replacement

For integers 0≤r≤n0\le r\le n, the number of ways to fill rr distinct ordered positions from nn distinct objects, with no object used twice, is

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

Here n!=n(n−1)⋯1n!=n(n-1)\cdots1 for positive integers nn, and 0!=10!=1. Thus arranging all nn distinct objects gives n!n!.
Not in the formula booklet: learn the counting reasoning.

Writing the available choices beside the actual positions often makes the method clearer than starting with a calculator button.

Worked example 1: three different roles

Question. Seven people volunteer. Find the number of ways to appoint a captain, deputy and secretary, with nobody holding more than one role.

Plan. Fill the named roles one at a time, removing each appointed person from later choices.

7×6×5=210.7\times6\times5=210.

There are seven possible captains, six remaining deputies for each captain, and five remaining secretaries for each pair.

Answer. 210210 appointments.

Check. For a fixed captain, listing deputy choices gives six branches, each with five secretary choices: 3030 outcomes. Seven disjoint captain branches give 7(30)=2107(30)=210.

Keep the same volunteers and add just one distinct role. The existing three-role appointments each extend in four ways.

Worked example 2: one additional role

Question. The same seven people must fill captain, deputy, secretary and treasurer. Nobody may hold more than one role. Find the number of appointments.

Plan. Extend the ordered selection to four positions.

7P4=7×6×5×4=840.{}^7P_4=7\times6\times5\times4=840.

The fourth factor is 44, because three people have already been used.

Answer. 840840 appointments.

Check. Each of the 210210 appointments in Example 1 has exactly four possible treasurers, so 210×4=840210\times4=840.

If repetition is allowed, the available choices need not decrease: a three-digit code using digits 00 to 99 has 10310^3 possibilities if leading zero is permitted. That is a different experiment from appointing distinct people without replacement.

Watch out

Do not use 737^3 for three different people taking three roles. It permits the same person to occupy several roles. Write the restrictions before choosing the factors.

Extend the role count with a fresh group size.

Unordered selections

A committee has no captain, deputy or secretary. The selection Ada, Ben, Cara is the same committee as Cara, Ada, Ben. Counting ordered selections would count this one group 3!=63!=6 times.

Each group of rr distinct people appears in exactly r!r! orders. Divide the ordered count by that repeated count to obtain the number of groups.

Combinations

For integers 0≤r≤n0\le r\le n, the number of unordered selections of rr distinct objects from nn is

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

The objects are chosen without replacement. Also (n0)=(nn)=1\binom n0=\binom nn=1: there is one empty selection and one selection of everything.
In the formula booklet, in the binomial-series section.

This is the same coefficient used in a binomial expansion. A term containing rr choices of one part arises from choosing which rr of the nn brackets supply it.

Worked example 3: a committee without roles

Question. Find the number of three-person committees that can be selected from seven people.

Plan. Count ordered triples and divide by the six orders of each committee.

(73)=7×6×53×2×1=35.\binom73=\frac{7\times6\times5}{3\times2\times1}=35.

Dividing by 3!3! removes order; it does not remove any people.

Answer. 3535 committees.

Check. Giving the three selected people captain, deputy and secretary roles would produce 35×3!=21035\times3!=210 appointments, agreeing with Example 1.

Change only the committee size from three to four. The people left out now provide a second way to check the count.

Continue this lesson.

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

Create free account