Permutation

Permutation of a set of objects means an arrangement of objects in some order. Now, we shall find the permutation of a set of objects for the following different cases.

Set of objects all different

Let us consider abc and cba. Both of them consist of the same letters a, b, c but they are arranged in different order. So they are different permutations of the letters a, b, c. So, we can form many different permutations from a set of objects taken all at a time or taken particular number of objects at a time.

The number of permutations that can be formed taken $r$ at a time out of $n$ given objects is denoted by $P(n,r)$ or $^nP_r$.

Theorem: The total number of permutations of a set of n objects taken r at a time is given by \[P(n,r)=n(n-1)(n-2)…(n-r+1)\;\;(n≥r)\]

Proof: We prove this theorem by using the basic principle of counting.

The number of permutations of a set of $n$ objects taken $r$ at a time is equivalent to the number of ways in which $r$ positions can be filled up by those $n$ objects. To fill up the first position, there are $n$ choices. After filling the first position, there are only $(n-1)$ objects left. Hence, to fill up the second position, there are $(n-1)$ choices.

Similarly, there are $(n-2)$ choices to fill up the third position and so on. Ultimately, to fill up the $r^{\text{th}}$ position, there are $n-(r-1)=n-r+1$ choices. Then by the basic principle of counting, the total number of ways in which $r$ positions can be filled up is \[n(n-1)(n-2)…(n-r+1)\]

\[\begin{array}{l} \therefore P(n,r) &= n(n-1)(n-2)…(n-r+1) \\ &= \frac{n(n-1)(n-2)…(n-r+1)(n-r)…3\cdot 2\cdot 1}{(n-r)…3\cdot 2\cdot 1} \\ &= \frac{n!}{(n-r)!} \end{array}\] This gives the permutations of a set of $n$ objects taken $r$ at a time.

Cor. The permutations of a set of $n$ objects taken all at a time i.e. $r=n$ is given by, \[P(n,n)=n(n-1)(n-2)…1=n!\]

Example: If three persons enter a bus in which there are ten vacant seats, find in how many ways they can sit.

Here, there are ten vacant seats $(n=10)$ and three persons $(r=3)$. \[\begin{array}{l} \therefore P(10,3) &= \frac{10!}{(10-3)!} \\ &= \frac{10!}{7!} \\ &= 10×9×8 \\ &= 720 \end{array}\] Hence, they can sit in $720$ ways.

Set of objects not all different

Here, we shall find permutation of $n$ objects taken all at a time in which some objects are of same kind. Suppose in $n$ objects, $p$ of the objects are of first kind, $q$ of them are of second kind, $r$ of them are of third kind and the rest all are different.

Let $x$ be the total number of permutations of $n$ objects taken all at a time. Out of these $n$ objects, let $p$ of the objects of the first kind be replaced by $p$ new objects different from one another and also different from each of the remaining objects. If these $p$ different objects be arranged among themselves, keeping the position of all other objects same, they will give $p!$ permutations corresponding to each $x$ permutations. Hence, there will be $x×p!$ permutations in all.

In the same way, if $q$ of the objects of the second kind be replaced by $q$ new objects different from one another and from the remaining objects, in each of $x×p!$ permutations, the total permutations is $x×p!×q!$.

Similarly, if $r$ of the objects be replaced by $r$ different objects then the total number of permutations when all objects are different is $x×p!×q!×r!$.

But the total permutations of $n$ different objects taken all at a time is $n!$. \[\therefore x×p!×q!×r!=n!\] \[\Rightarrow x=\frac{n!}{p!\,q!\,r!}\] Thus, the total number of permutations \[=\frac{n!}{p!\,q!\,r!}\]

Example: In how many ways can the letters of the word “MATHEMATICS” be arranged?

The word “MATHEMATICS” consists of $11$ letters, $2$ of which are M’s, $2$ of which are A’s, $2$ of which are T’s and the rest are different. \[\therefore n=11, p=2, q=2, r=2\] Therefore, the total number of permutations \[=\frac{11!}{2!\,2!\,2!}\]

