Mathematics Extension 1 – Permutations and Combinations

Permutations and Combinations

Definitions

This topic is an introduction to counting methods used in Discrete Mathematics. Permutations and Combinations involve counting the number of different selections possible from a set of objects given certain restrictions and conditions.

We now look to distinguish between permutations and combinations.

Definition: A permutation is a selection where the order in which the objects are selected is important and repetition of objects is not allowed. For example the selection ABC is different to the selection ACB as permutations.

Definition: A combination is a selection where the order in which the objects are selected is not important and repetition of objects is not allowed. For example, the selection ABC is the same as the selection ACB as combinations.

To calculate the number of permutations and combinations we may of course simply list the number the different cases and then simply count the number of different cases. This method becomes tedious though when one is dealing with larger sets of objects. For example, considering the number of combinations of 3 objects selected from a group of 10 distinct objects, this requires 120 different cases which of course will become quite tedious to list. Hence we need to introduce a rigorous and systematic method to solve these counting problems.

The Fundamental Counting Principle

This principle is called so due to its importance to counting theory. In essence, this principle states that;

If there are $Latex formula$ distinct ways to do $Latex formula$, andq distinct ways to do $Latex formula$, then in total there are $Latex formula$ ways to do both $Latex formula$ and $Latex formula$ provided $Latex formula$ and $Latex formula$ are independent.

Simply stated, this states that when considering two events, both mutually exclusive (independent), then the total number of ways to do both events is the number of ways to do the first, multiplied by the number of ways to do the second. This principle may also be extended to several differing events as well. Consider the example below.

Example 1

If there are 3 ways to travel to Kuala Lumpur from Sydney, and 4 ways to travel from Kuala Lumpur to Tokyo, in how many ways can I travel from Sydney to Tokyo, via. Kuala Lumpur?

Solution 1

This is a simple case of the fundamental counting principle. Consider the below diagram (Not that this is not necessary for your answer but is of great assistance).

So, by the fundamental counting principle, the number of ways to travel to Tokyo from Sydney via. Kuala Lumpur is given by

No. of ways $Latex formula$

The next example shows a problem where the cases being considered are not independent, however the fundamental counting principle may be applied.

Example 2

In how many ways can you arrange 3 distinct books on a shelf?

Solution 2

In this question we use the fundamental counting principle again. Our argument is displayed in the diagram below.

There are 3 ways to place one of those books in the first position, since there are 3 possible books to choose from. Once a book has been removed, there are then 2 way to place a book in the second position, since there are then 2 books remaining to choose from. Once the second book has been removed, then there is 1 book remaining and hence 1 way to place a book in that last position. Hence the number of ways to arrange these three books on the shelf is given by;

No. of ways $Latex formula$

Permutations and the Factorial Notation

The product of all the positive integers less than or equal to a number, $Latex formula$ say, is denoted by $Latex formula$ and is read “ $Latex formula$ factorial”. That is,

 $Latex formula$

So as simple examples we have,

$Latex formula$

$Latex formula$

$Latex formula$ where $Latex formula$

By definition, we have that;

$Latex formula$

The factorial function $Latex formula$, has domain equal to the non-negative integers. (Although in higher undergraduate mathematics there turns out to be a way to consider the factorial function for negative integers and fractional values). This notation is particularly handy when considering arrangements in lines or circles. Consider the example below.

Example 3

In how many ways may 6 girls sit in a row?

Solution 3

In this case we may go through a similar argument to that in example 2, and find out that the answer is equal to;

No. of ways $Latex formula$

However, this is equal to;

$Latex formula$

In general when arranging $Latex formula$ distinct objects in a row (repetitions not allowed) we have that the number of arrangements or permutations of those $Latex formula$ objects are given by $Latex formula$. Now, if we were to have $Latex formula$ objects, not all distinct, then this is a different matter, and in fact there does exist a formula for such a case. The formula is given below.

If there are $Latex formula$ objects, with $Latex formula$ objects being non-distinct and of a certain type and $Latex formula$ objects being non-distinct and of another type and $Latex formula$ objects being non-distinct and of another type and so on, we have that the number of arrangements of such objects in a row is given by,

