Permutations and Combinations

What is permutation?

Linear permutation

When an arrangement with order is done on a straight line, it is known as a linear permutation. For instance, when you are required to find the number of ways the following 6 balls are to be arranged in order. Such arrangement of objects done in a straight line can be seen in the image below.

Circular permutation

However, when an arrangement with order is done in a circular or curved manner, it is known as a circular permutation. An example can be seen when different colored stones on a bead are to be arranged. The figure below gives an insight into circular arrangements.

Unlike linear permutations where items are organized on a straight line, circular permutations are arranged in a circular manner as seen above. Hereafter, you shall have further details and examples regarding circular permutations.

What is the permutation sign?

Several signs are used to represent permutation; they are:

$$\begin{gathered} P(n,r) \\ or \\ {}_{n}P_r \end{gathered}$$

Types of linear permutation and corresponding formulas

There are two types of permutation, permutation with repletion and permutation with no repetition.

Permutation with repetition

In such a case of arrangement or selection, the object can be reused in all steps of selection. This means that each component of a group can be used whenever the selection is made.

For instance, if three letters from the alphabets A to Z were to be selected, then the letter A can be selected in those 3 times like AAA. The same argument goes for B and C and so on etc. Since we have 26 alphabets, we have 26 choices each time! Therefore, the amount of times the three letters would be selected is,

${26}^3=17576times$

where the base 26 means that there are 26 alphabets and the exponent 3 represents the number of alphabets to be selected. This means that for selection with repetition using the formula,

$Thenumberofpossibleways=n^r$

where n is the number of objects in a set and r is the number of times the selection is made.

Permutation with no repetition

In this case, there is no repetition of a member of a set used when making selections. Once a member is used, it cannot be reused and as such reduces the chances available.

For instance, if one alphabet is to be picked and Z is picked, once Z is used it cannot be reused, reducing our chances from 26 to 25. Likewise, if two alphabets are to be picked and you pick Z and Y, once Z and Y are used, it further reduces our possibility from 26 to 24 and so on. Thus it leaves us with:

$$\begin{gathered} 26\times 25\times 24\times 23\times 22\times 21...\times 1=26! \\ 26!=403291461126605635584000000 \end{gathered}$$

Therefore, unlike permutation with repetition which allows item among the sets to be replaced and reused, permutations without repetition does not allow the replacement and subsequent use of any item once used.

In the earlier example, all members of numbers are selected and arranged. Now, what happens if some are selected out of all? For instance, you are given numbers 1 to 10 and you have to select 6.

Recall we can arrange numbers 1 to 10 in

$10!=10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1ways$.

However, since we are now selecting only 6 numbers, this means that we have

$10\times 9\times 8\times 7\times 6\times 5ways=\frac{10!}{4!}ways$

But$4!=(10-6)!$. Thus we can deduce the permutation formula:

$P(n,r)=\frac{n!}{(n-r)!}$

where n is the number of objects, r is the number of objects to be selected from.

Therefore, to solve the question afresh, we have

$$\begin{gathered} P(10,6)=\frac{10!}{(10-6)!} \\ P(10,6)=\frac{10!}{4!} \\ P(10,6)=\frac{10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1}{4\times 3\times 2\times 1} \\ P(10,6)=10\times 9\times 8\times 7\times 6\times 5 \\ P(10,6)=151,200 \end{gathered}$$

Using permutations in arranging letters

We recall that in order to make an ordered arrangement without repetition involving all members of a set of n members, we have P(n,n) = n! ways.

Meanwhile, if some members, r, out of a set, n, were to be selected and arranged, we have,

$P(n,r)=\frac{n!}{(n-r)!}$ways

However, there are cases where a member of a set is repeated within a set. For instance, in the word WINNER, N is repeated twice. Therefore, to account for the double N it becomes:

$\frac{P(6,6)}{P(2,2)}=\frac{6!}{2!}=\frac{6\times 5\times 4\times 3\times 2\times 1}{2\times 1}=360$

Note that the permutation of all members is divided by the permutation of how many repetitions (in this case 2). So, if N were repeated thrice the permutation would have been divided by P(3,3) which is 3!.

Likewise, if you have more than one member of a set being repeated, the permutation of all members is divided by the product of the permutation of each repeated member. For instance, in the word LESSES, we have two E and three S, with a total of six alphabets. To arrange this we use:

$\frac{P(6,6)}{P(2,2)\times P(3,3)}=\frac{6!}{2!\times 3!}=\frac{6\times 5\times 4\times 3\times 2\times 1}{(2\times 1)\times (3\times 2\times 1)}=60$

Based on this knowledge to arrange letters with the same alphabet it becomes

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

where, n is the total number of letters, p and q are the numbers of times an alphabet is repeated.

Circular permutation formula

