Reflection on Senior Mathematics

A SYSTEMATIC APPROACH TO PERMUTATIONS AND COMBINATIONS

Paul Larkin

Introduction

The following approach to solving permutation and combination problems results from the difficulty that my students and I encountered when I first taught it. Deciding how to solve a particular problem involves asking a set of questions. The responses to these questions allow the problem to be placed in a category that indicates the method of solution. This paper contains these questions and categories, with worked examples and some challenging problems that do not fit into any particular category.

Questions and categories

The questions students need to ask are:

1. Once an item has been chosen, is it replaced?

2. Are restrictions placed on how the items are chosen?

3. Is the order in which items are chosen important?

4. If order is important, are the items being arranged in a line or a circle?

For items arranged in a line without restriction, there are these questions:

5. Are all the items being arranged?

6. If all the items are being arranged, is each item unique?

Question 1 reminds us that permutations and combinations are used when items are chosen without replacement. Question 2 breaks problems into two categories, 'without restriction' and 'with restriction'. Questions 3 and 4 give three subcategories: line permutation, circle permutation and combination. Unrestricted line permutations are of three types: all items are arranged and are unique; all items are arranged and some are identical; only some items are arranged. These categories are shown in Figure 1.

Solutions - without restriction

FIGURE 2

Figure 2 shows the types of questions that fall within the category 'without restriction' and the general method of solution. Here are some specific examples:

Line permutation

1. All items, each unique

Q. In how many ways can seven students be arranged in a line?

Order important - line permutation, without restriction.

All 7 items arranged and unique.

No. of arrangements = 7! = 5040.

2. All items, some identical

Q. In how many ways can the letters of the word WOLLONGONG be arranged?

Order important - line permutation, without restriction.

All 10 items arranged.

Some items identical: 3 Os, 2 Ls 2 Ns, 2 Gs.

No. of arrangements

3. Some items

Q. How many different arrangements are there using 3 letters of the word SUNDAY?

Order important - line permutation, without restriction.

No. of items = 6.

No. of items chosen = 3.

No. of arrangements

Circle permutation

Q. In how many ways can six people be arranged in a circle?

Order important - circle permutation, without restriction.

No. of items = 6.

No. of arrangements = (6 - 1)! = 120.

Combinations

Q. How many committees of 4 students can be chosen from 8 students?

Order unimportant - combination.

No. of students = 8.

No. of students chosen = 4.

No. of committees

Solutions - with restriction

Note: These strategies are not rules or formulas. Carefully adapt each strategy to the problem you are solving.

Figure 3 shows the types of problems that occur with restriction and the general approach used to solve each type. Here are three important things to note:

(a) The presence of a restriction is usually but not always indicated by the word 'if'.

(b) A restriction breaks the items into two groups:

• a group of restricted items and a group of unrestricted items (see Q1), or
• two restricted groups of items (see Q2).

(c) With line permutations there are two kinds of restrictions:

• an item's position is restricted in relation to other items (see Q1, Q2);
• a location is restricted to only being occupied by some items (see Q3).

Line permutation

Q1. How many ways can 4 boys and 3 girls be arranged in a line so that all 4 boys are together?

Order important - line permutation, with restriction.

Restricted items - 4 boys, unrestricted items - 3 girls.

Restriction - 4 boys together:

Arr. of 4 boys = 4! = 24.

Arr. of 3 girls = 3! = 6.

Total no. of arr. = 4 x 24 x 6 = 576.

Q2. How many lines of 4 boys and 3 girls are there if boys and girls alternate?

Order important - line permutation, with restriction.

Restricted items - 4 boys, 3 girls.

Restriction - boys and girls alternate: B G B G B G B,

that is, 1 pattern.

Arr. of 4 boys = 4! = 24.

Arr. of 3 girls = 3! = 6.

Total no. of arr. = 1 x 24 x 6 = 144.