$Latex formula$

Although this may not be immediately obvious, the reason for the division by the values of $Latex formula$ and $Latex formula$ is simply to eliminate all the rearrangements of the similar objects between themselves. Consider the example below that illustrates the use of this formula.

Example 4

In how many ways may the letters of the word MAMMAL be rearranged?

Solution 4

In this example, we note that there are $Latex formula$ M’s and that there are $Latex formula$ A’s, and that in total we have $Latex formula$ letters. Using the above formula we have that the number of arrangements of the letters is given by,

$Latex formula$

Suppose now that we wish to arrange objects in a circle. The difference between this and the above case is the lack of a defined starting point and a defined ending point. Because of this we must assign one of the objects being arranged, to be our reference point and it is then that we may arrange the remaining objects about the object chosen to be the reference point. Hence upon removing an object (to place as a reference point) from the total objects to be arranged, we end up with one less object and then these objects must be arranged in the same way as was considered in example 2. Hence we have that;

If there are $Latex formula$ objects, all distinct, then the total number of ways in which these objects may be arranged about a circle is given by $Latex formula$.

Example 5

In how many ways may 5 married couples be arranged about a circular table?

Solution 5

Since there are 5 married couples, it follows that there are $Latex formula$ people to arrange. Thus the total number of arrangements is given by,

$Latex formula$

Suppose now that we have $Latex formula$ objects among those $Latex formula$ being similar and another $Latex formula$ being similar and so on. The number of arrangements about a circle is now given by the total number of arrangements divided by the arrangements of the similar objects themselves. Hence we have that;

If there are $Latex formula$ objects with $Latex formula$ similar and another $Latex formula$ similar and another $Latex formula$ similar etc. it follows that the total number of arrangements of those objects in a circle is given by

$Latex formula$

We now consider the arrangements of objects on a necklace, or a keychain. Suppose that we such to arrange $Latex formula$ distinct beads on a necklace. The total number of arrangements is given by the total number of unrestricted arrangements in a circle divided by $Latex formula$. The division by $Latex formula$ is due to the symmetry of the necklace by being able to turn the necklace around and observe the exact same permutation. Hence we have that;

Given $Latex formula$ objects, each distinct, the number of arrangements of these objects on a necklace is given by,

$Latex formula$

We have so far considered arrangements in rows and circles, given similarity between some of the objects. We shall now consider the number of arrangements of objects given certain conditions. Recall that a permutation of an object is simply an ordered selection or an arrangement. We thus have that,

The number of permutations of $Latex formula$ objects choosing $Latex formula$ at a time is given by;

$Latex formula$

Notice that for $Latex formula$ the formula becomes,

$Latex formula$

Thus, if one is choosing all the objects in the set then the total number of permutations is simply the same as arranging all the objects into a line which should at this point be quite obvious. Also, this formula assumes that no repetitions are allowed. Let us consider an example to illustrate this formula’s use.

Example 6

Find the number of $Latex formula$ letter arrangements of the letters of the word COMPLEX.

Solution 6

Since every letter is distinct, it thus follows that the total number of such arrangements is given by

$Latex formula$

Note that this is exactly the same as using the fundamental counting principle here the number of ways is given by $Latex formula$.

We are now going to consider some examples of questions that involve permutations given certain conditions. Students tend to have difficulty in grasping the techniques involved, since every question must be tackled on its own merits. The best way to master such questions is to expose oneself to as many examples as possible.

Example 7

In horse racing, a trifecta is name given to selecting the first three greyhounds in a race in the correct order. In how many ways can this be done if there are 8 horses?

Solution 7

In this question we are choosing a group of $Latex formula$ with order important from a set of $Latex formula$. Using the formula for permutations gives,

$Latex formula$

Example 8

In how many ways can 5 girls and 3 boys be arranged in a row if:
a) the $Latex formula$ boys must sit next to each other?

b) the $Latex formula$ boys must not sit next to each other?

Solution 8

