Permutations and Combinations

A combination of a given number of articles is a set or group of articles selected from those given where the order of the articles in the set or group is not taken into account.

A permutation of a given number of articles is a set or group of articles selected from those given where the order of the articles in the set or group is taken into account.

At that point we looked at straightforward questions and often used the formulae to calculate the number of permutations or combinations. We will now look at some more complicated examples where the formulae do not work directly.

Permutations

Example 1

How many arrangements can be made of three letters chosen from the word PLANTER if the first letter is a vowel and each arrangement contains three different letters?

Solution

We split this into two separate calculations.

Assume we begin with the letter A. Hence the other two letters can be chosen in .

If we begin with the letter E, then the other two letters can also be chosen in 30 ways.

Since these are the only two possibilities for beginning with a vowel, there are possible permutations.

Example 2

How many three-digit numbers can be made from the set of integers if

a) the three digits are all different

b) the three digits are all the same

c) the number is greater than 600

d) the number is even and each digit can only be used once?

Solution

a) The first digit can be chosen in nine ways.

The second digit can be chosen in eight ways.

The third digit can be chosen in seven ways.

Total number of three-digit numbers that are all different

b) If the three digits are all the same then there are nine possible three-digit numbers, since the only possibilities are 111, 222, 333, 444, 555, 666, 777, 888 and 999.

c) If the number is greater than 600 then there are only four choices for the first digit: 6, 7, 8 or 9.

The second and third digits can each be chosen in nine ways.

Total number of three-digit numbers

d) In this case we start with the last digit as this is the one with the restriction.

The last digit can be chosen in four ways.

The other two digits can be chosen in eight ways and seven ways respectively.

Total number of three-digit numbers that are all different

Example 3

In how many ways can six people be sat around a circular dining table?

Solution

At first this appears to be a simple permutation, where the answer is 6! However, if we look at the two situations below, where the chairs are labelled from 1 to 6 and the people from A to F, we can see that they appear as different permutations, but are actually the same.

Because of the actual situation, every person has the same people on either side in both cases. If the chairs had been distinguishable, then this would no longer be the case.

Hence for every permutation of people sat around the table, there are five more permutations which are the same and hence the answer is six times too big. These are shown in the diagram below.

Therefore the number of ways that six people can be sat around a circular dining table is

NOTE!For any situation like this the answer can be generalised to

Example 4

Jenny is making a necklace. In how many ways can 4 beads chosen from 12 beads be threaded on a string?

Solution

This is similar to the example above. As with the example above the answer needs to be divided by 4 because of the repetitions caused by the fact that it is on a circle. However in this situation there is another constraint because the necklace can be turned over giving an equivalent answer. In the diagrams below, these two situations are actually the same, but appear as two separate permutations of the answer.

Hence we need to divide the answer by 2.

Therefore the number of permutations is .

Example 5

a) Find the number of arrangements of the letters of the word LITTER.

b) Find the number of arrangements where the T’s are together.

c) Find the number of arrangements where the T’s are separated.

Solution

a) In this question we treat it as a simple permutation and hence the answer would appear to be 6! However, the two T’s are indistinguishable and hence and are actually the same arrangement but appear as two separate permutations. As this happens in every single case the number of arrangements is .

b) With the T’s together we treat the two T’s as one letter. If we give TT the symbol , then we are finding the permutations of , which are arrangements.

c) For the T’s separated, we remove the T’s initially and find the number of permutations of LIER which is 4!

If we now consider the specific permutation REIL, then the two T’s can be placed in two of five positions. This is shown in the diagram below.

Hence for the permutation REIL there are ways of positioning the T’s. As this can happen with each of the 4! permutations of the four letters, then the total number of permutations is arrangements.

We could also think about this another way. As we know the total number of arrangements is 360 and the T’s either have to be together or separated then the number of arrangements where they are separated is 360 minus the number of arrangements where they are together.

This gives arrangements.

Example 6

Find the number of arrangements of the letters in the word REFERENCE where the E’s are separated.

Solution

We begin by considering RFRNC. The number of arrangements of these letters is since the two R’s are indistinguishable.

Again considering one possible arrangement of the letters, say RFNRC, the positions that the three E’s can take are shown below.

We need to find the number of combinations of four from six positions, which is

Hence the number of arrangements where the E’s are separated is

Combinations

Example 1

A team of 4 children is to be selected from a class of 20 children, to compete in a quiz game. In how many ways can the team be chosen if

a) any four can be chosen

b) the four chosen must include the oldest in the class?

Solution

a) This is a straightforward combination with an answer of

b) In this situation we remove the oldest in the class since this child has to be part of every group. Hence the problem is actually to find how many teams of 3 children can be found from 19. Therefore the number of teams is

Example 2

Ten students in a class are divided into two groups of five to play in a five-a-side soccer tournament. In how many ways can the two teams of five be selected?

Solution

This appears to be very similar to the example above, but there is a subtle difference. The number of ways of selecting a team of five is Let us imagine that the chosen team is ABCDE. Hence the other team would automatically be FGHIJ. However another possible combination of a team of

five would be FGHIJ and this would then automatically select the other team as ABCDE. In other words the calculation picks each pair of teams twice. Hence the actual number of teams is

Example 3

Anisa goes into her local supermarket and finds that there are 20 different types of chocolate on offer and 15 different types of soft drink. She wants to buy seven different bars of chocolate and four different cans of soft drink for herself and her friends. Find the number of different ways in which she can do this.

Solution