Circular Permutation

Consider four letters A, B, C and D be arranged in a circle. There are six different arrangements as shown below.

Taking clockwise arrangements, they are ABCD, ABDC, ADBC, ADCB, ACBD and ACDB. The arrangements BCDA, CDAB, DABC are same as the arrangement ABCD. Same thing follows for the rest.

If they were arranged in a line, then all the arrangements will be different. Hence, for every circular arrangements of A, B, C, D there are four arrangements in a line. If $P$ be the number of circular arrangements, then $4P$ is the number of arrangements in a line. \[\begin{array}{l} \therefore & 4P &= 4! \\ \Rightarrow & P &= 3! &= 6 \end{array}\]

In other words, let us explain this as; suppose we have to fill in four blank spaces circularly with objects A, B, C and D. Let any one of the them, say A, be placed in any one of the spaces. Now, there are three objects left to be arranged in three blank spaces which can be done in $3!$ ways.

This can be generalised to the following theorem:

Theorem: The total number of permutations of a set of $n$ objects arranged in a circle is $(n-1)!$.

Proof: Let the $n$ objects be $a_1,a_2,…,a_n$. If they are arranged in a circle, then the arrangements $\;a_1,a_2,…,a_n$, $\;a_2,a_3,…,a_n,a_1$, $\;a_3,a_4,…,a_n,a_1,a_2$ etc. are not distinguishable.

But if they are arranged in a straight line, to each arrangement in a circle, there are $n$ arrangements in a line. If $P$ is the number of arrangements in the circle, then, \[\begin{array}{l} & nP &= n! \\ \text{or,} & P &= \frac{n!}{n} \\ \therefore & P &= (n-1)!\end{array}\]

In the above theorem, we have considered that the clockwise and anticlockwise arrangements to be different. If they are not to be taken as different, then the number of arrangements will be \[\frac{1}{2}(n-1)!\]

In the above illustration of arranging A, B, C and D in a circle, the arrangements (a) and (d) are same, so are (b) and (f) as well as (c) and (e), if we consider the clockwise and anticlockwise arrangements to be same. Hence, the number of arrangements is \[\frac{1}{2}×3!=3\;\text{ways}\]

However, if the arrangements be with respect to the seats (i.e. think of the seats to be numbered) then the one that was fixed first can be given any one of the $n$ different seats. Hence, the total number of arrangements will be \[n×(n-1)!=n!\]

Example: In how many ways can eight people be seated in a round table if two people insist in sitting next to each other?

Since two people insist in sitting next to each other, consider those two people as one single thing. Hence we have to arrange seven people in a round table which can be done in \[(7-1)!=6!\;\text{ways}\]

Also, these two people can interchange their positions in $2!$ ways. Thus, the total number of arrangements \[=6!×2!=1440\;\text{ways}\]

Permutation of Repeated Things

Here, we shall find the permutation of $n$ objects taken $r$ at a time when each object may occur any number of time.

Let there be $n$ objects and $r$ places. The first place can be filled up by any one of the $n$ objects. So there are $n$ choices for filling up the first place. After filling up the first place, the second place can also be filled up by $n$ objects as the object occupying the first place may also occupy the second place. Hence, the first two places can be filled up in $n×n=n^2\;\text{ways}$. In the same way, the third place can also be filled in $n$ ways and the first three places can be filled up in $n×n×n=n^3\;\text{ways}$.

Proceeding in the same way, the $r$ places can be filled by $n$ objects in \[n×n×n×…×r\;\text{times}\] \[=n^r\;\text{ways}\]

Example: In how many ways can four letters be posted in six letter boxes?

Here, the first letter can be posted in six letter boxes. The second letter can also be posted in six letter boxes as the repetition is allowed. Since there are four letters, $r=4$ and six letter boxes, $n=6$. Thus, the total number of ways \[=n^r=6^4=1296\;\text{ways}\]