a) If the $Latex formula$ boys must sit next to each other, then we may treat the $Latex formula$ boys as one unit. Thus using this technique we have a total of $Latex formula$ objects to permute in a line which has a total number of permutations equal to $Latex formula$. Now, the boys themselves may be arranged about themselves within their unit, and this can be done in $Latex formula$ ways. Thus by the fundamental counting principle, the total number of ways to arrange them in this fashion is,

$Latex formula$

b) Now, if the boys are NOT to sit next to each other, then we can simply consider the complementary event.

Let $Latex formula$ represent the boys sitting next to each other, and $Latex formula$ represent the boys not sitting next to each other.
Let $Latex formula$ represent the number of ways $Latex formula$ may occur.

Hence we have

$Latex formula$

Where $Latex formula$ is the complementary event. Thus we have that

$Latex formula$

That is, the number of ways in which the boys do NOT sit next to each other is $Latex formula$.

Note: Do not fall into the common trap of listing cases and then counting the possible arrangements in each case. This is futile and tedious. If possible always look to the complementary event first.

Example 9

In how many ways can the letters of the word MEETING be arranged if vowels and consonants occupy alternate places?

Solution 9

Since there are 3 vowels and 4 consonants, then it follows that all arrangements have the form

where C represents a consonant and V represents a vowel.

Now, the vowels themselves may be arranged in their own possible positions in a total of $Latex formula$ ways owing to the fact that there exists two A’s and thus in this case we need to divide amongst the arrangements of the A’s themselves. The consonants may be arranged amongst themselves in their allocated positions in a total of $Latex formula$ ways. Hence the total number of arrangements is given by;

$Latex formula$

The next example involves repetitions.

Example 10

How many different number plates for cars exist if each contains 3 consonants of the alphabet followed by three digits?

Solution 10

There are six places to fill. In the first three places, we have that a consonant may occur, implying that one of 21 possible letters may occur in each of the first three positions. In the last three positions one 10 possible numbers may go into each one of the positions. Note that in this case repetitions are allowed.

$Latex formula$

We shall now consider a probability question involving permutations. Recall that the probability of an event $Latex formula$ is given by

$Latex formula$

where the sample space is the set of all possible outcomes.

Example 11

Mr. and Mrs. Smith and $Latex formula$ guests sit around a circular dinner table. Find the probability that the two hosts are together.

Solution 11

So, to solve this question we need to find the total number of ways that the $Latex formula$ people may be arranged, and this becomes the number of elements in the sample space. We then need to find the no. of ways the hosts may be together.

$Latex formula$

To find the number of ways the hosts may be together, we simply consider them as one unit at which point we have 7 objects left, and then consider the possible rearrangements around circular dinner table. Recall that the couple may also be arranged amongst themselves.

$Latex formula$

Thus we have that the probability that the hosts are together is given by,

$Latex formula$

Combinations

Recall that a combination is a selection where the order of the objects is not important. The number of combinations of $Latex formula$ objects, all distinct, taken $Latex formula$ at a time is given by,

$Latex formula$

and is read “ $Latex formula$ choose $Latex formula$”. A popular alternative notation for this is,

$Latex formula$

We shall now consider some examples that illustrate the use of this formula.

Example 12

In horse racing, a quinella refers to choosing the first two horses in either order. Find the number of possible quinella choices in a race of 8 horses, assuming all horses are equally likely to win.

Solution 12

So we are selecting two at time from a set of eight objects, disregarding order. This is equal to,

$Latex formula$

Hence there are 28 quinella possibilities.

Questions involving combinations may imply restrictions upon the possible selections made. We will consider some examples to illustrate some possible types of questions.

Example 13

In how many ways can a prefect committee of $Latex formula$ boys and $Latex formula$ girls be chosen from a group of $Latex formula$ boys and $Latex formula$ girls?

Solution 13

In this question, we are selecting $Latex formula$ from a group of $Latex formula$ and then selecting $Latex formula$ from a group of $Latex formula$. In each case order is not important. Note that we shall multiply the two by the fundamental counting principle. The number of such prefect committees is given by,

$Latex formula$

Note: Students often ask when to multiply results and when to add them (For e.g. in the above example we multiplied them). As a general rule, results are added if the conjunction between the two events is an “and”, and the results are added if the conjunction between the events is an “or”. Consider the example below for an “or” example.

