7.01d–7.01f - Permutations and combinations

7.01d–7.01f - Permutations and combinations

Count outcomes by splitting a choice into stages. You will use factorials for complete arrangements, permutations when order matters and combinations when it does not, and explain exactly why the two latter counts differ.

The multiplicative principle

Eight candidates are available. Is choosing a captain, deputy and secretary the same counting problem as choosing a team of three? Both use three people, but one of the answers will be six times the other.

The foundation is simpler: if a menu offers 44 mains and 33 drinks, each main can be paired with all three drinks. There are 3+3+3+3=4×3=123+3+3+3=4\times3=12 meals, rather than 4+3=74+3=7.

You already know

An enumeration problem asks for a count. Outcomes in different, non-overlapping cases can be added. A set has no order, so listing the same people in a different order does not create a new subset.

Multiplication counts a sequence of decisions. The number of options at each stage may depend on how many choices have already been made, but it must have the stated value for every history that reaches that stage. If it varies between branches, separate those branches first.

Multiplicative principle

If a process has kk stages, with aia_i choices at stage ii for every permitted sequence of preceding choices, its total number of outcomes is

a1a2⋯aka_1a_2\cdots a_k

Not in the formula booklet: learn it.

A small choice tree explains the product: every branch at one stage gives the same number of branches at the next. You need not draw the full tree once the stage counts are clear.

Worked example 1: independent menu choices

Question. A meal consists of one of 44 mains, one of 33 drinks and one of 22 desserts. Find the number of different meals.

Plan. Choose a main, then a drink, then a dessert, and multiply the numbers of options.

main and drink choices=4×3=12three drinks for every maincomplete meals=12×2=24two desserts for every pair\begin{aligned} \text{main and drink choices}&=4\times3=12 &&\text{three drinks for every main}\\ \text{complete meals}&=12\times2=24 &&\text{two desserts for every pair} \end{aligned}

Why this step? Every meal requires all three choices, so multiply across the stages; adding would count isolated menu items rather than meals.

Answer. 2424 meals.

Check. For each of the 44 mains there are 3×2=63\times2=6 completions, giving 4×6=244\times6=24.

The next example changes only whether dessert is compulsory. “No dessert” is one additional choice, not the removal of the final stage.

Worked example 2: an optional stage

Question. The same menu has 44 mains, 33 drinks and 22 desserts. A meal has one main and one drink, but may have either one dessert or no dessert. Find the number of meals.

Plan. Count the dessert stage as three possibilities: either named dessert, or neither.

dessert-stage choices=2+1=3include the option of nonecomplete meals=4×3×3=36multiply the stage counts\begin{aligned} \text{dessert-stage choices}&=2+1=3 &&\text{include the option of none}\\ \text{complete meals}&=4\times3\times3=36 &&\text{multiply the stage counts} \end{aligned}

Why this step? “No dessert” is the same single option for each main-and-drink pair; it is not two different ways of declining the two desserts.

Answer. 3636 meals.

Check. 2424 meals with a dessert plus 4×3=124\times3=12 without one gives 3636.

Addition and multiplication answer different questions.

Watch out

Wrong: 4+3+2=94+3+2=9 meals in the first example. Right: choose a main and a drink and a dessert, giving 4×3×2=244\times3\times2=24. Add only when combining disjoint alternative cases.

Write a short label beside each factor so that the meaning of your product remains visible.

Arranging all distinct objects

When different objects are used once each, every placement reduces the number left for the next placement.

For three books AA, BB, CC, there are 33 choices for the first place, then 22, then 11. The six arrangements are ABCABC, ACBACB, BACBAC, BCABCA, CABCAB, CBACBA. This is the multiplicative principle with shrinking stage counts.

Factorial

For a positive integer nn, nn factorial, written n!n!, is the product of the integers from 11 to nn. Define 0!=10!=1. For example, 4!=4×3×2×1=244!=4\times3\times2\times1=24; factorial does not mean 444^4.

The value 0!=10!=1 fits counting: there is exactly one arrangement of no objects, the empty arrangement. It also makes n!=n(n−1)!n!=n(n-1)! valid at n=1n=1.

Complete arrangements of distinct objects

The number of arrangements in a line of nn distinct objects, each used exactly once, is

n!=∏r=1nrn!=\prod_{r=1}^{n}r

The empty arrangement has count 0!=10!=1.

Not in the formula booklet: learn it.

The factorial increases quickly: only ten different books already have 10!=3 628 80010!=3\,628\,800 possible orders. A short product can represent a very long list.

Worked example 3: six different books

Question. Find the number of orders in which 66 different books can be placed in a line on a shelf.

Plan. Fill the shelf from left to right, using each book once.

orders=6×5×4×3×2×1one fewer book each time=6!=720evaluate the product\begin{aligned} \text{orders}&=6\times5\times4\times3\times2\times1 &&\text{one fewer book each time}\\ &=6!=720 &&\text{evaluate the product} \end{aligned}

Why this step? The books are distinct, so exchanging any two produces a different arrangement.

Answer. 720720 orders.

Check. There are 66 choices for the first book and 5!=1205!=120 orders for the rest: 6×120=7206\times120=720.

The next example adds one book. The new factor is 77, because any one of the seven books can be placed first.

Worked example 4: adding one distinct object

Question. Find the number of orders for 77 different books in a line.

Plan. Count all seven stages, or multiply the previous factorial by 77.

orders=7!all seven books are used=7×6!=7×720=5040factorial recurrence\begin{aligned} \text{orders}&=7! &&\text{all seven books are used}\\ &=7\times6!=7\times720=5040 &&\text{factorial recurrence} \end{aligned}

Why this step? A complete arrangement uses all the books, so the product continues down to 11, rather than stopping after an arbitrary number of positions.

Answer. 50405040 orders.

Check. Insert the new book into any of the 77 gaps before, between or after the 66 books; this also gives 720×7720\times7.

The condition “distinct” will matter when letters or objects repeat.

Watch out

The count n!n! assumes that exchanging two objects changes the arrangement. It cannot be used unchanged for indistinguishable copies, such as the two copies of AA in ABACABAC.

For now, all objects in the count are distinguishable and each is used once.

Permutations: order matters

An ordered selection stops the factorial product after the required number of places has been filled.

Choosing a captain and then a deputy from 55 candidates gives 5×4=205\times4=20 outcomes. The choice (A,B)(A,B) means captain AA, deputy BB; reversing the order changes the appointments.

Continue this lesson.

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

Create free account