The number of ways she can choose seven bars of chocolate is

The number of ways she can choose four cans of soft drink is

Since with any particular combination of chocolate bars she can put all the particular combinations of cans of soft drink, the total number of choices is 77 520 1365 = 105 814 800.

Example 4

A box contains four red, two blue, one yellow and one pink ball. How many different selections of three balls may be made?

Solution

All three the same: The only possibility here is three red balls and hence there is only one way of doing this.

Two the same, one different: There are two possibilities for two the same, red and blue. The third ball can then be chosen from any of the others, so there are three possibilities because we cannot choose the same colour again. Therefore the total number of ways is

All three different: Since there are four different colours of ball this is

Hence the number of different selections that can be made is

NOTE!Unlike the previous example, we added the combinations here as opposed to multiplying them.

EXERCISES

Exercises (using permutations and combinations)

1. In how many ways can six different files be arranged in a row on a desk?

2. In how many ways can two boys and two girls be chosen from a group of 15 boys and 18 girls?

3. In how many ways can four different letters be put in four different envelopes?

4. In how many ways can three different coats be arranged on five hooks in a row?

5. Giulia has ten different mathematics books and four different chemistry books. In how many ways can she arrange seven of the mathematics books and one chemistry book on a shelf if the chemistry book must always be at one end?

6. In how many ways can the letters of the word PHOTOGRAPH be arranged?

7. Two sets of books contain seven different novels and four different autobiographies. In how many ways can the books be arranged on a shelf if the novels and the autobiographies are not mixed up?

8. In how many ways can ten different examinations be arranged so that the two mathematics examinations are not consecutive and the two French examinations are not consecutive?

9. Given that each digit can be used more than once, how many two-digit numbers can be made from the set if

a) any two digits can be used

b) the two digits must be the same

c) the number must be odd

d )the number must be greater than 60?

10. A quiz team of five students is to be chosen from nine students. The two oldest students cannot both be chosen. In how many ways can the quiz team be chosen?

11. Consider the letters of the word DIFFICULT.

a) How many different arrangements of the letters can be found?

b) How many of these arrangements have the two I’s together and the two F’s together?

c) How many of the arrangements begin and end with the letter F?

12. Margaret wants to put eight new plants in her garden. They are all different.

a) She first of all decides to plant them in a row. In how many ways can she do this?

b) She then decides that they would look better in a circle. In how many ways can she do this?

c) She now realizes that two of the plants are identical. How many arrangements are there for planting them in a row and for planting them in a circle?

13. a) How many different arrangements of the word ARRANGEMENT can be made?

b) How many arrangements are there which start with a consonant and end with a vowel?

14. Jim is having a dinner party for four couples.

a) In how many ways can the eight people be seated at Jim’s circular dining table?

b) John and Robin are a couple, but do not want to sit next to each other at the dinner party. In how many ways can the eight people now be seated?

c) Jim decides that the two oldest guests should sit next to each other. In how many ways can the eight people now be seated?

15. a) How many numbers greater than 300 can be made from the set if each integer can be used only once?

b) How many of these numbers are even?

16. a) A local telephone number has seven digits and cannot start with zero. How many local numbers are there?

b) The telephone company realizes that they do not have enough numbers. It decides to add an eighth digit to each number, but insists that all the eight-digit numbers start with an odd number and end with an even number. The number still cannot start with a zero. Does this increase or decrease the number of possible telephone numbers and if so by how many?

17. a) How many different arrangements are there of the letters of the word INQUISITION?

b) How many arrangements are there where the four I’s are separate?

c) How many arrangements are there where the S and the T are together?

18. Five different letters are written and five different envelopes are addressed. In how many ways can at least one letter be placed in the wrong envelope?

19. On an examination paper of 20 questions a student obtained either 6 or 7 marks for each question. If his total mark is 126, in how many different ways could he have obtained this total?

20. Four boxes each contain six identical coloured counters. In the first box the counters are red, in the second box the counters are orange, in the third box the counters are green and in the fourth box the counters are purple. In how many ways can four counters be arranged in a row if

a) they are all the same

b) three are the same and one is different

c) they are all different

d) there is no restriction on the colours of the counters?

21. a) In how many ways can six different coloured beads be arranged on a ring?

b) If two beads are the same colour, how many ways are there now?

22. a) How many different combinations of six numbers can be chosen from the digits 1, 2, 3, 4, 5, 6, 7, 8 if each digit is only chosen once?

b) In how many ways can the digits be divided into a group of six digits and a group of two digits?

c) In how many ways can the digits be divided into two groups of four digits?

23. A shop stocks ten different types of shampoo. In how many ways can a shopper buy three types of shampoo if

a) each bottle is a different type

b) two bottles are the same type and the third is different?

24. A mixed team of 10 players is chosen from a class of 25 students. 15 students are boys and 10 students are girls. In how many ways can this be done if the team has five boys and five girls?

25. Find the number of ways in which ten people playing five-a-side football can be divided into two teams of five if Alex and Bjorn must be in different teams.

26. A tennis team of four is chosen from seven married couples to represent a club at a match. If the team must consist of two men and two women and a husband and wife cannot both be in the team, in how many ways can the team be formed?

27. Nick goes to the shop to buy seven different packets of snacks and four bottles of drink. At the shop he find he has to choose from 15 different packets of snacks and 12 different bottles of drink. In how many different ways can he make his selection?

28. In how many ways can three letters from the word BOOKS be arranged in a row if at least one of the letters is O?