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 $p$ distinct ways to do $A$ , andq distinct ways to do $B$ , then in total there are $p\times q$ ways to do both $A$ and $B$ provided $A$ and $B$ 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 $=3\times 4=12$

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 $=3\times 2\times 1=6$

Permutations and the Factorial Notation

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

$n!=n(n-1)(n-2)(n-3)\ldots (5)(4)(3)(2)(1)$

So as simple examples we have,

$3!=3\times 2\times 1=6$

$5!=5\times 4\times 3\times 2\times 1=120$

$(n-r)!=(n-r)(n-r-1)(n-r-2)\ldots (3)(2)(1)$ where $n>r>0$

By definition, we have that;

$0!=1$

The factorial function $(n)=n!$ , 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 $=6\times 5\times 4\times 3\times 2\times 1=720$

However, this is equal to;

$6!=720$

In general when arranging $n$ distinct objects in a row (repetitions not allowed) we have that the number of arrangements or permutations of those $n$ objects are given by $n!$ . Now, if we were to have $n$ 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 $n$ objects, with $p$ objects being non-distinct and of a certain type and $q$ objects being non-distinct and of another type and $r$ 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,

$\frac{n!}{p!q!r!\ldots }$

Although this may not be immediately obvious, the reason for the division by the values of $p, q$ and $r$ 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 $3$ M’s and that there are $2$ A’s, and that in total we have $6$ letters. Using the above formula we have that the number of arrangements of the letters is given by,

$\frac{6!}{3!2!}=60$

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 $n$ objects, all distinct, then the total number of ways in which these objects may be arranged about a circle is given by $(n-1)!$ .

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 $10$ people to arrange. Thus the total number of arrangements is given by,

$(10-1)!=9!=362, 880$

Suppose now that we have $p$ objects among those $n$ being similar and another $q$ 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 $n$ objects with $p$ similar and another $q$ similar and another $r$ similar etc. it follows that the total number of arrangements of those objects in a circle is given by

$\frac{(n-1)!}{p!q!r!\ldots }$

We now consider the arrangements of objects on a necklace, or a keychain. Suppose that we such to arrange $n$ distinct beads on a necklace. The total number of arrangements is given by the total number of unrestricted arrangements in a circle divided by $2$ . The division by $2$ 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 $n$ objects, each distinct, the number of arrangements of these objects on a necklace is given by,

$\frac{1}{2}(n-1)!$

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 $n$ objects choosing $r$ at a time is given by;

${}_{}{}^{n}P_{r}=\frac{n!}{(n-r)!}=n(n-1)(n-2)\ldots (n-r+1)$

Notice that for $n=r$ the formula becomes,

${}_{}{}^{n}P_{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!$

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 $3$ 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

${}_{}{}^{7}P_{3}=\frac{7!}{(7-3)!}=\frac{7!}{4!}=7\times 6\times 5=210$

Note that this is exactly the same as using the fundamental counting principle here the number of ways is given by $7\times 6\times 5=210$ .

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 $3$ with order important from a set of $8$ . Using the formula for permutations gives,

${}_{}{}^{8}P_{3}=\frac{8!}{5!}=8\times 7\times 6=336$

Example 8

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

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

Solution 8

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

$6!\times 3!=4320$

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

Let $S$ represent the boys sitting next to each other, and $\bar{S}$ represent the boys not sitting next to each other.
Let $n(A)$ represent the number of ways $A$ may occur.

Hence we have

$n(\bar{S})=n(Total with no restrictions)-n(S)$

Where $S$ is the complementary event. Thus we have that

$n(\bar{S})=8!-6!3!=36,000$

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

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 $3!/2!$ 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 $4!$ ways. Hence the total number of arrangements is given by;

$4!\times \frac{3!}{2!}=72$

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.

$n(Number plates)=21\times 21\times 21\times 10\times 10\times 10=21^{3}\times 10^{3}$

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

$P(E)=\frac{No.of elements where E is favourable}{Total number of elements in the sample space}$

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

Example 11

Mr. and Mrs. Smith and $6$ 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 $8$ 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.

$n(Total)=(8-1)!=7!=5040$

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.

$n(Hosts together)=(7-1)!\times 2!=6!2!=1440$

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

$P(Hosts together)=\frac{n(Hosts together)}{n(Total)}=\frac{1440}{5040}=\frac{2}{7}$

Combinations

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

${}_{}{}^{n}C_{r}=\frac{n!}{(n-r)!r! }$

and is read “ $n$ choose $r$ ”. A popular alternative notation for this is,

$\binom{n}{r}={}_{}{}^{n}C_{r}$

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,

$\binom{8}{2}=\frac{8!}{6!2!}=28$

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 $6$ boys and $3$ girls be chosen from a group of $10$ boys and $8$ girls?

Solution 13

In this question, we are selecting $6$ from a group of $10$ and then selecting $3$ from a group of $8$ . 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,

$\binom{10}{6}\binom{8}{3}=11,760$

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,

$\binom{6}{3}=\frac{6!}{3!3!}=20$

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,

$\binom{5}{1}=\frac{5!}{(5-1)!}=\frac{5!}{4!}=5$

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,

$n(Total)=n(No doubles or triples)+n(One double only)+n(One triple only)$

$n(Total)=20+5+1=26$

Example 15

How many diagonals does an $n$ -gon ( $n$ 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,

$\binom{n}{2} -n$

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,

$\binom{5}{4}\times 4!=120$

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;

$\binom{5}{3}\times 4!=240$

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 $2!$ since the N occurs twice. Thus, the total number of such arrangements is;

$\binom{5}{2}\times \frac{4!}{2!}=120$

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	$\binom{6}{1}=6$
2	2	4	$\binom{6}{2}=15$
3	3	3	$\binom{6}{3}=20$
4	4	2	$\binom{6}{4}=15$
5	5	1	$\binom{6}{5}=6$
OVERALL			$6+15+20+15+6=62$

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 $4$ choices, and hence as there are four families, the total number of arrangements is given by;

$4\times 4\times 4\times 4=4^{4}=256$

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

$4!=24$

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,

$4\times 3\times 3=36$

Mathematics Extension 1 – Permutations and Combinations