Q3. In how many ways can 2 adults and 3 children be arranged in a line if the adults are at either end of the line?

Order important - line permutation, with restriction.

Restricted items - 2 adults, unrestricted items - 3 children.

Restriction - 2 adults at either end of line: A - - - A.

Arr. of 2 adults = 2! = 2.

Arr. of 3 children = 3! = 6.

Total no. of arr. = 2 x 6 = 12.

Circle permutation

Q. In how many ways can 5 friends sit around a table if Bill and Ben do not sit next to each other?

Order important - circle permutation, with restriction.

Restricted items - Bill and Ben, unrestricted items - other 3 friends.

Restriction - Bill and Ben not next to each other,

Choose a location for Bill.

Arrange other four items as line permutation, with restriction.

Arr. of Ben (restricted item) = 1! = 1.

Arr. of 3 friends (unrestricted items) = 3! = 6.

Total no. of arr. = 2 x 1 x 6 = 12.

Combinations

Q. How many committees consisting of 3 teachers and 5 students can be made up if there are 6 teachers and 10 students to choose from?

Order unimportant - combination, with restriction.

Given: 6 teachers and 10 students.

Choose: 3 teachers and 5 students.

Comb. of teachers

Comb. of students

Total no. of committees = 20 x 252 = 5040.

Probability questions

Once students have mastered the different categories, solving probability questions becomes quite simple. Using the result: n(E) is an arrangement or combination with restriction and n(S) is the same arrangement or combination without restriction. For example, refer to earlier examples to solve this question:

Q. 4 boys and 3 girls are arranged in a line. What is the probability that boys and girls alternate.

n(E) = 576 [See Q2, line perm., with restriction.]

n(S) = 5040 [See Q, line perm., without restriction.]

in item 1 on p.94.

Exceptions

There are some more challenging questions that do not fall into any of the categories given in Figure 1. In fact the gaps in Figure 1 suggest the types of questions that are not common to textbooks. For example, arranging some items of a word with repeated letters.

Q1.How many arrangements of three letters from the word BANANA are there?

3 possibilities - 3 unique letters, 3 letters with 2 identical, 3 letters all identical.

3 unique letters: 1 possibility - B, N, A:

Arr. = 3 ! = 6.

3 letters with 2 identical: 4 possibilities -

2 As with B or N.

2 Ns with B or A.

Arr.

Total = 4 x 3 = 12.

3 letters, all identical: 1 possibility - 3 As.

Arr.

Total no. of arr. = 6 + 12 + 1 = 19.

These questions are generally solved by considering individual cases. Others require calculation of a combination followed by a permutation. Try this one (from Fitzpatrick, p.194, Q23): How many words (arrangements of letters) containing 3 consonants and 2 vowels can be formed from the letters of the word promise? [Solution: 1440.]

Conclusion

With the exception of the charts, I have used this approach with two 3 Unit classes and it worked very well (much better than my first attempts). I first introduce them to the concepts of permutations and combinations (using a story about a hairdresser whose salon only offers perms and combs). We then look at the different categories, followed by an exercise where students provide the categories to which each question belongs. We next do problems in the same order as given in this paper. (Students are also shown the alternative methods of solution that exist for some types of questions.) This is followed by more theoretical aspects of the topic, which then leads into the binomial theorem. Strategies that help students with permutations and combinations include:

• using colours to distinguish the various sections of a solution;

• using students to model permutations and combinations;

• getting students to visualize the situation being described in the question;

• having printed lists of all possible arrangements of a word like SUNDAY to show that the large numbers are true;

• buying students a triple ice cream while they calculate how many hundreds of centuries it would take to produce all possible arrangements of 16 flavours if a new arrangement of tubs is set up each day.

The process of categorizing permutation and combination problems provides a methodical approach that helps both understanding and memory. Giving each category a label also helps some students. Overall, students definitely benefit from being able to approach questions systematically rather than haphazardly.