Every body of discovery is mathematical in form because there is no other guidance we can have - DARWIN

6.1 Introduction

Suppose you have a suitcase with a number lock. The number lock has 4 wheels each labelled with 10 digits from 0 to 9 . The lock can be opened if 4 specific digits are arranged in a particular sequence with no repetition. Some how, you have forgotten this specific sequence of digits. You remember only the first digit which is 7. In order to open the lock, how many sequences of 3-digits you may have to check with? To answer this question, you may, immediately, start listing all possible arrangements of 9 remaining digits taken 3 at a time. But, this method will be tedious, because the number of possible sequences may be large. Here, in this Chapter, we shall learn some basic counting techniques which will

enable us to answer this question without actually listing 3-digit arrangements. In fact, these techniques will be useful in determining the number of different ways of arranging and selecting objects without actually listing them. As a first step, we shall examine a principle which is most fundamental to the learning of these techniques.

6.2 Fundamental Principle of Counting

Let us consider the following problem. Mohan has 3 pants and 2 shirts. How many different pairs of a pant and a shirt, can he dress up with? There are 3 ways in which a pant can be chosen, because there are 3 pants available. Similarly, a shirt can be chosen in 2 ways. For every choice of a pant, there are 2 choices of a shirt. Therefore, there are $3 \times 2=6$ pairs of a pant and a shirt.

Let us name the three pants as $P_1, P_2, P_3$ and the two shirts as $S_1, S_2$. Then, these six possibilities can be illustrated in the Fig. 6.1.

Let us consider another problem of the same type.

Sabnam has 2 school bags, 3 tiffin boxes and 2 water bottles. In how many ways can she carry these items (choosing one each).

A school bag can be chosen in 2 different ways. After a school bag is chosen, a tiffin box can be chosen in 3 different ways. Hence, there are $2 \times 3=6$ pairs of school bag and a tiffin box. For each of these pairs a water bottle can be chosen in 2 different ways.

Hence, there are $6 \times 2=12$ different ways in which, Sabnam can carry these items to school. If we name the 2 school bags as $B_1, B_2$, the three tiffin boxes as $T_1, T_2, T_3$ and the two water bottles as $W_1, W_2$, these possibilities can be illustrated in the Fig. 6.2.

In fact, the problems of the above types are solved by applying the following principle known as the fundamental principle of counting, or, simply, the multiplication principle, which states that

“If an event can occur in $m$ different ways, following which another event can occur in $n$ different ways, then the total number of occurrence of the events in the given order is $m \times n$.”

The above principle can be generalised for any finite number of events. For example, for 3 events, the principle is as follows:

‘If an event can occur in $m$ different ways, following which another event can occur in $n$ different ways, following which a third event can occur in $p$ different ways, then the total number of occurrence to “the events in the given order is $m \times n \times p$.”

In the first problem, the required number of ways of wearing a pant and a shirt was the number of different ways of the occurence of the following events in succession:

(i) the event of choosing a pant

(ii) the event of choosing a shirt.

In the second problem, the required number of ways was the number of different ways of the occurence of the following events in succession:

(i) the event of choosing a school bag

(ii) the event of choosing a tiffin box

(iii) the event of choosing a water bottle.

Here, in both the cases, the events in each problem could occur in various possible orders. But, we have to choose any one of the possible orders and count the number of different ways of the occurence of the events in this chosen order.

6.3 Permutations

In Example 1 of the previous Section, we are actually counting the different possible arrangements of the letters such as ROSE, REOS, …, etc. Here, in this list, each arrangement is different from other. In other words, the order of writing the letters is important. Each arrangement is called a permutation of 4 different letters taken all at a time. Now, if we have to determine the number of 3-letter words, with or without meaning, which can be formed out of the letters of the word NUMBER, where the repetition of the letters is not allowed, we need to count the arrangements NUM, NMU, MUN, NUB, …, etc. Here, we are counting the permutations of 6 different letters taken 3 at a time. The required number of words $=6 \times 5 \times 4=120$ (by using multiplication principle).

