Permutations

Suppose that you have to arrange n people in a row. How many distinct arrangements are possible? Visualize a row with n chairs:

\[\underbrace {{\fbox{}}\;{\fbox{}}\;{\fbox{}}{\ldots}{\ldots}{\ldots}\;{\fbox{}}\;{\fbox{}}{\fbox{}}}_{nchairs}\]

We have n options to fill the first chair, \(\left( {n - 1} \right)\) options to fill the second chair, \(\left( {n - 2} \right)\) options to fill the third chair, and so on. Thus, using the FPC, the total number of arrangements of the n people in the row of n chairs is

\[\left( n \right) \times \left( {n - 1} \right) \times \left( {n - 2} \right) \times ... \times 1 = n!\]

Each particular arrangement is termed a permutation of the n people. Thus, the total number of permutations of n people (or in general, n distinct objects) is n! .

Now, suppose that we have n people, but only r chairs, where r is less than n. In how many ways can we seat the n people, taken r at a time, in the r chairs? In other words, how many permutations exist of n people (or n distinct objects) taken r at a time?

Once again, we make use of the FPC:

• there are n options for the first chair

• once the first chair is filled, there are \(\left( {n - 1} \right)\) options for the second chair…

• …and so on, till we reach the \({r^{th}}\) chair. There are \(\left( {n - r + 1} \right)\) options for this chair. Make sure you understand why this expression is correct.

Thus, the number of permutations of n persons, taken r at a time, is

\[\left( n \right) \times \left( {n - 1} \right) \times ... \times \left( {n - r + 1} \right)\]

At this point, we introduce a new notation. The symbol \(^n{P_r}\) is used to denote the number of permutations of n distinct objects, taken r at a time. Thus,

\[^n{P_r} = \left( n \right) \times \left( {n - 1} \right) \times ... \times \left( {n - r + 1} \right)\]

Here are some examples:

(i) If you have 6 people and 4 chairs, then the number of possible arrangements of the 6 people in the 4 chairs (taken 4 at a time) is:

\[^6{P_4} = 6 \times 5 \times 4 \times 3 = 360\]

(ii) The number of 3-letter words which can be formed from the letters of the word KEYBOARD is

\[^8{P_3} = 8 \times 7 \times 6 = 336\]

Let us find a shorter expression for \(^n{P_r}\). Note that in the expanded product form of \(^n{P_r}\), the product from n to \(\left( {n - r + 1} \right)\). Let us take this product all the way from n to 1. We do this by multiplying the existing product with

\[\begin{align}&\left( {n - r} \right) \times \left( {n - r - 1} \right) \times \left( {n - r - 2} \right) \times ... \times 1\\&{\rm{or}},\quad\left( {n - r} \right)!,\end{align}\]

and dividing by this same expression, as follows:

\[\begin{align}&^n{P_r} \;= \left( n \right) \times \left( {n - 1} \right) \times ... \times \left( {n - r + 1} \right)\\&\qquad = \frac{{\left( n \right) \times \left( {n - 1} \right) \times ... \times \left( {n - r + 1} \right) \times \left( {n - r} \right)!}}{{\left( {n - r} \right)!}}\end{align}\]

Now, in the numerator, the product goes all the way from n to 1. Thus,

\[^n{P_r} = \frac{{n!}}{{\left( {n - r} \right)!}}\]

Some examples:

\[\begin{align}&^5{P_2} = \frac{{5!}}{{\left( {5 - 2} \right)!}} = \frac{{5!}}{{3!}} = \frac{{120}}{6} = 20\\&^6{P_5} = \frac{{6!}}{{\left( {6 - 5} \right)!}} = \frac{{6!}}{{1!}} = \frac{{120}}{1} = 120\\&^7{P_2} = \frac{{7!}}{{\left( {7 - 2} \right)!}} = \frac{{7!}}{{5!}} = \frac{{7 \times 6 \times 5!}}{{5!}} = 42\end{align}\]

Let us talk about an interesting result which follows from this discussion. We have seen that the number of permutations of n objects, taken all together, is \(n!\). Thus,

\[\begin{align}&^n{P_n} = n!\quad\Rightarrow \,\,\,\frac{{n!}}{{\left( {n - n} \right)!}} = n!\\&\qquad \quad \qquad\Rightarrow \frac{{n!}}{{0!}} = n!\,\,\, \Rightarrow \,\,\,0! = 1\end{align}\]

We see that the value of 0! is 1.

Now, we summarize our discussion on permutations up to this point.

1. You should always associate the word permutations with the word arrangements. When you read the phrase “number of permutations”, think of the phrase “number of arrangements”. When you are arranging objects, the order of the objects matters. For example, ABC and ACB are different arrangements, even though they contain the same objects (A, B and C).

2. The number of permutations of n distinct objects taken all together is \(n!\).

3. The number of permutations of n distinct objects, taken r at a time (where r is less than n), is \(^n{P_r} = \frac{{n!}}{{\left( {n - r} \right)!}}\).

4. These results were derived using the FPC, and no new concept was applied. Make sure you internalize the derivation of these results from the FPC.

5. From the particular case of \(^n{P_n} = n!\), we were able to deduce that \(0! = 1\).

Let us apply these results to some examples.