Example 14

Find the number of ways to select 3 letters from the letters of the word EXERCISE.

Solution 14

Since there are three E’s, we must break this up into cases. Every case classifies into one of the following cases: (1) No doubles or triples present, (2) one double present or (3) one triple present. This technique is particularly important in Mathematics Extension 2.

No Doubles or triples:

We must choose three letters from E , X , R , C , I , S. The number of ways to do so is given by,

$Latex formula$

One Double only:

So we have two E’s present in our triple, and we now need to select one letter from the letters X , R , C , I , S since we may not choose another E, as this will make it a triple, which is a separate case. The number of ways to do so is given by,

$Latex formula$

One Triple only:

There is only one way to choose a group containing three E’s. Since there are no other possibilities.

Thus, the total number of combinations is given by,

$Latex formula$

$Latex formula$

Example 15

How many diagonals does an $Latex formula$-gon ( $Latex formula$ sided polygon) have?

Solution 15

The number of diagonals present is equal to the number of ways we can choose two points with order not important, minus the number of sides. This is because upon choosing two points, we automatically have a line through these points and thus this presents itself as a diagonal. Of course, those lines which form the sides of the polygon are then removed from the total count. Thus the total number of diagonals is,

$Latex formula$

We shall now consider some examples involving both combinations and permutations. With these examples, at times the fundamental counting principle may be used to great success. However, the fundamental counting principle is not necessarily the easiest way to solve each problem. Observe the examples below. Again, the best way to master these problems is to solve a lot of them.

Also, from here on in and for all examination type questions, students should be wary about repetitions. Students should always ask themselves if repetition is allowed or not. Often this is easily answered, however students should still practice distinguishing between the two.

Example 16

Consider the word RIEMANN. How many 4 letter words may be formed containing;

a) no N’s.

b) one N.

c) both N’s

Solution 16

a) We have to permute four letters from the letters R , I , E , M , A. The total number of ways is,

$Latex formula$

Notice here that we initially choose 4 from the 5 letters, then arrange those letters accordingly.

b) Here, we already have one N present, implying that we now have to choose three from R , I , E , M , A. Once we have chosen the letters, we then need to arrange those letters accordingly including the N that is already present as one of the four. Hence the total number of ways is;

$Latex formula$

c) Here we already have two N’s present and thus need to choose two letters from the letters R , I , E , M , A. Once we have chosen the letters, we then need to rearrange these letters with the two N’s. Be wary, that in this case we must divide the total number permutations by $Latex formula$ since the N occurs twice. Thus, the total number of such arrangements is;

$Latex formula$

Example 17

In how many ways can 6 different books be distributed between 2 students, provided that both students receive at least one book?

Solution 17

For this question we set up a table that indicates the number of books each student receives and the number of possible ways to distribute the books in each case.

 Case no. No. of books student A has No. of books student B has Number of ways to receive books 1 1 5 $Latex formula$ 2 2 4 $Latex formula$ 3 3 3 $Latex formula$ 4 4 2 $Latex formula$ 5 5 1 $Latex formula$ OVERALL $Latex formula$

Hence the total number of ways the books may be distributed in this way is 62.

Example 18

Four families arrive at a resort where there are 4 motels.

a) If there are no restrictions on where they stay, how many different accommodation arrangements are there?

b) If each family stays at a different motel, how many arrangements are possible?

c) Two of the families are close friends and wish to stay in the same motel. How many different accommodation arrangements are possible if the other two can stay at any of the other motels?

Solution 18

a) Each family has $Latex formula$ choices, and hence as there are four families, the total number of arrangements is given by;

$Latex formula$

b) If each family stays at a different motel, then the first family has $Latex formula$ choices, and the second has $Latex formula$, the third has $Latex formula$ and the fourth has $Latex formula$ choice. Hence the total number of arrangements is;

$Latex formula$

c) If two of the families wish to be together, then they may choose any of the four motels. Once they have chosen, the other two families each have 3 choices. Hence the total number of arrangements is given by,

$Latex formula$