If the repetition of the letters was allowed, the required number of words would be $6 \times 6 \times 6=216$.

Definition 1 A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.

In the following sub-section, we shall obtain the formula needed to answer these questions immediately.

6.3.1 Permutations when all the objects are distinct

Theorem 1 The number of permutations of $n$ different objects taken $r$ at a time, where $0<r \leq n$ and the objects do not repeat is $n(n-1)(n-2) \ldots(n-r+1)$, which is denoted by ${ }^{n} P_r$.

Proof There will be as many permutations as there are ways of filling in $r$ vacant places $ \underset{\leftarrow r \text{ vacant places} \rightarrow}{\Large{\square \square \square \cdots }} \Large{\square}$ by

the $n$ objects. The first place can be filled in $n$ ways; following which, the second place can be filled in $(n-1)$ ways, following which the third place can be filled in $(n-2)$ ways,…, the $r$ th place can be filled in $(n-(r-1))$ ways. Therefore, the number of ways of filling in $r$ vacant places in succession is $n(n-1)(n-2) \ldots(n-(r-1))$ or $n(n-1)(n-2) \ldots(n-r+1)$

This expression for ${ }^{n} P$ is cumbersome and we need a notation which will help to reduce the size of this expression. The symbol $n$! (read as factorial $n$ or $n$ factorial ) comes to our rescue. In the following text we will learn what actually $n$! means.

6.3.2 Factorial notation

The notation $n$! represents the product of first $n$ natural numbers, i.e., the product $1 \times 2 \times 3 \times \ldots \times(n-1) \times n$ is denoted as $n$ !. We read this symbol as ’ $n$ factorial’. Thus, $1 \times 2 \times 3 \times 4 \ldots \times(n-1) \times n=n$ !

$ \begin{aligned} & 1=1 ! \\ & 1 \times 2=2 ! \\ & 1 \times 2 \times 3=3 ! \\ & 1 \times 2 \times 3 \times 4=4 \text{ ! and so on. } \end{aligned} $

We define $0 !=1$

We can write $5 !=5 \times 4 !=5 \times 4 \times 3 !=5 \times 4 \times 3 \times 2$ !

$ =5 \times 4 \times 3 \times 2 \times 1 \text{ ! } $

Clearly, for a natural number $n$

$ \begin{aligned} n ! & =n(n-1) ! & & \\ & =n(n-1)(n-2) ! & & {[\text{provided}(n \geq 2)] } \\ & =n(n-1)(n-2)(n-3) ! & & {[\text{provided}(n \geq 3)] } \end{aligned} $

and so on.

6.3.3 Derivation of the formula for ${ }^{n} P_r$

$ { }^{n} P_r=\frac{n !}{(n-r) !}, 0 \leq r \leq n $

Let us now go back to the stage where we had determined the following formula:

$ { }^{n} P_r=n(n-1)(n-2) \ldots(n-r+1) $

Multiplying numerator and denomirator by $(n-r)(n-r-1) \ldots 3 \times 2 \times 1$, we get

$ { }^{n} P_r=\frac{n(n-1)(n-2) \ldots(n-r+1)(n-r)(n-r-1) \ldots 3 \times 2 \times 1}{(n-r)(n-r-1) \ldots 3 \times 2 \times 1}=\frac{n !}{(n-r) !}, $

Thus $\quad \quad \quad$ $ { }^{n} P_r=\frac{n !}{(n-r) !} \text{, where } 0<r \leq n $

This is a much more convenient expression for ${ }^{n} P_r$ than the previous one.

In particular, when $r=n,{ }^{n} P_n=\frac{n !}{0 !}=n$ !

Counting permutations is merely counting the number of ways in which some or all objects at a time are rearranged. Arranging no object at all is the same as leaving behind all the objects and we know that there is only one way of doing so. Thus, we can have