We have considered permutation of objects in a linear manner, but sometimes arrangement is done in a circular or rotating way as mentioned earlier in this study. This requires a different approach because unlike a straight line that begins from a point and ends at another point, a circle begins at a point and ends on the same point. This means that for an n set of numbers, n is repeated so that we have:

$$\begin{gathered} \frac{P(n,n)}{n}=\frac{n!}{n}=\frac{n\times (n-1)!}{n} \\ \frac{n\times (n-1)!}{n}=(n-1)! \end{gathered}$$

Thus, permutation, in this case, follows the use of $(n-1)!$.

What is combination?

The combination is a selection method that does not follow an order. Unlike permutation, if three letters were to be chosen from letters A to E, ABC, ACB, BAC, BCA, CAB, and CBA would all be outcomes because the order is involved. But in combination where the order is not needed, only one ABC stands for the rest because they are all repetitions if the order is not involved.

Outcomes of combination are lower than those of permutation because, with the removal of order, only one outcome replaces the orders which are similar. Like instead of writing these six outcomes; ABC, ACB, BAC, BCA, CAB, and CBA, you write just one ABC. reducing the option of that combination from 6 to 1.

To calculate combinations we use:

$C(n,r)=\frac{n!}{(n-r)!r!}$

Where

n stands for the total number of items to be chosen from

r stands for the number of items chosen.

What is the combination sign?

Several signs are used to represent permutation; they are:

$$\begin{gathered} C(n,r) \\ or \\ {}_{n}C_r \end{gathered}$$

Combination of multiple events

In combination with multiple events, more than one kind of choice is made from a set containing more than one group.

For instance, if a class of 14 contains 8 girls and 6 boys and you were to pick 4 boys and 5 girls, then you would have to consider your choice per gender. Therefore, it becomes picking 4 boys out of 6 and 5 girls out of 8. This means that:

$$\begin{gathered} C(6,4)\times C(8,5) \\ C(6,4)=\frac{6!}{(6-4)!4!} \\ C(6,4)=\frac{6\times 5\times 4!}{2!\times 4!} \\ C(6,4)=\frac{30}{2} \\ C(6,4)=15 \end{gathered}$$

and

$$\begin{gathered} C(8,5)=\frac{8!}{(8-5)!5!} \\ C(8,5)=\frac{8\times 7\times 6\times 5!}{3!\times 5!} \\ C(8,5)=\frac{8\times 7\times 6}{3\times 2} \\ C(8,5)=56 \end{gathered}$$

therefore,

$$\begin{gathered} C(6,4)\times C(8,5)=15\times 56 \\ \mathit{C}\mathbf{(}\mathbf{6}\mathbf{,}\mathbf{4}\mathbf{)}\mathbf{\times }\mathit{C}\mathbf{(}\mathbf{8}\mathbf{,}\mathbf{5}\mathbf{)}\mathbf{=}\mathbf{840} \end{gathered}$$

Combination with repetition

Sometimes, selections are made without order but with repetition. Such operation is a combination with repetition and you apply the formula,

$\frac{(r+n-1)!}{(n-1)!r!}$

where n is the total number of things to choose from, r is the number of things we are to pick out of n and repetition is allowed with no order involved.

What is the difference between permutation and combination?

Confusing questions of permutation with those of combinations occur. They are indeed quite similar in that they both deal with possible items occurring. However, they differ in the following major ways:

Order

In permutation, the arrangement involves items that are arranged in order. This means that the position of items is very important. But in combination, the selection of items is without order. Therefore the order is not relevant in combination.

For example, if the letters A,B,C are to be permuted without repetition, then we have; AB, BA, AC, CA, BC, and CB. Meanwhile, if A, B, and C are to be combined without repetition, we have; AB, AC, and BC. Note that in permutation, AB and BA are not the same because, in AB, A comes before B same thing applies in BA and the rest of the outcomes. This as a matter of fact makes the outcomes of permutation larger than those of combination.

Terminology

Several people make mistakes when using the right terms regarding permutation as well as combination. In permutation, you arrange or organize but in combination, you choose or select. Never make the mistake of interchanging these terms when addressing either permutation or combination.

Formula

Very importantly and clearly observed, the formula of permutation differs from that of combination. the permutation formula is:

$P(n,r)=\frac{n!}{(n-r)!}$

however, the combination is calculated with:

$C(n,r)=\frac{n!}{(n-r)!r!}$

The difference in the formula is the r!, we can thus create a mathematical relationship between permutation and combination as:

$Permutation=Combination\times r!$

This again confirms why the outcomes of permutation are larger than those of combination by a multiplicative factor of r!.

Further examples of permutation and combination

You should try out many more problems so as to have an idea of several ways you can be tasked in an exam. A few examples here would help you.