Introduction To Permutation

$\underline{Introduction}$

The word $\unicode{0x201C} permute \unicode{0x201D}$ means to rearrange.or to change the order.

For example, if we rearrange the digits of the number $123$, we can get the following numbers:

$132$

$213$

$231$

$312$

$321$

Therefore, including the original number $123$, there are $6$ possible arrangements of the digits $1,\ 2,$ and $3$.

$\underline{Arrangement\ Of\ All\ Distinct\ Objects:}$

Let us count the possible number of arrangements of four distinct objects $a$, $b$, $c$ and $d$.

Let us imagine that there are four empty spaces to be filled as shown below:

$\underline{*}$ $\underline{*}$ $\underline{*}$ $\underline{*}$

We can now restate our problem, to say that in how many ways can we fill up the four empty spaces such that each space contains one of the given objects. Thus, each unique selection will correspond to a unique arrangement.

The first place can be filled up using any one of the four given objects. So there are $4$ ways of filling the first blank.

For each of the choices we make for the first place, we will be left with $3$ objects to choose from for the second place.

Hence we can fill up the first two spaces is $4 \times 3 = 12$ ways.

-----------book page break-----------

These are:

$\underline{a} \underline{b} \underline{*} \underline{*}$, $\underline{a} \underline{c} \underline{*} \underline{*}$, $\underline{a} \underline{d} \underline{*} \underline{*}$,

$\underline{b} \underline{c} \underline{*} \underline{*}$, $\underline{b} \underline{d} \underline{*} \underline{*}$, $\underline{b} \underline{a} \underline{*} \underline{*}$,

$\underline{c} \underline{d} \underline{*} \underline{*}$, $\underline{c} \underline{a} \underline{*} \underline{*}$, $\underline{c} \underline{b} \underline{*} \underline{*}$,

$\underline{d} \underline{a} \underline{*} \underline{*}$, $\underline{d} \underline{b} \underline{*} \underline{*}$, $\underline{d} \underline{c} \underline{*} \underline{*}$,

Moving ahead, after filling up the first two places, we are left with $2$ choices to fill up the third space, and finally we will be left with $1$ choice for the last space.

Therefore, the total number of arrangements we can have with $4$ distinct items is $4 \times 3 \times 2 \times 1 = 24$

The above product series is represented as $\xafactorial{4}$ or in modern days, more commonly as $4!$

So, if we have $n$ distinct objects, we can have:

$n \times (n-1) \times (n-2) \times ... \times 2 \times 1 = n!$ different arrangement of these objects.

$\underline{Arrangement\ Of\ Subsets\ Of\ Distinct\ Objects:}$

Now we will see how to count the possible arrangements given $n$ distinct object but using only $r$ objects at a time, where $r \le n$

We can visualise this problem easily using $r$ empty spaces that need to be filled up using $r$ items from a set of $n$ distinct objects.

The first place can be filled up using any one of the $n$ given objects, the second place can be filled up in $n-1$ ways.

Likewise the last $(r\xasuper{th})$ place can be filled up in $n - r + 1$ ways.

The total number of ways is:

$n \times (n - 1) \times (n - 2) \times .... (n - r + 2) \times (n - r + 1)$ ways

-----------book page break-----------

Multiplying the above expression by $(n - r)(n-r-1)..2\times 1$ and dividing it by the same number we get:

Total number of arrangements $= \dfrac{n \times (n - 1) \times ... \times (n - r + 1) \times (n - r) \times ... \times 2 \times 1}{(n - r) \times (n - r - 1) \times ... \times 2 \times 1}$

$= \dfrac{n!}{r!}$

Using the standard notations of permutation, we denote this as $\xaperm{n}{r}$, read as:

$\unicode{0x201C}$permutations of $n$ distinct objects taking $r$ at a time$\unicode{0x201D}$

$\underline{Arrangement\ Of\ Objects\ Containing\ Identical\ Items:}$

Let's say we have to count the number of arrangements of $3$ tiles containing $2$ red, $1$ blue tile.

To begin with we can treat each of the red tiles as distinct by marking them $R_1,\ R_2$. With this we can have $3!$ arrangements, which are as follows:

$\underline{R_1} \underline{R_2} \underline{B}$, $\underline{R_1} \underline{B} \underline{R_2}$,

$\underline{R_2} \underline{R_1} \underline{B}$, $\underline{R_2} \underline{B} \underline{R_1}$,

$\underline{B} \underline{R_1} \underline{R_2}$, $\underline{B} \underline{R_1} \underline{R_1}$

Now, if we treat $R_1$ and $R_2$ as identical objects, then all the arrangements which are obtained by interchanging $R_1$ and $R_2$ will be treated as one. For example,

$\underline{R_1} \underline{R_2} \underline{B}$ and $\underline{R_2} \underline{R_1} \underline{B}$ will be treated as one arrangement that is $\underline{R} \underline{R} \underline{B}$

Similarly $\underline{R_1} \underline{B} \underline{R_2}$ and $\underline{R_2} \underline{B} \underline{R_1}$ will be treated as $\underline{R} \underline{B} \underline{R}$

and

$\underline{B} \underline{R_1} \underline{R_2}$ and $\underline{B} \underline{R_2} \underline{R_1}$ will be treated as $\underline{B} \underline{R} \underline{R}$

-----------book page break-----------

Since there are $2!$ arrangements possible with two identical red tiles, the total number of arrangements in this case is:

$\dfrac{3!}{2!} = 3$

Now, we can generalise the above, for $n$ given objects, of which $r_1$ are identical and of type $1$, $r_2$ are identical and of type $2...$, $r_n$ are identical and of type $n$, then the possible number of arrangements is:

$\dfrac{n!}{r_1! \times r_2! \times ... \times r_n!}$