$$ { }^{n} P_0=1=\frac{n !}{n !}=\frac{n !}{(n-0) !} \quad \quad \quad \quad \quad\quad\quad \ldots(1) $$

Therefore, the formula (1) is applicable for $r=0$ also.

Thus $\quad \quad \quad$ $ { }^{n} P_r=\frac{n !}{(n-r) !}, 0 \leq r \leq n $

Theorem 2 The number of permutations of $n$ different objects taken $r$ at a time, where repetition is allowed, is $n^{r}$.

Proof is very similar to that of Theorem 1 and is left for the reader to arrive at.

Here, we are solving some of the problems of the pervious Section using the formula for ${ }^{n} P_r$ to illustrate its usefulness.

In Example 1 , the required number of words $={ }^{4} P_4=4 !=24$. Here repetition is not allowed. If repetition is allowed, the required number of words would be $4^{4}=256$.

The number of 3-letter words which can be formed by the letters of the word

NUMBER $={ }^{6} P_3=\frac{6 !}{3 !}=4 \times 5 \times 6=120$. Here, in this case also, the repetition is not allowed. If the repetition is allowed, the required number of words would be $6^{3}=216$.

The number of ways in which a Chairman and a Vice-Chairman can be chosen from amongst a group of 12 persons assuming that one person can not hold more than one position, clearly ${ }^{12} P_2=\frac{12 !}{10 !}=11 \times 12=132$.

6.3.4 Permutations when all the objects are not distinct objects

Suppose we have to find the number of ways of rearranging the letters of the word ROOT. In this case, the letters of the word are not all different. There are $2 Os$, which are of the same kind. Let us treat, temporarily, the $2 Os$ as different, say, $O_1$ and $O_2$. The number of permutations of 4-different letters, in this case, taken all at a time is 4 !. Consider one of these permutations say, $RO_1 O_2 T$. Corresponding to this permutation, we have 2 ! permutations $RO_1 O_2 T$ and $RO_2 O_1 T$ which will be exactly the same permutation if $O_1$ and $O_2$ are not treated as different, i.e., if $O_1$ and $O_2$ are the same $O$ at both places.Therefore, the required number of permutations $=\frac{4 !}{2 !}=3 \times 4=12$.

Permutations when $O_1, O_2$ are Permutations when $O_1, O_2$ are different. the same $O$.

$\left.\begin{array}{l}\mathrm{RO}_1 \mathrm{O}_2 \mathrm{T} \\ \mathrm{RO}_2 \mathrm{O}_1 \mathrm{T}\end{array}\right] \longrightarrow \quad \mathrm{ROOT}$

$\left.\begin{array}{l}\mathrm{RO}_1 \mathrm{O}_2 \mathrm{T} \\ \mathrm{RO}_2 \mathrm{O}_1 \mathrm{T}\end{array}\right] \longrightarrow \quad \mathrm{ROOT}$

$\left.\begin{array}{l}\mathrm{RO}_1 \mathrm{T} \mathrm{O}_2 \\ \mathrm{RO}_2 \mathrm{T} \mathrm{O}_1\end{array}\right] \longrightarrow \quad \mathrm{ROTO}$

$\left.\begin{array}{l}\mathrm{T} \mathrm{O}_1 \mathrm{RO}_2 \\ \mathrm{TO}_2 \mathrm{R} \mathrm{O}_1\end{array}\right] \longrightarrow \quad \mathrm{TORO}$

$\left.\begin{array}{l}\mathrm{RTO}_1 \mathrm{O}_2 \\ \mathrm{RTO}_2 \mathrm{O}_1\end{array}\right] \longrightarrow \quad \mathrm{RTOO}$

$\left.\begin{array}{l}\mathrm{TRO}_1 \mathrm{O}_2 \\ \mathrm{TRO}_2 \mathrm{O}_1\end{array}\right] \longrightarrow \quad \mathrm{TROO}$

$\left.\begin{array}{l}\mathrm{O}_1 \mathrm{O}_2 \mathrm{RT} \\ \mathrm{O}_2 \mathrm{O}_1 \text { TR }\end{array}\right] \longrightarrow \quad \mathrm{OORT}$

$\left.\begin{array}{c}\mathrm{O}_1 \mathrm{RO}_2 \mathrm{~T} \\ \mathrm{O}_2 \mathrm{RO}_1 \mathrm{~T}\end{array}\right] \longrightarrow \quad \mathrm{OROT}$

$\left.\begin{array}{c}\mathrm{O}_1 \mathrm{TO}_2 \mathrm{R} \\ \mathrm{O}_2 \mathrm{TO}_1 \mathrm{R}\end{array}\right] \longrightarrow \quad \mathrm{OTOR}$

$\left.\begin{array}{lll}\mathrm{O}_1 \mathrm{R} \mathrm{TO}_2 \\ \mathrm{O}_2 \mathrm{R} \mathrm{T} \mathrm{O}_1\end{array}\right] \longrightarrow \quad \mathrm{ORTO}$

$\left.\begin{array}{c}\mathrm{O}_1 \mathrm{TR}_2 \mathrm{O}_2 \\ \mathrm{O}_2 \mathrm{TRO}_1\end{array}\right] \longrightarrow \quad \mathrm{OTRO}$

$\left.\begin{array}{c}\mathrm{O}_1 \mathrm{O}_2 \text { TR } \\ \mathrm{O}_2 \mathrm{O}_1 \text { TR }\end{array}\right] \longrightarrow \quad \mathrm{OOTR}$

Let us now find the number of ways of rearranging the letters of the word INSTITUTE. In this case there are 9 letters, in which I appears 2 times and $T$ appears 3 times.

Temporarily, let us treat these letters different and name them as $I_1, I_2, T_1, T_2, T_3$. The number of permutations of 9 different letters, in this case, taken all at a time is 9 !. Consider one such permutation, say, $I_1 NT_1 SI_2 T_2 UE_3$. Here if $I_1, I_2$ are not same and $T_1, T_2, T_3$ are not same, then $I_1, I_2$ can be arranged in 2 ! ways and $T_1, T_2, T_3$ can be arranged in 3 ! ways. Therefore, $2 ! \times 3$ ! permutations will be just the same permutation corresponding to this chosen permutation $I_1 NT_1 SI_2 T_2 UET_3$. Hence, total number of different permutations will be $\frac{9 !}{2 ! 3 !}$

We can state (without proof) the following theorems:

Theorem 3 The number of permutations of $n$ objects, where $p$ objects are of the same kind and rest are all different $=\frac{n !}{p !}$.

In fact, we have a more general theorem.

Theorem 4 The number of permutations of $n$ objects, where $p_1$ objects are of one kind, $p_2$ are of second kind, …, $p_k$ are of $k^{\text{th }}$ kind and the rest, if any, are of different kind is $\frac{n !}{p_1 ! p_2 ! \ldots p_k !}$.

6.4 Combinations

Let us now assume that there is a group of 3 lawn tennis players $X, Y, Z$. A team consisting of 2 players is to be formed. In how many ways can we do so? Is the team of $X$ and $Y$ different from the team of $Y$ and $X$ ? Here, order is not important. In fact, there are only 3 possible ways in which the team could be constructed.

These are XY, YZ and ZX (Fig 6.3).

Here, each selection is called a combination of 3 different objects taken 2 at a time. In a combination, the order is not important.

Now consider some more illustrations.

Twelve persons meet in a room and each shakes hand with all the others. How do we determine the number of hand shakes. $X$ shaking hands with $Y$ and $Y$ with $X$ will not be two different hand shakes. Here, order is not important. There will be as many hand shakes as there are combinations of 12 different things taken 2 at a time.

Seven points lie on a circle. How many chords can be drawn by joining these points pairwise? There will be as many chords as there are combinations of 7 different things taken 2 at a time.

Now, we obtain the formula for finding the number of combinations of $n$ different objects taken $r$ at a time, denoted by ${ }^{n} C_r$.

Suppose we have 4 different objects A, B, C and D. Taking 2 at a time, if we have to make combinations, these will be $AB, AC, AD, BC, BD, CD$. Here, $AB$ and $BA$ are the same combination as order does not alter the combination. This is why we have not included BA, CA, DA, CB, DB and DC in this list. There are as many as 6 combinations of 4 different objects taken 2 at a time, i.e., ${ }^{4} C_2=6$.

Corresponding to each combination in the list, we can arrive at 2! permutations as 2 objects in each combination can be rearranged in 2! ways. Hence, the number of permutations $={ }^{4} C_2 \times 2$!.

On the other hand, the number of permutations of 4 different things taken 2 at a time $={ }^{4} P_2$.

Therefore $\quad { }^{4} P_2= ^{4} C_2 \times 2 !$ or $\frac{4 !}{(4-2) ! 2 !}= ^{4} C_2$

Now, let us suppose that we have 5 different objects A, B, C, D, E. Taking 3 at a time, if we have to make combinations, these will be $ABC, ABD, ABE, BCD, BCE$, $CDE, ACE, ACD, ADE, BDE$. Corresponding to each of these ${ }^{5} C_3$ combinations, there are 3! permutations, because, the three objects in each combination can be rearranged in 3! ways. Therefore, the total of permutations $={ }^{5} C_3 \times 3$!

Therefore $\quad{ }^{5} P_3={ }^{5} C_3 \times 3$ ! or $\quad \frac{5 !}{(5-3) ! 3 !}={ }^{5} C_3$

These examples suggest the following theorem showing relationship between permutaion and combination:

Theorem 5 ${ }^{n} P_r={ }^{n} C_r r!, 0<r \leq n$.

Proof Corresponding to each combination of ${ }^{n} C_r$, we have $r$! permutations, because $r$ objects in every combination can be rearranged in $r$ ! ways.

Hence, the total number of permutations of $n$ different things taken $r$ at a time is ${ }^{n} C_r \times r !$. On the other hand, it is ${ }^{n} P_r$. Thus

$ { }^{n} P_r={ }^{n} C_r \times r !, 0<r \leq n $

Remarks 1. From above $\frac{n !}{(n-r) !}={ }^{n} C_r \times r !$, i.e., $\quad{ }^{n} C_r=\frac{n !}{r !(n-r) !}$.

In particular, if $r=n,{ }^{n} C_n=\frac{n !}{n ! 0 !}=1$.

2. We define ${ }^{n} C_0=1$, i.e., the number of combinations of $n$ different things taken nothing at all is considered to be 1 . Counting combinations is merely counting the number of ways in which some or all objects at a time are selected. Selecting nothing at all is the same as leaving behind all the objects and we know that there is only one way of doing so. This way we define ${ }^{n} C_0=1$.

3. As $\frac{n !}{0 !(n-0) !}=1={ }^{n} C_0$, the formula ${ }^{n} C_r=\frac{n !}{r !(n-r) !}$ is applicable for $r=0$ also.

Hence

$ { }^{n} C_r=\frac{n !}{r !(n-r) !}, 0 \leq r \leq n . $

4. $\quad{ }^{n} C _{n-r}=\frac{n !}{(n-r) !(n-(n-r)) !}=\frac{n !}{(n-r) ! r !}={ }^{n} C_r$, i.e., selecting $r$ objects out of $n$ objects is same as rejecting $(n-r)$ objects.

5. $\quad{ }^{n} C_a={ }^{n} C_b \Rightarrow a=b$ or $a=n-b$, i.e., $n=a+b$

Theorem 6 ${ }^{n} C_r+{ }^{n} C _{r-1}={ }^{n+1} C_r$

Proof We have $\quad{ }^{n} C_r+{ }^{n} C _{r-1}=\frac{n !}{r !(n-r) !}+\frac{n !}{(r-1) !(n-r+1) !}$

$ \begin{aligned} & =\frac{n !}{r \times(r-1) !(n-r) !}+\frac{n !}{(r-1) !(n-r+1)(n-r) !} \\ & =\frac{n !}{(r-1) !(n-r) !}[\frac{1}{r}+\frac{1}{n-r+1}] \\ & =\frac{n !}{(r-1) !(n-r) !} \times \frac{n-r+1+r}{r(n-r+1)}=\frac{(n+1) !}{r !(n+1-r) !}={ }^{n+1} C_r \end{aligned} $

Summary

• Fundamental principle of counting If an event can occur in $m$ different ways, following which another event can occur in $n$ different ways, then the total number of occurrence of the events in the given order is $m \times n$.

• The number of permutations of $n$ different things taken $r$ at a time, where repetition is not allowed, is denoted by ${ }^{n} P_r$ and is given by ${ }^{n} P_r=\frac{n !}{(n-r) !}$, where $0 \leq r \leq n$.

• $n !=1 \times 2 \times 3 \times \ldots \times n$

• $n !=n \times(n-1)$ !

• The number of permutations of $n$ different things, taken $r$ at a time, where repeatition is allowed, is $n^{r}$.

• $\diamond$ The number of permutations of $n$ objects taken all at a time, where $p_1$ objects are of first kind, $p_2$ objects are of the second kind, $\ldots, p_k$ objects are of the $k^{\text{th }}$ kind and rest, if any, are all different is $\frac{n !}{p_1 ! p_2 ! \ldots p_k !}$.

• The number of combinations of $n$ different things taken $r$ at a time, denoted by ${ }^{n} C_r$, is given by ${ }^{n} C_r==\frac{n !}{r !(n-r) !}, 0 \leq r \leq n$.

Historical Note

The concepts of permutations and combinations can be traced back to the advent of Jainism in India and perhaps even earlier. The credit, however, goes to the Jains who treated its subject matter as a self-contained topic in mathematics, under the name Vikalpa.

Among the Jains, Mahavira, (around 850) is perhaps the world’s first mathematician credited with providing the general formulae for permutations and combinations.

In the 6th century B.C., Sushruta, in his medicinal work, Sushruta Samhita, asserts that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc. Pingala, a Sanskrit scholar around third century B.C., gives the method of determining the number of combinations of a given number of letters, taken one at a time, two at a time, etc. in his work Chhanda Sutra. Bhaskaracharya (born 1114) treated the subject matter of permutations and combinations under the name Anka Pasha in his famous work Lilavati. In addition to the general formulae for ${ }^{n} C_r$ and ${ }^{n} P_r$ already provided by Mahavira, Bhaskaracharya gives several important theorems and results concerning the subject.

Outside India, the subject matter of permutations and combinations had its humble beginnings in China in the famous book I-King (Book of changes). It is difficult to give the approximate time of this work, since in 213 B.C., the emperor had ordered all books and manuscripts in the country to be burnt which fortunately was not completely carried out. Greeks and later Latin writers also did some scattered work on the theory of permutations and combinations.

Some Arabic and Hebrew writers used the concepts of permutations and combinations in studying astronomy. Rabbi ben Ezra, for instance, determined the number of combinations of known planets taken two at a time, three at a time and so on. This was around 1140. It appears that Rabbi ben Ezra did not know the formula for ${ }^{n} C_r$. However, he was aware that ${ }^{n} C_r={ }^{n} C _{n-r}$ for specific values $n$ and $r$. In 1321, Levi Ben Gerson, another Hebrew writer came up with the formulae for ${ }^{n} P_r,{ }^{n} P_n$ and the general formula for ${ }^{n} C_r$.

The first book which gives a complete treatment of the subject matter of permutations and combinations is Ars Conjectandi written by a Swiss, Jacob Bernoulli (1654 - 1705), posthumously published in 1713. This book contains essentially the theory of permutations and combinations as is known today.