Chapter-06 Permutations and Combinations

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.

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.

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.

Example 1 Find the number of 4 letter words, with or without meaning, which can be formed out of the letters of the word ROSE, where the repetition of the letters is not allowed.

Solution There are as many words as there are ways of filling in 4 vacant places $\square \square \square \square$ by the 4 letters, keeping in mind that the repetition is not allowed. The first place can be filled in 4 different ways by anyone of the 4 letters R,O,S,E. Following which, the second place can be filled in by anyone of the remaining 3 letters in 3 different ways, following which the third place can be filled in 2 different ways; following which, the fourth place can be filled in 1 way. Thus, the number of ways in which the 4 places can be filled, by the multiplication principle, is $4 \times 3 \times 2 \times 1=24$. Hence, the required number of words is 24 .

Note - If the repetition of the letters was allowed, how many words can be formed? One can easily understand that each of the 4 vacant places can be filled in succession in 4 different ways. Hence, the required number of words $=4 \times 4 \times 4 \times 4=256$.

Example 2 Given 4 flags of different colours, how many different signals can be generated, if a signal requires the use of 2 flags one below the other?

Solution There will be as many signals as there are ways of filling in 2 vacant places $\begin{array}{|l|} \hline \quad \\ \hline \\ \hline \end{array}$ in succession by the 4 flags of different colours. The upper vacant place can be filled in 4 different ways by anyone of the 4 flags; following which, the lower vacant place can be filled in 3 different ways by anyone of the remaining 3 different flags. Hence, by the multiplication principle, the required number of signals $=4 \times 3=12$.

Example 3 How many 2 digit even numbers can be formed from the digits $1,2,3,4,5$ if the digits can be repeated?

Solution There will be as many ways as there are ways of filling 2 vacant places $\square \square$ in succession by the five given digits. Here, in this case, we start filling in unit’s place, because the options for this place are 2 and 4 only and this can be done in 2 ways; following which the ten’s place can be filled by any of the 5 digits in 5 different ways as the digits can be repeated. Therefore, by the multiplication principle, the required number of two digits even numbers is $2 \times 5$, i.e., 10 .

Example 4 Find the number of different signals that can be generated by arranging at least 2 flags in order (one below the other) on a vertical staff, if five different flags are available.

Solution A signal can consist of either 2 flags, 3 flags, 4 flags or 5 flags. Now, let us count the possible number of signals consisting of 2 flags, 3 flags, 4 flags and 5 flags separately and then add the respective numbers.

There will be as many 2 flag signals as there are ways of filling in 2 vacant places $\begin{array}{|l|} \hline \quad \\ \hline \\ \hline \end{array}$ in succession by the 5 flags available. By Multiplication rule, the number of ways is $5 \times 4=20$.

Similarly, there will be as many 3 flag signals as there are ways of filling in 3 vacant places $\begin{array}{|l|} \hline \quad \\ \hline \\ \hline \\ \hline \end{array}$ in succession by the 5 flags.

The number of ways is $5 \times 4 \times 3=60$.

Continuing the same way, we find that

The number of 4 flag signals $=5 \times 4 \times 3 \times 2=120$

and the number of 5 flag signals $=5 \times 4 \times 3 \times 2 \times 1=120$

Therefore, the required no of signals $=20+60+120+120=320$.

EXERCISE 6.1

1. How many 3-digit numbers can be formed from the digits 1, 2, 3, 4 and 5 assuming that

(i) repetition of the digits is allowed?

(ii) repetition of the digits is not allowed?

Show Answer

Answer :

(i) There will be as many ways as there are ways of filling 3 vacant places

$ \begin{array}{|c|c|c|} \hline & & \\ \hline \end{array} $

in succession by the given five digits. In this case, repetition of digits is allowed. Therefore, the units place can be filled in by any of the given five digits. Similarly, tens and hundreds digits can be filled in by any of the given five digits.

Thus, by the multiplication principle, the number of ways in which three-digit numbers can be formed from the given digits is $5 \times 5 \times 5=125$

(ii) In this case, repetition of digits is not allowed. Here, if units place is filled in first, then it can be filled by any of the given five digits. Therefore, the number of ways of filling the units place of the three-digit number is 5 .

Then, the tens place can be filled with any of the remaining four digits and the hundreds place can be filled with any of the remaining three digits.

Thus, by the multiplication principle, the number of ways in which three-digit numbers can be formed without repeating the given digits is $5 \times 4 \times 3=60$

2. How many 3-digit even numbers can be formed from the digits 1,2,3,4, 5, 6 if the digits can be repeated?

Show Answer

Answer :

There will be as many ways as there are ways of filling 3 vacant places

$\square \square \square$ in succession by the given six digits. In this case, the units place can be filled by 2 or 4 or 6 only i.e., the units place can be filled in 3 ways. The tens place can be filled by any of the 6 digits in 6 different ways and also the hundreds place can be filled by any of the 6 digits in 6 different ways, as the digits can be repeated.

Therefore, by multiplication principle, the required number of three digit even numbers is $3 \times 6 \times 6=108$

3. How many 4-letter code can be formed using the first 10 letters of the English alphabet, if no letter can be repeated?

Show Answer

Answer :

There are as many codes as there are ways of filling 4 vacant places $\square \square \square \square$ in succession by the first 10 letters of the English alphabet, keeping in mind that the repetition of letters is not allowed.

The first place can be filled in 10 different ways by any of the first 10 letters of the English alphabet following which, the second place can be filled in by any of the remaining letters in 9 different ways. The third place can be filled in by any of the remaining 8 letters in 8 different ways and the fourth place can be filled in by any of the remaining 7 letters in 7 different ways.

Therefore, by multiplication principle, the required numbers of ways in which 4 vacant places can be filled is $10 \times 9 \times 8 \times 7=5040$

Hence, 5040 four-letter codes can be formed using the first 10 letters of the English alphabet, if no letter is repeated.

4. How many 5-digit telephone numbers can be constructed using the digits 0 to 9 if each number starts with 67 and no digit appears more than once?

Show Answer

Answer :

It is given that the 5-digit telephone numbers always start with 67.

Therefore, there will be as many phone numbers as there are ways of filling 3 vacant places

$ \begin{array}{|c|c|c|} \hline 6 & 7\\ \hline \end{array} $

by the digits $0-9$, keeping in mind that the digits cannot be repeated.

The units place can be filled by any of the digits from 0 - 9, except digits 6 and 7 . Therefore, the units place can be filled in 8 different ways following which, the tens place can be filled in by any of the remaining 7 digits in 7 different ways, and the hundreds place can be filled in by any of the remaining 6 digits in 6 different ways.

Therefore, by multiplication principle, the required number of ways in which 5-digit telephone numbers can be constructed is $8 \times 7 \times 6=336$

5. A coin is tossed 3 times and the outcomes are recorded. How many possible outcomes are there?

Show Answer

Answer :

When a coin is tossed once, the number of outcomes is 2 (Head and tail) i.e., in each throw, the number of ways of showing a different face is 2 .

Thus, by multiplication principle, the required number of possible outcomes is $2 \times 2 \times 2=8$

6. Given 5 flags of different colours, how many different signals can be generated if each signal requires the use of 2 flags, one below the other?

Show Answer

Answer :

Each signal requires the use of 2 flags.

There will be as many flags as there are ways of filling in 2 vacant places $\square$ in succession by the given 5 flags of different colours.

The upper vacant place can be filled in 5 different ways by any one of the 5 flags following which, the lower vacant place can be filled in 4 different ways by any one of the remaining 4 different flags.

Thus, by multiplication principle, the number of different signals that can be generated is $5 \times 4=20$

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{array}{rlrl} 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{array} $$

and so on.

Example 5 Evaluate

(i) 5 !

(ii) 7 !

(iii) $7 !-5$ !

Solution

(i) $5 !=1 \times 2 \times 3 \times 4 \times 5=120$

(ii) 7 ! $=1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7=5040$

and

(iii) $7 !-5 !=5040-120=4920$.

Example 6 Compute (i) $\frac{7 !}{5 !}$

(ii) $\frac{12 !}{(10 !)(2 !)}$

Solution

(i) We have $\frac{7 !}{5 !}=\frac{7 \times 6 \times 5 !}{5 !}=7 \times 6=42$

and

(ii) $\frac{12 !}{(10 !)(2 !)}=\frac{12 \times 11 \times(10 !)}{(10 !) \times(2)}=6 \times 11=66$.

Example 7 Evaluate $\frac{n !}{r !(n-r) !}$, when $n=5, r=2$.

Solution We have to evaluate $\frac{5 !}{2 !(5-2) !}($ since $n=5, r=2)$

We have $\quad \frac{5 !}{2 !(5-2) !}=\frac{5 !}{2 ! \times 3 !}=\frac{5 \times 4}{2}=10$

Example 8 If $\frac{1}{8 !}+\frac{1}{9 !}=\frac{x}{10 !}$, find $x$.

Solution We have $\frac{1}{8 !}+\frac{1}{9 \times 8 !}=\frac{x}{10 \times 9 \times 8 !}$

Therefore $1+\frac{1}{9}=\frac{x}{10 \times 9}$ or $\frac{10}{9}=\frac{x}{10 \times 9}$

So

$ x=100 . $

EXERCISE 6.2

1. Evaluate

(i) 8 !

(ii) 4 ! -3 !

Show Answer

Answer :

(i) $8 !=1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8=40320$

(ii) 4 ! $=1 \times 2 \times 3 \times 4=24$

$3 !=1 \times 2 \times 3=6$

$\therefore 4$ ! - 3 ! $=24-6=18$

2. Is $3 !+4 !=7 !$ ?

Show Answer

Answer :

$3 !=1 \times 2 \times 3=6$

$4 !=1 \times 2 \times 3 \times 4=24$

$\therefore 3 !+4 !=6+24=30$

$7 !=1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7=5040$

$\therefore 3 !+4 ! \neq 7$ !

3. Compute $\dfrac{8 !}{6 ! \times 2 !}$

Show Answer

Answer :

$\dfrac{8 !}{6 ! \times 2 !}=\dfrac{8 \times 7 \times 6 !}{6 ! \times 2 \times 1}=\dfrac{8 \times 7}{2}=28$

4. If $\dfrac{1}{6 !}+\dfrac{1}{7 !}=\dfrac{x}{8 !}$, find $x$

Show Answer

Answer :

$\dfrac{1}{6 !}+\dfrac{1}{7 !}=\dfrac{x}{8 !}$

$\Rightarrow \dfrac{1}{6 !}+\dfrac{1}{7 \times 6 !}=\dfrac{x}{8 \times 7 \times 6 !}$

$\Rightarrow \dfrac{1}{6 !}(1+\dfrac{1}{7})=\dfrac{x}{8 \times 7 \times 6 !}$

$\Rightarrow 1+\dfrac{1}{7}=\dfrac{x}{8 \times 7}$

$\Rightarrow \dfrac{8}{7}=\dfrac{x}{8 \times 7}$

$\Rightarrow x=\dfrac{8 \times 8 \times 7}{7}$

$\therefore x=64$

5. Evaluate $\dfrac{n !}{(n-r) !}$, when

(i) $n=6, r=2$

(ii) $n=9, r=5$.

Show Answer

Answer :

(i) When $n=6, r=2, \dfrac{n !}{(n-r) !}=\dfrac{6 !}{(6-2) !}=\dfrac{6 !}{4 !}=\dfrac{6 \times 5 \times 4 !}{4 !}=30$

(ii) When $n=9, r=5, \dfrac{n !}{(n-r) !}=\dfrac{9 !}{(9-5) !}=\dfrac{9 !}{4 !}=\dfrac{9 \times 8 \times 7 \times 6 \times 5 \times 4 !}{4 !}$

$=9 \times 8 \times 7 \times 6 \times 5=15120$

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 !}$.

Example 9 Find the number of permutations of the letters of the word ALLAHABAD.

Solution Here, there are 9 objects (letters) of which there are 4A’s, 2 L’s and rest are all different.Therefore, the required number of arrangements

$$=\frac{9 !}{4 ! 2 !}=\frac{5 \times 6 \times 7 \times 8 \times 9}{2}=7560$$

Example 10 How many 4-digit numbers can be formed by using the digits 1 to 9 if repetition of digits is not allowed?

Solution Here order matters for example 1234 and 1324 are two different numbers. Therefore, there will be as many 4 digit numbers as there are permutations of 9 different digits taken 4 at a time.

Therefore, the required 4 digit numbers $={ }^{9} P_4=\frac{9 !}{(9-4) !}=\frac{9 !}{5 !}=9 \times 8 \times 7 \times 6=3024$.

Example 11 How many numbers lying between 100 and 1000 can be formed with the digits $0,1,2,3,4,5$, if the repetition of the digits is not allowed?

Solution Every number between 100 and 1000 is a 3-digit number. We, first, have to count the permutations of 6 digits taken 3 at a time. This number would be ${ }^{6} P_3$. But, these permutations will include those also where 0 is at the 100 ’s place. For example, $092,042, \ldots$, etc are such numbers which are actually 2 -digit numbers and hence the number of such numbers has to be subtracted from ${ }^{6} P_3$ to get the required number. To get the number of such numbers, we fix 0 at the 100 ’s place and rearrange the remaining 5 digits taking 2 at a time. This number is ${ }^{5} P_2$. So

The required number $\quad={ }^{6} P_3-{ }^{5} P_2=\frac{6 !}{3 !}-\frac{5 !}{3 !}$

$ =4 \times 5 \times 6-4 \times 5=100 $

Example 12 Find the value of $n$ such that (i) ${ }^{n} P_5=42{ }^{n} P_3, n>4$ (ii) $\frac{{ }^{n} P_4}{{ }^{n-1} P_4}=\frac{5}{3}, n>4$

Solution (i) Given that

$$ { }^{n} \mathrm{P} _{5}=42{ }^{n} \mathrm{P} _{3} $$

or $\quad \quad \quad \quad$ $n(n-1)(n-2)(n-3)(n-4)=42 n(n-1)(n-2)$

Since $\quad \quad \quad \quad$ $n>4 \quad$ so $n(n-1)(n-2) \neq 0$

Therefore, by dividing both sides by $n(n-1)(n-2)$, we get

$$\begin{array}{ll} {} & (n-3(n-4)=42 \\ \text{or}\quad\quad & n^{2}-7 n-30=0 \\ \text{or} & n^{2}-10 n+3 n-30 \\ \text{or} & (n-10)(n+3)=0 \\ \text{or} & n-10=0 \text{ or } \quad n+3=0 \\ \text{or} & n=10 \quad \text{ or } \quad n=-3 \end{array}$$

As $n$ cannot be negative, so $n=10$.

(ii) Given that $\frac{{ }^{n} P _4}{{ }^{n-1} P _4}=\frac{5}{3}$

Therefore $\quad \quad 3 n(n-1)(n-2)(n-3)=5(n-1)(n-2)(n-3)(n-4)$

or $\quad \quad3 n=5(n-4) \quad[$ as $(n-1)(n-2)(n-3) \neq 0, n>4]$

or $\quad \quad n=10$.

Example 13 Find $r$, if $5{ }^{4} P_r=6{ }^{5} P _{r-1}$.

Solution We have $5{ }^{4} P_r=6{ }^{5} P _{r-1}$

or $ \quad\quad5 \times \frac{4 !}{(4-r) !}=6 \times \frac{5 !}{(5-r+1) !} $

or $ \quad\quad\frac{5 !}{(4-r) !}=\frac{6 \times 5 !}{(5-r+1)(5-r)(5-r-1) !} $

or $\quad(6-r)(5-r)=6$

or $\quad r^{2}-11 r+24=0$

or $\quad r^{2}-8 r-3 r+24=0$

or $\quad(r-8)(r-3)=0$

or $\quad r=8$ or $r=3$.

Hence $\quad r=8,3$.

Example 14 Find the number of different 8-letter arrangements that can be made from the letters of the word DAUGHTER so that

(i) all vowels occur together

(ii) all vowels do not occur together.

Solution (i) There are 8 different letters in the word DAUGHTER, in which there are 3 vowels, namely, A, U and E. Since the vowels have to occur together, we can for the time being, assume them as a single object (AUE). This single object together with 5 remaining letters (objects) will be counted as 6 objects. Then we count permutations of these 6 objects taken all at a time. This number would be ${ }^{6} P_6=6$ !. Corresponding to each of these permutations, we shall have 3 ! permutations of the three vowels A, U, E taken all at a time . Hence, by the multiplication principle the required number of permutations $=6 ! \times 3 !=4320$.

(ii) If we have to count those permutations in which all vowels are never together, we first have to find all possible arrangments of 8 letters taken all at a time, which can be done in 8 ! ways. Then, we have to subtract from this number, the number of permutations in which the vowels are always together.

Therefore, the required number

$$ \begin{aligned} 8 !-6 ! \times 3 ! & =6 !(7 \times 8-6) \\ & =2 \times 6 !(28-3) \\ & =50 \times 6 !=50 \times 720=36000 \end{aligned} $$

Example 15 In how many ways can 4 red, 3 yellow and 2 green discs be arranged in a row if the discs of the same colour are indistinguishable?

Solution Total number of discs are $4+3+2=9$. Out of 9 discs, 4 are of the first kind (red), 3 are of the second kind (yellow) and 2 are of the third kind (green).

Therefore, the number of arrangements $\frac{9 !}{4 ! 3 ! 2 !}=1260$.

Example 16 Find the number of arrangements of the letters of the word INDEPENDENCE. In how many of these arrangements,

(i) do the words start with $P$

(ii) do all the vowels always occur together

(iii) do the vowels never occur together

(iv) do the words begin with I and end in P?

Solution There are 12 letters, of which $N$ appears 3 times, $E$ appears 4 times and D appears 2 times and the rest are all different. Therefore

The required number of arrangements $=\frac{12 !}{3 ! 4 ! 2 !}=1663200$

(i) Let us fix $P$ at the extreme left position, we, then, count the arrangements of the remaining 11 letters. Therefore, the required number of words starting with $P$

$$ =\frac{11 !}{3 ! 2 ! 4 !}=138600 $$

(ii) There are 5 vowels in the given word, which are 4 Es and 1 I. Since, they have to always occur together, we treat them as a single object EEEEI for the time being. This single object together with 7 remaining objects will account for 8 objects. These 8 objects, in which there are $3 Ns$ and $2 Ds$, can be rearranged in $8 !$ $\overline{3 ! 2 !}$ ways. Corresponding to each of these arrangements, the 5 vowels E, E, E, E and I can be rearranged in $\frac{5 !}{4 !}$ ways. Therefore, by multiplication principle, the required number of arrangements

$$ =\frac{8 !}{3 ! 2 !} \times \frac{5 !}{4 !}=16800 $$

(iii) The required number of arrangements $=$ the total number of arrangements (without any restriction) - the number of arrangements where all the vowels occur together.

$$ =1663200-16800=1646400 $$

(iv) Let us fix I and P at the extreme ends (I at the left end and P at the right end). We are left with 10 letters.

Hence, the required number of arrangements $ =\frac{10 !}{3 ! 2 ! 4 !}=12600 $

EXERCISE 6.3

1. How many 3-digit numbers can be formed by using the digits 1 to 9 if no digit is repeated?

Show Answer

Answer :

3-digit numbers have to be formed using the digits 1 to 9 .

Here, the order of the digits matters.

Therefore, there will be as many 3-digit numbers as there are permutations of 9 different digits taken 3 at a time.

Therefore, required number of 3-digit numbers

$ ={ }^{9} P_3=\dfrac{9 !}{(9-3) !}=\dfrac{9 !}{6 !} $

$=\dfrac{9 \times 8 \times 7 \times 6 !}{6 !}=9 \times 8 \times 7=504$

2. How many 4-digit numbers are there with no digit repeated?

Show Answer

Answer :

There are four places for the digits in a 4-digit number: thousands, hundreds, tens, and units. We can fill these places one by one following these constraints:

1. Thousands place: The digit cannot be zero, because then the number would become a 3-digit number. So, there are 9 choices $(1, 2, 3, 4, 5, 6, 7, 8, 9)$ for the thousands place.

2. Hundreds place: Since no digit can be repeated, there are only $9$ digits remaining to fill the hundreds place.

3. Tens place: After filling the thousands and hundreds places, there are 8 digits remaining to fill the tens place.

4. Units place: Finally, there are $7$ digits remaining to fill the units place.

By the fundamental counting principle, the total number of unique 4-digit numbers possible is the product of the number of choices at each place:

Total numbers = Choices (thousands) × Choices (hundreds) × Choices (tens) × Choices (units) $= 9 × 9 × 8 × 7$

Therefore, there are $4536$ ($9$ x $504)$ different 4-digit numbers that can be formed with no digits repeated.

3. How many 3-digit even numbers can be made using the digits $1,2,3,4,6,7$, if no digit is repeated?

Show Answer

Answer :

3-digit even numbers are to be formed using the given six digits, 1, 2, 3, 4, 6, and 7, without repeating the digits.

Then, units digits can be filled in 3 ways by any of the digits, 2, 4, or 6 .

Since the digits cannot be repeated in the 3-digit numbers and units place is already occupied with a digit (which is even), the hundreds and tens place is to be filled by the remaining 5 digits.

Therefore, the number of ways in which hundreds and tens place can be filled with the remaining 5 digits is the permutation of 5 different digits taken 2 at a time.

Number of ways of filling hundreds and tens place

$ ={ }^{5} P_2=\dfrac{5 !}{(5-2) !}=\dfrac{5 !}{3 !} $

$=\dfrac{5 \times 4 \times 3 !}{3 !}=20$

Thus, by multiplication principle, the required number of 3-digit numbers is

$3 \times 20=60$

4. Find the number of 4-digit numbers that can be formed using the digits 1,2,3,4, 5 if no digit is repeated. How many of these will be even?

Show Answer

Answer :

4-digit numbers are to be formed using the digits, 1, 2, 3, 4, and 5 .

There will be as many 4-digit numbers as there are permutations of 5 different digits taken 4 at a time.

Therefore, required number of 4 digit numbers $=$

$ { }^{5} P_4=\dfrac{5 !}{(5-4) !}=\dfrac{5 !}{1 !} $

$=1 \times 2 \times 3 \times 4 \times 5=120$

Among the 4-digit numbers formed by using the digits, 1, 2, 3, 4, 5, even numbers end with either 2 or 4 .

The number of ways in which units place is filled with digits is 2 .

Since the digits are not repeated and the units place is already occupied with a digit (which is even), the remaining places are to be filled by the remaining 4 digits.

Therefore, the number of ways in which the remaining places can be filled is the permutation of 4 different digits taken 3 at a time.

Number of ways of filling the remaining places

$ ={ }^{4} P_3=\dfrac{4 !}{(4-3) !}=\dfrac{4 !}{1 !} $

$=4 \times 3 \times 2 \times 1=24$

Thus, by multiplication principle, the required number of even numbers is

$24 \times 2=48$

5. From a committee of 8 persons, in how many ways can we choose a chairman and a vice chairman assuming one person can not hold more than one position?

Show Answer

Answer :

From a committee of 8 persons, a chairman and a vice chairman are to be chosen in such a way that one person cannot hold more than one position.

Here, the number of ways of choosing a chairman and a vice chairman is the permutation of 8 different objects taken 2 at a time.

Thus, required number of ways $=$

$ ={ }^{8} P_2=\dfrac{8 !}{(8-2) !}=\dfrac{8 !}{6 !}=\dfrac{8 \times 7 \times 6 !}{6 !}=8 \times 7=56 $

6. Find $n$ if ${ }^{n-1} P_3:{ }^{n} P_4=1: 9$.

Show Answer

Answer :

$ \begin{aligned} & { }^{n-1} P_3:{ }^{n} P_4=1: 9 \\ & \Rightarrow \dfrac{{ }^{n-1} P_3}{{ }^{n} P_4}=\dfrac{1}{9} \\ & \Rightarrow \dfrac{[\dfrac{(n-1) !}{(n-1-3) !}]}{[\dfrac{n !}{(n-4) !}]}=\dfrac{1}{9} \\ & \Rightarrow \dfrac{(n-1) !}{(n-4) !} \times \dfrac{(n-4) !}{n !}=\dfrac{1}{9} \\ & \Rightarrow \dfrac{(n-1) !}{n \times(n-1) !}=\dfrac{1}{9} \\ & \Rightarrow \dfrac{1}{n}=\dfrac{1}{9} \\ & \therefore n=9 \end{aligned} $

7. Find $r$ if (i) ${ }^{5} P_r=2{ }^{6} P _{r-1}$ (ii) ${ }^{5} P_r={ }^{6} P _{r-1}$.

Show Answer

Answer:

(i)

$ \begin{aligned} & { }^{5} P_r=2^{6} P _{r-1} \\ & \Rightarrow \dfrac{5 !}{(5-r) !}=2 \times \dfrac{6 !}{(6-r+1) !} \\ & \Rightarrow \dfrac{5 !}{(5-r) !}=\dfrac{2 \times 6 !}{(7-r) !} \\ & \Rightarrow \dfrac{5 !}{(5-r) !}=\dfrac{2 \times 6 \times 5 !}{(7-r)(6-r)(5-r) !} \\ & \Rightarrow 1=\dfrac{2 \times 6}{(7-r)(6-r)} \\ & \Rightarrow(7-r)(6-r)=12 \end{aligned} $

$ \begin{aligned} & \Rightarrow 42-6 r-7 r+r^{2}=12 \\ & \Rightarrow r^{2}-13 r+30=0 \\ & \Rightarrow r^{2}-3 r-10 r+30=0 \\ & \Rightarrow r(r-3)-10(r-3)=0 \\ & \Rightarrow(r-3)(r-10)=0 \\ & \Rightarrow(r-3)=0 \text{ or }(r-10)=0 \\ & \Rightarrow r=3 \text{ or } r=10 \end{aligned} $

It is known that,

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

$\therefore 0 \leq r \leq 5$

Hence, $r \neq 10$

$\therefore r=3$

(ii)

$ \begin{aligned} & { }^{5} P_r={ }^{6} P _{r-1} \\ & \Rightarrow \dfrac{5 !}{(5-r) !}=\dfrac{6 !}{(6-r+1) !} \\ & \Rightarrow \dfrac{5 !}{(5-r) !}=\dfrac{6 \times 5 !}{(7-r) !} \\ & \Rightarrow \dfrac{1}{(5-r) !}=\dfrac{6}{(7-r)(6-r)(5-r) !} \\ & \Rightarrow 1=\dfrac{6}{(7-r)(6-r)} \\ & \Rightarrow(7-r)(6-r)=6 \\ & \Rightarrow 42-7 r-6 r+r^{2}-6=0 \\ & \Rightarrow r^{2}-13 r+36=0 \\ & \Rightarrow r^{2}-4 r-9 r+36=0 \\ & \Rightarrow r(r-4)-9(r-4)=0 \\ & \Rightarrow(r-4)(r-9)=0 \\ & \Rightarrow(r-4)=0 \text{ or }(r-9)=0 \\ & \Rightarrow r=4 \text{ or } r=9 \end{aligned} $

It is known that,

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

Hence, $r \neq 9$

$\therefore r=4$

8. How many words, with or without meaning, can be formed using all the letters of the word EQUATION, using each letter exactly once?

Show Answer

Answer :

There are 8 different letters in the word EQUATION.

Therefore, the number of words that can be formed using all the letters of the word EQUATION, using each letter exactly once, is the number of permutations of 8 different objects taken 8 at a time, which is ${ }^{8} P_8=8$ !.

Thus, required number of words that can be formed $=8 !=40320$

9. How many words, with or without meaning can be made from the letters of the word MONDAY, assuming that no letter is repeated, if.

(i) 4 letters are used at a time,

(ii) all letters are used at a time,

(iii) all letters are used but first letter is a vowel?

Show Answer

Answer :

There are 6 different letters in the word MONDAY.

(i) Number of 4-letter words that can be formed from the letters of the word MONDAY, without repetition of letters, is the number of permutations of 6 different objects taken 4 at a time, which is ${ }^{6} P_4$.

Thus, required number of words that can be formed using 4 letters at a time is

$ { }^{6} P_4=\dfrac{6 !}{(6-4) !}=\dfrac{6 !}{2 !}=\dfrac{6 \times 5 \times 4 \times 3 \times 2 !}{2 !}=6 \times 5 \times 4 \times 3=360 $

(ii) Number of words that can be formed by using all the letters of the word MONDAY at a time is the number of permutations of 6 different objects taken 6 at a time, which is ${ }^{6} P_6=6$ !

Thus, required number of words that can be formed when all letters are used at a time $=6 !=6 \times 5 \times 4 \times 3 \times 2 \times 1=$ 720

(iii) In the given word, there are 2 different vowels, which have to occupy the rightmost place of the words formed. This can be done only in 2 ways.

Since the letters cannot be repeated and the rightmost place is already occupied with a letter (which is a vowel), the remaining five places are to be filled by the remaining 5 letters. This can be done in 5 ! ways.

Thus, in this case, required number of words that can be formed is

$5 ! \times 2=120 \times 2=240$

10. In how many of the distinct permutations of the letters in MISSISSIPPI do the four I’s not come together?

Show Answer

Answer :

In the given word MISSISSIPPI, I appears 4 times, S appears 4 times, P appears 2 times, and M appears just once. Therefore, number of distinct permutations of the letters in the given word

$ \begin{aligned} & =\dfrac{11 !}{4 ! 4 ! 2 !} \\ & =\dfrac{11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 !}{4 ! \times 4 \times 3 \times 2 \times 1 \times 2 \times 1} \\ & =\dfrac{11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1 \times 2 \times 1} \\ & =34650 \end{aligned} $

There are 4 Is in the given word. When they occur together, they are treated as a single object IIII for the time being. This single object together with the remaining 7 objects will account for 8 objects.

These 8 objects in which there are 4 Ss and 2 Ps can be arranged in $\dfrac{8 !}{4 ! 2 !}$ ways i.e., 840 ways.

Number of arrangements where all Is occur together $=840$

Thus, number of distinct permutations of the letters in MISSISSIPPI in which four Is do not come together $=34650$-$840=33810$

11. In how many ways can the letters of the word PERMUTATIONS be arranged if the

(i) words start with $P$ and end with $S$,

(ii) vowels are all together,

(iii) there are always 4 letters between $P$ and $S$ ?

Show Answer

Answer :

In the word PERMUTATIONS, there are $2 Ts$ and all the other letters appear only once.

(i) If $P$ and $S$ are fixed at the extreme ends ( $P$ at the left end and $S$ at the right end), then 10 letters are left.

Hence, in this case, required number of arrangements

$ =\dfrac{10 !}{2 !}=1814400 $

(ii) There are 5 vowels in the given word, each appearing only once.

Since they have to always occur together, they are treated as a single object for the time being. This single object together with the remaining 7 objects will account for 8 objects. These 8 objects in which there are 2 Ts can be

arranged in $\dfrac{8 !}{2 !}$ ways .

Corresponding to each of these arrangements, the 5 different vowels can be arranged in 5 ! ways.

Therefore, by multiplication principle, required number of arrangements in this case $=\dfrac{8 !}{2 !} \times 5 !=2419200$

(iii) The letters have to be arranged in such a way that there are always 4 letters between $P$ and $S$.

Therefore, in a way, the places of $P$ and $S$ are fixed. The remaining 10 letters in which there are $2 Ts$ can be arranged in $\dfrac{10 !}{2 !}$ ways

Also, the letters $P$ and $S$ can be placed such that there are 4 letters between them in $2 \times 7=14$ ways.

Therefore, by multiplication principle, required number of arrangements in this case

$ =\dfrac{10 !}{2 !} \times 14=25401600 $

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} $$

Example 17 If ${ }^{n} C_9={ }^{n} C_8$, find ${ }^{n} C _{17}$.

Solution We have ${ }^{n} C_9={ }^{n} C_8$

i.e., $\quad \frac{n !}{9 !(n-9) !}=\frac{n !}{(n-8) ! 8 !}$

or $ \quad\quad\quad \frac{1}{9}=\frac{1}{n-8} \text{ or } n-8=9 \text{ or } n=17 $

Therefore $ \quad \quad { }^{n} C _{17}={ }^{17} C _{17}=1 . $

Example 18 A committee of 3 persons is to be constituted from a group of 2 men and 3 women. In how many ways can this be done? How many of these committees would consist of 1 man and 2 women?

Solution Here, order does not matter. Therefore, we need to count combinations. There will be as many committees as there are combinations of 5 different persons taken 3 at a time. Hence, the required number of ways $={ }^{5} C_3=\frac{5 !}{3 ! 2 !}=\frac{4 \times 5}{2}=10$.

Now, 1 man can be selected from 2 men in ${ }^{2} C_1$ ways and 2 women can be selected from 3 women in ${ }^{3} C_2$ ways. Therefore, the required number of committees

$$ ={ }^{2} C_1 \times{ }^{3} C_2=\frac{2 !}{1 ! 1 !} \times \frac{3 !}{2 ! 1 !}=6 $$

Example 19 What is the number of ways of choosing 4 cards from a pack of 52 playing cards? In how many of these

(i) four cards are of the same suit,

(ii) four cards belong to four different suits,

(iii) are face cards,

(iv) two are red cards and two are black cards,

(v) cards are of the same colour?

Solution There will be as many ways of choosing 4 cards from 52 cards as there are combinations of 52 different things, taken 4 at a time. Therefore The required number of ways

$$ ={ }^{52} \mathrm{C}_{4}=\frac{52 !}{4 ! 48 !}=\frac{49 \times 50 \times 51 \times 52}{2 \times 3 \times 4}=270725 $$

(i) There are four suits: diamond, club, spade, heart and there are 13 cards of each suit. Therefore, there are ${ }^{13} C_4$ ways of choosing 4 diamonds. Similarly, there are ${ }^{13} C_4$ ways of choosing 4 clubs, ${ }^{13} C_4$ ways of choosing 4 spades and ${ }^{13} C_4$ ways of choosing 4 hearts. Therefore

The required number of ways $={ }^{13} C_4+{ }^{13} C_4+{ }^{13} C_4+{ }^{13} C_4$.

$$ =4 \times \frac{13 !}{4 ! 9 !}=2860 $$

(ii) There are13 cards in each suit. Therefore, there are ${ }^{13} C_1$ ways of choosing 1 card from 13 cards of diamond, ${ }^{13} C_1$ ways of choosing 1 card from 13 cards of hearts, ${ }^{13} C_1$ ways of choosing 1 card from 13 cards of clubs, ${ }^{13} C_1$ ways of choosing 1 card from 13 cards of spades. Hence, by multiplication principle, the required number of ways

$$ ={ }^{13} C_1 \times{ }^{13} C_1 \times{ }^{13} C_1 \times{ }^{13} C_1=13^{4} $$

(iii) There are 12 face cards and 4 are to be selected out of these 12 cards. This can be done in ${ }^{12} C_4$ ways. Therefore, the required number of ways $=\frac{12 !}{4 ! 8 !}=495$.

(iv) There are 26 red cards and 26 black cards. Therefore, the required number of ways

$$ \begin{aligned} & ={ }^{26} \mathrm{C} _{2} \times{ }^{26} \mathrm{C} _{2} \\ & =\frac{26 !}{2 ! 24 !}^{2}=(325)^{2}=105625 \end{aligned} $$

(v) 4 red cards can be selected out of 26 red cards in ${ }^{26} C_4$ ways. 4 black cards can be selected out of 26 black cards in ${ }^{26} C_4$ ways.

Therefore, the required number of ways $={ }^{26} C_4+{ }^{26} C_4$ $$ =2 \times \frac{26 !}{4 ! 22 !}=29900 . $$

EXERCISE 6.4

1. If ${ }^{n} C_8={ }^{n} C_2$, find ${ }^{n} C_2$.

Show Answer

Answer :

It is known that, ${ }^{n} C_a={ }^{n} C_b \Rightarrow a=b$ or $n=a+b$

Therefore,

$ \begin{aligned} & { }^{n} C_8={ }^{n} C_2 \Rightarrow n=8+2=10 \\ & \therefore{ }^{n} C_2={ }^{10} C_2=\dfrac{10 !}{2 !(10-2) !}=\dfrac{10 !}{2 ! 8 !}=\dfrac{10 \times 9 \times 8 !}{2 \times 1 \times 8 !}=45 \end{aligned} $

2. Determine $n$ if

(i) ${ }^{2 n} C_3:{ }^{n} C_3=12: 1$

(ii) ${ }^{2 n} C_3:{ }^{n} C_3=11: 1$

Show Answer

Answer :

(i)

$ \begin{aligned} & \dfrac{{ }^{2 n} C_3}{{ }^{n} C_3}=\dfrac{12}{1} \\ & \Rightarrow \dfrac{(2 n) !}{3 !(2 n-3) !} \times \dfrac{3 !(n-3) !}{n !}=\dfrac{12}{1} \\ & \Rightarrow \dfrac{(2 n)(2 n-1)(2 n-2)(2 n-3) !}{(2 n-3) !} \times \dfrac{(n-3) !}{n(n-1)(n-2)(n-3) !}=12 \\ & \Rightarrow \dfrac{2(2 n-1)(2 n-2)}{(n-1)(n-2)}=12 \\ & \Rightarrow \dfrac{4(2 n-1)(n-1)}{(n-1)(n-2)}=12 \\ & \Rightarrow \dfrac{(2 n-1)}{(n-2)}=3 \\ & \Rightarrow 2 n-1=3(n-2) \\ & \Rightarrow 2 n-1=3 n-6 \\ & \Rightarrow 3 n-2 n=-1+6 \\ & \Rightarrow n=5 \end{aligned} $

(ii)

$\dfrac{{ }^{2 n} C_3}{{ }^{n} C_3}=\dfrac{11}{1}$

$\Rightarrow \dfrac{(2 n) !}{3 !(2 n-3) !} \times \dfrac{3 !(n-3) !}{n !}=11$

$\Rightarrow \dfrac{(2 n)(2 n-1)(2 n-2)(2 n-3) !}{(2 n-3) !} \times \dfrac{(n-3) !}{n(n-1)(n-2)(n-3) !}=11$

$\Rightarrow \dfrac{2(2 n-1)(2 n-2)}{(n-1)(n-2)}=11$

$\Rightarrow \dfrac{4(2 n-1)(n-1)}{(n-1)(n-2)}=11$

$\Rightarrow \dfrac{4(2 n-1)}{n-2}=11$

$\Rightarrow 4(2 n-1)=11(n-2)$

$\Rightarrow 8 n-4=1 \ln -22$

$\Rightarrow 1 \ln -8 n=-4+22$

$\Rightarrow 3 n=18$

$\Rightarrow n=6$

3. How many chords can be drawn through 21 points on a circle?

Show Answer

Answer :

For drawing one chord on a circle, only 2 points are required.

To know the number of chords that can be drawn through the given 21 points on a circle, the number of combinations have to be counted.

Therefore, there will be as many chords as there are combinations of 21 points taken 2 at a time.

Thus, required number of chords $=$

$ { }^{21} C_2=\dfrac{21 !}{2 !(21-2) !}=\dfrac{21 !}{2 ! 19 !}=\dfrac{21 \times 20}{2}=210 $

4. In how many ways can a team of 3 boys and 3 girls be selected from 5 boys and 4 girls?

Show Answer

Answer :

A team of 3 boys and 3 girls is to be selected from 5 boys and 4 girls.

3 boys can be selected from 5 boys in ${ }^{5} C_3$ ways.

3 girls can be selected from 4 girls in ${ }^{4} C_3$ ways.

Therefore, by multiplication principle, number of ways in which a team of 3 boys and 3 girls can be

selected

$ ={ }^{5} C_3 \times{ }^{4} C_3=\dfrac{5 !}{3 ! 2 !} \times \dfrac{4 !}{3 ! 1 !} $

$=\dfrac{5 \times 4 \times 3 !}{3 ! \times 2} \times \dfrac{4 \times 3 !}{3 !}$

$=10 \times 4=40$

5. Find the number of ways of selecting 9 balls from 6 red balls, 5 white balls and 5 blue balls if each selection consists of 3 balls of each colour.

Show Answer

Answer :

There are a total of 6 red balls, 5 white balls, and 5 blue balls.

9 balls have to be selected in such a way that each selection consists of 3 balls of each colour.

Here,

3 balls can be selected from 6 red balls in ${ }^{6} C_3$ ways.

3 balls can be selected from 5 white balls in ${ }^{5} C_3$ ways.

3 balls can be selected from 5 blue balls in ${ }^{5} C_3$ ways.

Thus, by multiplication principle, required number of ways of selecting 9 balls

$ \begin{aligned} & ={ }^{6} C_3 \times{ }^{5} C_3 \times{ }^{5} C_3=\dfrac{6 !}{3 ! 3 !} \times \dfrac{5 !}{3 ! 2 !} \times \dfrac{5 !}{3 ! 2 !} \\ & =\dfrac{6 \times 5 \times 4 \times 3 !}{3 ! \times 3 \times 2} \times \dfrac{5 \times 4 \times 3 !}{3 ! \times 2 \times 1} \times \dfrac{5 \times 4 \times 3 !}{3 ! \times 2 \times 1} \\ & =20 \times 10 \times 10=2000 \end{aligned} $

6. Determine the number of 5 card combinations out of a deck of 52 cards if there is exactly one ace in each combination.

Show Answer

Answer :

In a deck of 52 cards, there are 4 aces. A combination of 5 cards have to be made in which there is exactly one ace.

Then, one ace can be selected in ${ }^{4} C_1$ ways and the remaining 4 cards can be selected out of the 48 cards in ${ }^{48} C_4$ ways.

$ \begin{aligned} & ={ }^{48} C_4 \times{ }^{4} C_1=\dfrac{48 !}{4 ! 44 !} \times \dfrac{4 !}{1 ! 3 !} \\ & =\dfrac{48 \times 47 \times 46 \times 45}{4 \times 3 \times 2 \times 1} \times 4 \end{aligned} $

Thus, by multiplication principle, required number of 5 card combinations $=778320$

7. In how many ways can one select a cricket team of eleven from 17 players in which only 5 players can bowl if each cricket team of 11 must include exactly 4 bowlers?

Show Answer

Answer :

Out of 17 players, 5 players are bowlers.

A cricket team of 11 players is to be selected in such a way that there are exactly 4 bowlers.

4 bowlers can be selected in ${ }^{5} C_4$ ways and the remaining 7 players can be selected out of the 12 players in ${ }^{12} C_7$ ways.

Thus, by multiplication principle, required number of ways of selecting cricket

$ \text{ team }={ }^{5} C_4 \times{ }^{12} C_7=\dfrac{5 !}{4 ! 1 !} \times \dfrac{12 !}{7 ! 5 !}=5 \times \dfrac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1}=3960 $

8. A bag contains 5 black and 6 red balls. Determine the number of ways in which 2 black and 3 red balls can be selected.

Show Answer

Answer :

There are 5 black and 6 red balls in the bag.

2 black balls can be selected out of 5 black balls in ${ }^{5} C_2$ ways and 3 red balls can be selected out of 6 red balls in ${ }^{6} C_3$ ways.

Thus, by multiplication principle, required number of ways of selecting 2 black and 3 red

balls $={ }^{5} C_2 \times{ }^{6} C_3=\dfrac{5 !}{2 ! 3 !} \times \dfrac{6 !}{3 ! 3 !}=\dfrac{5 \times 4}{2} \times \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1}=10 \times 20=200$

9. In how many ways can a student choose a programme of 5 courses if 9 courses are available and 2 specific courses are compulsory for every student?

Show Answer

Answer :

There are 9 courses available out of which, 2 specific courses are compulsory for every student.

Therefore, every student has to choose 3 courses out of the remaining 7 courses. This can be chosen in ${ }^{7} C_3$ ways. Thus, required number of ways of choosing the programme

$ ={ }^{7} C_3=\dfrac{7 !}{3 ! 4 !}=\dfrac{7 \times 6 \times 5 \times 4 !}{3 \times 2 \times 1 \times 4 !}=35 $

Miscellaneous Examples

Example 20 How many words, with or without meaning, each of 3 vowels and 2 consonants can be formed from the letters of the word INVOLUTE ?

Solution In the word INVOLUTE, there are 4 vowels, namely, I,O,E,Uand 4 consonants, namely, $N, V, L$ and $T$.

The number of ways of selecting 3 vowels out of $4={ }^{4} C_3=4$.

The number of ways of selecting 2 consonants out of $4={ }^{4} C_2=6$.

Therefore, the number of combinations of 3 vowels and 2 consonants is $4 \times 6=24$.

Now, each of these 24 combinations has 5 letters which can be arranged among themselves in 5 ! ways. Therefore, the required number of different words is $24 \times 5 !=2880$.

Example 21 A group consists of 4 girls and 7 boys. In how many ways can a team of 5 members be selected if the team has (i) no girl ? (ii) at least one boy and one girl ? (iii) at least 3 girls ?

Solution (i) Since, the team will not include any girl, therefore, only boys are to be selected. 5 boys out of 7 boys can be selected in ${ }^{7} C_5$ ways. Therefore, the required number of ways $={ }^{7} C_5=\frac{7 !}{5 ! 2 !}=\frac{6 \times 7}{2}=21$

(ii) Since, at least one boy and one girl are to be there in every team. Therefore, the team can consist of

(a) 1 boy and 4 girls

(b) 2 boys and 3 girls

(c) 3 boys and 2 girls

(d) 4 boys and 1 girl.

1 boy and 4 girls can be selected in ${ }^{7} C_1 \times{ }^{4} C_4$ ways.

2 boys and 3 girls can be selected in ${ }^{7} C_2 \times{ }^{4} C_3$ ways.

3 boys and 2 girls can be selected in ${ }^{7} C_3 \times{ }^{4} C_2$ ways.

4 boys and 1 girl can be selected in ${ }^{7} C_4 \times{ }^{4} C_1$ ways.

Therefore, the required number of ways

$ \begin{aligned} & ={ }^{7} C_1 \times{ }^{4} C_4+{ }^{7} C_2 \times{ }^{4} C_3+{ }^{7} C_3 \times{ }^{4} C_2+{ }^{7} C_4 \times{ }^{4} C_1 \\ & =7+84+210+140=441 \end{aligned} $

(iii) Since, the team has to consist of at least 3 girls, the team can consist of (a) 3 girls and 2 boys, or (b) 4 girls and 1 boy.

Note that the team cannot have all 5 girls, because, the group has only 4 girls.

3 girls and 2 boys can be selected in ${ }^{4} C_3 \times{ }^{7} C_2$ ways.

4 girls and 1 boy can be selected in ${ }^{4} C_4 \times{ }^{7} C_1$ ways.

Therefore, the required number of ways

$ ={ }^{4} C_3 \times{ }^{7} C_2+{ }^{4} C_4 \times{ }^{7} C_1=84+7=91 $

Example 22 Find the number of words with or without meaning which can be made using all the letters of the word AGAIN. If these words are written as in a dictionary, what will be the $50^{\text{th }}$ word?

Solution There are 5 letters in the word AGAIN, in which A appears 2 times. Therefore, the required number of words $=\frac{5 !}{2 !}=60$.

To get the number of words starting with A, we fix the letter A at the extreme left position, we then rearrange the remaining 4 letters taken all at a time. There will be as many arrangements of these 4 letters taken 4 at a time as there are permutations of 4 different things taken 4 at a time. Hence, the number of words starting with $A=4 !=24$. Then, starting with $G$, the number of words $=\frac{4 !}{2 !}=12$ as after placing $G$ at the extreme left position, we are left with the letters A, A, I and N. Similarly, there are 12 words starting with the next letter I. Total number of words so far obtained $=24+12+12=48$. The $49^{\text{th }}$ word is NAAGI. The $50^{\text{th }}$ word is NAAIG.

Example 23 How many numbers greater than 1000000 can be formed by using the digits $1,2,0,2,4,2,4$ ?

Solution Since, 1000000 is a 7-digit number and the number of digits to be used is also 7. Therefore, the numbers to be counted will be 7-digit only. Also, the numbers have to be greater than 1000000 , so they can begin either with 1,2 or 4 .

The number of numbers beginning with $1=\frac{6 !}{3 ! 2 !}=\frac{4 \times 5 \times 6}{2}=60$, as when 1 is fixed at the extreme left position, the remaining digits to be rearranged will be $0,2,2,2$, 4,4 , in which there are $3,2 s$ and $2,4 s$.

Total numbers begining with 2 $=\frac{6 !}{2 ! 2 !}=\frac{3 \times 4 \times 5 \times 6}{2}=180$

and total numbers begining with $4=\frac{6 !}{3 !}=4 \times 5 \times 6=120$

Therefore, the required number of numbers $=60+180+120=360$.

Alternative Method

The number of 7-digit arrangements, clearly, $\frac{7 !}{3 ! 2 !}=420$. But, this will include those numbers also, which have 0 at the extreme left position. The number of such arrangements $\frac{6 !}{3 ! 2 !}$ (by fixing 0 at the extreme left position) $=60$. Therefore, the required number of numbers $=420-60=360$.

Note - If one or more than one digits given in the list is repeated, it will be understood that in any number, the digits can be used as many times as is given in the list, e.g., in the above example 1 and 0 can be used only once whereas 2 and 4 can be used 3 times and 2 times, respectively.

Example 24 In how many ways can 5 girls and 3 boys be seated in a row so that no two boys are together?

Solution Let us first seat the 5 girls. This can be done in 5 ! ways. For each such arrangement, the three boys can be seated only at the cross marked places.

$$ \times G \times G \times G \times G \times G \times . $$

There are 6 cross marked places and the three boys can be seated in ${ }^{6} P_3$ ways. Hence, by multiplication principle, the total number of ways

$$ \begin{aligned} & =5 ! \times{ }^{6} P_3=5 ! \times \frac{6 !}{3 !} \\ & =4 \times 5 \times 2 \times 3 \times 4 \times 5 \times 6=14400 . \end{aligned} $$

Miscellaneous Exercise on Chapter 6

1. How many words, with or without meaning, each of 2 vowels and 3 consonants can be formed from the letters of the word DAUGHTER?

Show Answer

Answer :

In the word DAUGHTER, there are 3 vowels namely, A, U, and E, and 5 consonants namely, D, G, H, T, and R.

Number of ways of selecting 2 vowels out of 3 vowels $={ }^{3} C_2=3$

Number of ways of selecting 3 consonants out of 5 consonants $={ }^{5} C_3=10$

Therefore, number of combinations of 2 vowels and 3 consonants $=3 \times 10=30$

Each of these 30 combinations of 2 vowels and 3 consonants can be arranged among themselves in 5 ! ways.

Hence, required number of different words $=30 \times 5 !=3600$

2. How many words, with or without meaning, can be formed using all the letters of the word EQUATION at a time so that the vowels and consonants occur together?

Show Answer

Answer :

In the word EQUATION, there are 5 vowels, namely, $A, E, I, O$, and $U$, and 3 consonants, namely, Q, $T$, and $N$. Since all the vowels and consonants have to occur together, both (AEIOU) and (QTN) can be assumed as single objects. Then, the permutations of these 2 objects taken all at a time are counted. This number would be ${ }^{2} P_2=2$ ! Corresponding to each of these permutations, there are 5 ! permutations of the five vowels taken all at a time and 3 ! permutations of the 3 consonants taken all at a time.

Hence, by multiplication principle, required number of words $=2 ! \times 5 ! \times 3 !$

$=1440$

3. A committee of 7 has to be formed from 9 boys and 4 girls. In how many ways can this be done when the committee consists of:

(i) exactly 3 girls ?

(ii) atleast 3 girls ?

(iii) atmost 3 girls ?

Show Answer

Answer :

A committee of 7 has to be formed from 9 boys and 4 girls.

i. Since exactly 3 girls are to be there in every committee, each committee must consist of $(7-3)$ boys only.

Thus, in this case, required number of ways $=$

$ { }^{4} C_3 \times{ }^{9} C_4=\dfrac{4 !}{3 ! 1 !} \times \dfrac{9 !}{4 ! 5 !} $

$=4 \times \dfrac{9 \times 8 \times 7 \times 6 \times 5 !}{4 \times 3 \times 2 \times 1 \times 5 !}$

$=504$

(ii) Since at least 3 girls are to be there in every committee, the committee can consist of

(a) 3 girls and 4 boys or (b) 4 girls and 3 boys

3 girls and 4 boys can be selected in ${ }^{4} C_3 \times{ }^{9} C_4$ ways.

4 girls and 3 boys can be selected in ${ }^{4} C_4 \times{ }^{9} C_3$ ways.

Therefore, in this case, required number of ways $={ }^{4} C_3 \times{ }^{9} C_4+{ }^{4} C_4 \times{ }^{9} C_3$ $=504+84=588$

(iii) Since atmost 3 girls are to be there in every committee, the committee can consist of

(a) 3 girls and 4 boys (b) 2 girls and 5 boys

(c) 1 girl and 6 boys (d) No girl and 7 boys

3 girls and 4 boys can be selected in ${ }^{4} C_3 \times{ }^{9} C_4$ ways.

2 girls and 5 boys can be selected in ${ }^{4} C_2 \times{ }^{9} C_5$ ways.

1 girl and 6 boys can be selected in ${ }^{4} C_1 \times{ }^{9} C_6$ ways.

No girl and 7 boys can be selected in ${ }^{4} C_0 \times{ }^{9} C_7$ ways.

Therefore, in this case, required number of ways

$={ }^{4} C_3 \times{ }^{9} C_4+{ }^{4} C_2 \times{ }^{9} C_5+{ }^{4} C_1 \times{ }^{9} C_6+{ }^{4} C_0 \times{ }^{9} C_7$

$=\dfrac{4 !}{3 ! 1 !} \times \dfrac{9 !}{4 ! 5 !}+\dfrac{4 !}{2 ! 2 !} \times \dfrac{9 !}{5 ! 4 !}+\dfrac{4 !}{1 ! 3 !} \times \dfrac{9 !}{6 ! 3 !}+\dfrac{4 !}{0 ! 4 !} \times \dfrac{9 !}{7 ! 2 !}$

$=504+756+336+36$

$=1632$

4. If the different permutations of all the letter of the word EXAMINATION are listed as in a dictionary, how many words are there in this list before the first word starting with $E$ ?

Show Answer

Answer :

In the given word EXAMINATION, there are 11 letters out of which, $A, I$, and $N$ appear 2 times and all the other letters appear only once.

The words that will be listed before the words starting with $E$ in a dictionary will be the words that start with $A$ only.

Therefore, to get the number of words starting with A, the letter A is fixed at the extreme left position, and then the remaining 10 letters taken all at a time are rearranged.

Since there are 2 Is and $2 Ns$ in the remaining 10 letters,

Number of words starting with $A=\dfrac{10 !}{2 ! 2 !}=907200$

Thus, the required numbers of words is 907200 .

5. How many 6-digit numbers can be formed from the digits $0,1,3,5,7$ and 9 which are divisible by 10 and no digit is repeated?

Show Answer

Answer :

A number is divisible by 10 if its units digits is 0 .

Therefore, 0 is fixed at the units place.

Therefore, there will be as many ways as there are ways of filling 5 vacant places

$ \begin{array}{|c|c|c|c|c|c|} \hline & & & & & 0\\ \hline \end{array} $

by the remaining 5 digits (i.e., 1, 3, 5, 7 and 9 ).

The 5 vacant places can be filled in 5 ! ways.

Hence, required number of 6-digit numbers $=5 !=120$

6. The English alphabet has 5 vowels and 21 consonants. How many words with two different vowels and 2 different consonants can be formed from the alphabet?

Show Answer

Answer :

2 different vowels and 2 different consonants are to be selected from the English alphabet.

Since there are 5 vowels in the English alphabet, number of ways of selecting 2 different vowels from the alphabet

$ ={ }^{5} C_2=\dfrac{5 !}{2 ! 3 !}=10 $

Since there are 21 consonants in the English alphabet, number of ways of selecting 2 different consonants from the alphabet

$ ={ }^{21} C_2=\dfrac{21 !}{2 ! 19 !}=210 $

Therefore, number of combinations of 2 different vowels and 2 different consonants $=10 \times 210=2100$

Each of these 2100 combinations has 4 letters, which can be arranged among themselves in 4! ways.

Therefore, required number of words $=2100 \times 4 !=50400$

7. In an examination, a question paper consists of 12 questions divided into two parts i.e., Part I and Part II, containing 5 and 7 questions, respectively. A student is required to attempt 8 questions in all, selecting at least 3 from each part. In how many ways can a student select the questions?

Show Answer

Answer :

It is given that the question paper consists of 12 questions divided into two parts Part I and Part II, containing 5 and 7 questions, respectively.

A student has to attempt 8 questions, selecting at least 3 from each part.

This can be done as follows.

(a) 3 questions from part I and 5 questions from part II

(b) 4 questions from part I and 4 questions from part II

(c) 5 questions from part I and 3 questions from part II

3 questions from part I and 5 questions from part II can be selected in ${ }^{5} C_3 \times{ }^{7} C_5$ ways.

4 questions from part I and 4 questions from part II can be selected in ${ }^{5} C_4 \times{ }^{7} C_4$ ways.

5 questions from part I and 3 questions from part II can be selected in ${ }^{5} C_5 \times{ }^{7} C_3$ ways.

Thus, required number of ways of selecting questions

$ \begin{aligned} & ={ }^{5} C_3 \times{ }^{7} C_5+{ }^{5} C_4 \times{ }^{7} C_4+{ }^{5} C_5 \times{ }^{7} C_3 \\ & =\dfrac{5 !}{2 ! 3 !} \times \dfrac{7 !}{2 ! 5 !}+\dfrac{5 !}{4 ! 1 !} \times \dfrac{7 !}{4 ! 3 !}+\dfrac{5 !}{5 ! 0 !} \times \dfrac{7 !}{3 ! 4 !} \\ & =210+175+35=420 \end{aligned} $

8. Determine the number of 5-card combinations out of a deck of 52 cards if each selection of 5 cards has exactly one king.

Show Answer

Answer :

From a deck of 52 cards, 5 -card combinations have to be made in such a way that in each selection of 5 cards, there is exactly one king.

In a deck of 52 cards, there are 4 kings.

1 king can be selected out of 4 kings in ${ }^{4} C_1$ ways.

4 cards out of the remaining 48 cards can be selected in ${ }^{48} C_4$ ways.

Thus, the required number of 5-card combinations is ${ }^{4} C_1 \times{ }^{48} C_4$.

9. It is required to seat 5 men and 4 women in a row so that the women occupy the even places. How many such arrangements are possible?

Show Answer

Answer :

5 men and 4 women are to be seated in a row such that the women occupy the even places.

The 5 men can be seated in 5 ! ways. For each arrangement, the 4 women can be seated only at the cross marked places (so that women occupy the even places).

$ M \times M \times M \times M \times M $

Therefore, the women can be seated in 4! ways.

Thus, possible number of arrangements $=4 ! \times 5 !=24 \times 120=2880$

10. From a class of 25 students, 10 are to be chosen for an excursion party. There are 3 students who decide that either all of them will join or none of them will join. In how many ways can the excursion party be chosen?

Show Answer

Answer :

From the class of 25 students, 10 are to be chosen for an excursion party.

Since there are 3 students who decide that either all of them will join or none of them will join, there are two cases.

Case I: All the three students join.

Then, the remaining 7 students can be chosen from the remaining 22 students in ${ }^{22} C_7$ ways.

Case II: None of the three students join.

Then, 10 students can be chosen from the remaining 22 students in ${ }^{22} C _{10}$ ways.

Thus, required number of ways of choosing the excursion party is ${ }^{22} C_7+{ }^{22} C _{10}$.

11. In how many ways can the letters of the word ASSASSINATION be arranged so that all the S’s are together?

Show Answer

Answer :

In the given word ASSASSINATION, the letter A appears 3 times, $S$ appears 4 times, I appears 2 times, $N$ appears 2 times, and all the other letters appear only once.

Since all the words have to be arranged in such a way that all the Ss are together, SSSS is treated as a single object for the time being. This single object together with the remaining 9 objects will account for 10 objects.

These 10 objects in which there are 3 As, 2 ls, and 2 Ns can be arranged in $\dfrac{10 !}{3 ! 2 ! 2 !}$ ways.

Thus, required number of ways of arranging the letters of the given word

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

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.

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

6.1 भूमिक (Introduction)

मान लीजिए कि आपके पास नंबर वाले ताले का एक सूटकेस है। माना उस ताले में 4 चक्र लगे हैं और प्रत्येक चक्र 0 से 9 तक के 10 अंकों द्वारा चिह्नित है। ताले को खोला जा सकता है यदि 4 विशिष्ट अंको को, बिना दोहराए, एक निश्चित क्रम में व्यवस्थित किया जाए। माना किसी कारण आप अंकों के इस निश्चित क्रम को भूल गए हैं। आपकों केवल पहला अंक याद है जो कि 7 है। ताले को खोलने के लिए, आपको 3 अंकों के कितने अनुक्रमों की जाँच करनी पड़ेगी? इस प्रश्न के उत्तर के लिए, आप संभवतः शेष 9 अंकों में से एक समय में 3 अंकों को लेकर, सभी संभव क्रमों को अविलंब सूचीबद्ध करना प्रारंभ कर दें। परंतु यह विधि थकाने वाली और नीरस होगी, क्योंकि संभव

Jacob Bernoulli (1654-1705 A.D.) क्रमों की संख्या बड़ी हो सकती है। इस अध्याय में, हम कुछ ऐसी मौलिक गणन तकनीक सीखेंगे जिनसे हम, 3 अंकों के क्रमों को सूचीबद्ध किए बिना ही, इस प्रश्न का उत्तर दे सकेंगे। वस्तुतः ये तकनीक, वस्तुओं के चयन तथा उनको क्रमबद्ध करने के भिन्न-भिन्न तरीकों की संख्या निर्धारित करने में उपयोगी होती हैं। प्रथम चरण में, हम उस सिद्धांत पर विचार करेंगे, जो कि इन तकनीकों को सीखनें के लिए अत्यधिक मौलिक है।

6.2 गणना का आधारभूत सिद्धांत (Fundamental Principle of Counting)

उसके पास पहनने के लिए पैंट तथा कमीज़ के कितने भिन्न-भिन्न जोड़े (युग्म) हैं? एक पैंट चुनने के लिए 3 तरीके हैं, क्योंकि चयन के लिए 3 पैंट उपलब्ध हैं। इसी प्रकार एक कमीज़ का चयन 2 तरह से किया जा सकता है। पैंट के प्रत्येक चयन के लिए कमीज़ के चयन के 2 विकल्प संभव हैं। अतः पैंट तथा कमीज़ के जोड़ों के चयन की संख्या $3 \times 2=6$ है। इस तथ्य को आकृति 6.1 में स्पष्ट किया गया है।

आइए हम निम्नलिखित समस्या पर विचार करें: मोहन के पास $\mathrm{P} _{1}, \mathrm{P} _{2}, \mathrm{P} _{3}$ तीन पैंट तथा $\mathrm{S} _{1}, \mathrm{~S} _{2}$ दो कमीज़ें है।

आकृति 6.1

आइए हम इसी प्रकार की एक दूसरी समस्या पर विचार करें:

शबनम के पास 2 बस्ते, 3 खाने के डिब्बे तथा 2 पानी की बोतलें हैं। वह इन वस्तुओं को किस प्रकार से ले जा सकती है (प्रत्येक में से एक चुन कर)।

एक बस्ते को 2 भिन्न तरीकों से चुना जा सकता है। एक बस्ते के चुने जाने के बाद, एक खाने के डिब्बे को चुनने के 3 भिन्न तरीके हैं। इस प्रकार बस्ते और खाने के डिब्बे के जोड़ों की संख्या $2 \times 3=6$ है। इनमें से प्रत्येक जोड़े के लिए, एक पानी की बोतल को चुनने के 2 भिन्न तरीके हैं।

अतः शबनम द्वारा इन वस्तुओं को स्कूल ले जाने के कुल $6 \times 2=12$ भिन्न तरीके हैं। यदि हम दो बस्तों को $\mathrm{B} _{1}, \mathrm{~B} _{2}$, तीन खाने के डिब्बों को $\mathrm{T} _{1}, \mathrm{~T} _{2}, \mathrm{~T} _{3}$ तथा दो पानी की बोतलों को $\mathrm{W} _{1}, \mathrm{~W} _{2}$, नाम दें, तो इन संभावनाओं को नीचे बनी आकृति द्वारा स्पष्ट किया जा सकता है (आकृति 6.2.)।

आकृति 6.2

वस्तुतः उपर्युक्त प्रकार की समस्याओं को निम्नलिखित सिद्धांत के प्रयोग द्वारा सरल किया जाता है, जिसे गणना का आधारभूत सिद्धांत अथवा केवल गणन सिद्धांत कहते हैं और जिसका कथन इस प्रकार है,

“यदि एक घटना $m$ भिन्न तरीकों से घटित हो सकती है, तदोपरांत एक अन्य घटना $n$ भिन्न तरीकों से घटित हो सकती है, तो दिए हुए क्रम में दोनों घटनाओं के भिन्न तरीकों के घटित होने की कुल भिन्न संख्या $m \times n$ है।"

ऊपर वर्णित सिद्धांत का घटनाओं की सीमित संख्या के लिए व्यापकीकरण किया जा सकता है। उदाहरणार्थ, 3 घटनाओं के लिए, यह सिद्धांत निम्नलिखित प्रकार से होगा:

‘यदि एक घटना $m$ भिन्न तरीकों से घटित हो सकती है, इसके उपरांत एक दूसरी घटना $n$ भिन्न तरीकों से घटित हो सकती है, तदोपरांत एक तीसरी घटना $p$ भिन्न तरीकों से घटित हो सकती है, तो तीनों घटनाओं के घटित होने के भिन्न तरीकों की कुल संख्या, दिए हुए क्रम में, $m \times n \times p$ है।"

प्रथम प्रश्न में, पैंट तथा कमीज़ के जोड़ों को पहनने की अभीष्ट संख्या, निम्नलिखित घटनाओं के उत्तरोत्तर घटित होने के विभिन्न विन्यासों की संख्या के तुल्य है:

(i) एक पैंट के चयन की घटना

(ii) एक कमीज़ के चयन की घटना

दूसरे प्रश्न में विन्यासों की अभीष्ट संख्या, निम्नलिखित घटनाओं के उत्तरोत्तर घटित होने के विभिन्न विन्यासों की संख्या के बराबर है:

(i) एक बस्ते के चयन की घटना,

(ii) एक खाने के डिब्बे के चयन की घटना,

(iii) एक पानी की बोतल के चयन की घटना।

यहाँ दोनों में से प्रत्येक प्रश्न में घटनाएँ अनेक संभव क्रमों में घटित हो सकती हैं परंतु हम इन संभव क्रमों में से किसी एक का चयन करते हैं और इस चयनित क्रम में घटनाओं के घटित होने के विभिन्न विन्यासों की गणना करते हैं।

उदाहरण 1 शब्द ROSE, के अक्षरों से बनने वाले 4 अक्षरों वाले, अर्थपूर्ण या अर्थहीन, शब्दों की संख्या ज्ञात कीजिए, जबकि अक्षरों के पुनरावृत्ति की अनुमति नहीं है।

हल रचित शब्दों की संख्या, 4 रिक्त स्थानों $\square \square \square \square$ को 4 अक्षरों से उत्तरोत्तर भरने के तरीकों की संख्या के बराबर है, जबकि इस बात का ध्यान रखा जाए कि पुनरावृत्ति की अनुमति नहीं है। पहले स्थान को, 4 अक्षर $\mathrm{R}, \mathrm{O}, \mathrm{S}$, और $\mathrm{E}$ में से किसी एक द्वारा 4 विभिन्न तरीकों से भरा जा सकता है। इसके बाद, दूसरे स्थान को शेष तीन अक्षरों में से किसी एक द्वारा 3 विभिन्न तरीकों से भरा जा सकता हैं इसके उपरांत तीसरे स्थान को 2 विभिन्न तरीकों से भरा जा सकता है और अंत में चौथे स्थान को केवल 1 तरीके से भरा जा सकता है इस प्रकार गुणन सिद्धांत द्वारा चारों स्थानों को भरने के तरीकों की संख्या $4 \times 3 \times 2 \times 1=24$ है। अतः शब्दों की अभीष्ट संख्या 24 है।

टिप्पणी यदि अक्षरों की पुनरावृत्ति की अनुमति होती, तो कितने शब्द बन सकते हैं? यह बात सरलता से समझी जा सकती है कि 4 रिक्त स्थानों में से प्रत्येक उत्तरोत्तर 4 विभिन्न तरीकों से भरा जा सकता है। अत: शब्दों की अभीष्ट संख्या $=4 \times 4 \times 4 \times 4=256$.

उदाहरण 2 भिन्न-भिन्न रंगों के दिए हुए 4 झंडों से, कितने भिन्न-भिन्न संकेत उत्पन्न किए जा सकते हैं, यदि एक संकेत के लिए, एक दूसरे के नीचे, 2 झंडों की आवश्यकता पड़ती है?

हल उत्पादित संकेतों की संख्या 2 रिक्त स्थानों $\begin{array}{|l|} \hline \quad \\ \hline \\ \hline \end{array}$ को भिन्न-भिन्न रंगों के 4 झंडों से उत्तरोत्तर भरने के तरीकों की संख्या के बराबर है। ऊपर के रिक्त स्थान को 4 झंडों में से किसी एक द्वारा 4 विभिन्न तरीकों से भरा जा सकता है। इसके बाद, नीचे के रिक्त स्थान को शेष 3 झंडों में से किसी एक द्वारा 3 विभिन्न तरीकों से भरा जा सकता है। अतः गुणन सिद्धांत द्वारा संकेतों की अभीष्ट संख्या $=4 \times 3=12$.

उदाहरण 3 अंकों $1,2,3,4,5$ से कितनी 2 अंकीय सम संख्याएँ बन सकती हैं, यदि अंकों की पुनरावृत्ति की जा सकती है?

हल संख्याओं को बनाने के तरीके, 2 रिक्त स्थानों $\square \square$ को उत्तरोत्तर उचित प्रकार से भरने के तरीको की संख्या के बराबर है। यहाँ इकाई स्थान को भरने के लिए केवल 2 विकल्प हैं: अंक 2 या 4 , और यह 2 तरीकों से किया जा सकता है। इसके पश्चात् दहाई स्थान को 5 अंकों में से किसी एक द्वारा भरा जा सकता है (क्योंकि अंकों की पुनरावृत्ति की जा सकती है)। अतः इसके 5 विकल्प हैं। अतएव गुणन सिद्धांत द्वारा दो अंकों वाली सम संख्याओं की अभीष्ट संख्या $=2 \times 5$, अर्थात् 10 है।

उदाहरण 4 यदि पाँच विभिन्न झंडे उपलब्ध हैं, तो उन विभिन्न संकेतों की संख्या ज्ञात कीजिए जिन्हें कम से कम दो झंडों को एक ऊर्ध्व दंड पर क्रमवत एक को दूसरे के नीचे रखकर उत्पन्न किया जा सकता है?

हल एक संकेत या तो 2 या 3 या 4 या 5 झंडों से बनाया जा सकता है। अब हम $2,3,4$ या 5 झंडों से बनने वाले संकेतों की संभव संख्याओं की अलग-अलग गणना करेंगे और फिर इन संख्याओं को जोड़ देंगे।

2 झंडों द्वारा बनने वाले संकेतों की संख्या, 5 उपलब्ध झंडों से 2 रिक्त स्थानों $\begin{array}{|l|} \hline \quad \\ \hline \\ \hline \end{array}$ को उत्तरोत्तर भरने की संख्या के बराबर है। गुणन नियम के अनुसार इसकी संख्या $=5 \times 4=20$ है।

इसी प्रकार 3 झंडों द्वारा बनने वाले संकेतों की संख्या, 5 झंडों से 3 रिक्त स्थानों $\begin{array}{|l|} \hline \quad \\ \hline \\ \hline \\ \hline \end{array}$ को उत्तरोत्तर भरने की संख्या के बराबर है

इसकी संख्या $5 \times 4 \times 3=60$ है।

इसी प्रकार

झंडों वाले संकेतों की संख्या $=5 \times 4 \times 3 \times 2=120$

और 5 झंडों वाले संकेतों की संख्या $=5 \times 4 \times 3 \times 2 \times 1=120$

अतः संकेतो की अभीष्ट संख्या $=20+60+120+120=320$.

प्रश्नावली 6.1

1. अंक $1,2,3,4$ और 5 से कितनी 3 अंकीय संख्याएँ बनाई जा सकती हैं, यदि

(i) अंकों की पुनरावृत्ति की अनुमति हो ?

(ii) अंकों की पुनरावृत्ति की अनुमति नहीं हो ?

Show Answer

Answer

/#missing

2. अंक $1,2,3,4,5,6$ से कितनी 3 अंकीय सम संख्याएँ बनाई जा सकती हैं, यदि अंकों की पुनरावृत्ति की जा सकती है ?

Show Answer

Answer

/#missing

3. अंग्रेज़ी वर्णमाला के प्रथम 10 अक्षरों से कितने 4 अक्षर के कोड बनाए जा सकते हैं, यदि किसी भी अक्षर की पुनरावृत्ति नहीं की जा सकती है?

Show Answer

Answer

/#missing

4. 0 से 9 तक के अंकों का प्रयोग करके कितने 5 अंकीय टेलीफोन नंबर बनाए जा सकते हैं, यदि प्रत्येक नंबर 67 से प्रारंभ होता है और कोई अंक एक बार से अधिक नहीं आता है?

Show Answer

Answer

/#missing

5. एक सिक्का तीन बार उछाला जाता है और परिणाम अंकित कर लिए जाते हैं। परिणामों की संभव संख्या क्या है?

Show Answer

Answer

/#missing

6. भिन्न-भिन्न रंगों के 5 झंडे दिए हुए हैं। इनसे कितने विभिन्न संकेत बनाए जा सकते हैं, यदि प्रत्येक संकेत में 2 झंडों, एक के नीचे दूसरे, के प्रयोग की आवश्यकता पड़ती है?

Show Answer

Answer

/#missing

6.3 क्रमचय (Permutations)

पिछले अनुच्छेद के उदाहरण 1 में, हम वास्तव में अक्षरों के विभिन्न विन्यासों, जैसे ROSE, REOS, …, इत्यादि, की संभव संख्या की गणना करते हैं। इस सूची में प्रत्येक विन्यास दूसरे से भिन्न हैं। दूसरे शब्दों में अक्षरों के लिखने का क्रम महत्वपूर्ण है इनमें से प्रत्येक विन्यास, 4 विभिन्न अक्षरों में से एक समय में सभी को साथ लेकर बनाया गया, क्रमचय कहलाता है अब यदि हमें शब्द NUMBER, के अक्षरों में से 3 अक्षरीय, अर्थपूर्ण या अर्थहीन रचित शब्दों की संख्या निर्धारित करनी है, जबकि अक्षरों की पुनरावृत्ति की अनुमति नहीं हो, तो हमें NUM, NMU,MUN,NUB, …इत्यादि विन्यासों की गणना की आवश्यकता है। यहाँ पर हम 6 विभिन्न अक्षरों में से एक समय में 3 अक्षरों को लेकर बनने वाले क्रमचयों की गणना कर रहे हैं। इस प्रकार के शब्दों की अभीष्ट संख्या $=6 \times 5 \times 4=$ 120 (गुणन सिद्धांत के प्रयोग द्वारा) हैं।

यदि अक्षरों की पुनरावृत्ति की अनुमति होती, तो शब्दों की अभीष्ट संख्या $6 \times 6 \times 6=216$ होगी।

परिभाषा 1 क्रमचय एक निश्चित क्रम में बना विन्यास है, जिसको दी हुई वस्तुओं में से एक समय में कुछ या सभी को लेकर बनाया गया है।

नीचे दिए उप-अनुच्छेद में हम उस सूत्र को निर्धारित करेंगे जिसकी आवश्यकता इस प्रकार के प्रश्नों के उत्तर देने के लिए पड़ती है।

6.3.1 क्रमचय, जब सभी वस्तुएँ भिन्न-भिन्न हैं (Permutations when all the objects are distinct)

प्रमेय $1 n$ विभिन्न वस्तुओं में से एक समय में $r$ वस्तुओं को लेकर बनाए गए क्रमचयों की संख्या को प्रतीक ${ }^{n} \mathrm{P} _{r}$ से निरूपित करते हैं, जहाँ $0<r \leq n$ तथा किसी भी क्रमचय में वस्तुओं की पुनरावृत्ति की अनुमति नहीं है, ${ }^{n} \mathrm{P} _{r}=n(n-1)(n-2) \ldots(n-r+1)$

उपपत्ति क्रमचयों की संख्या, $r$ रिक्त स्थानों को $ \underset{\leftarrow r \text{ रिक्त स्थान} \rightarrow}{\Large{\square \square \square \cdots }} \Large{\square}$ उत्तरोत्तर

$n$ वस्तुओं से भरने के तरीकों की संख्या के बराबर है। पहला स्थान $n$ तरीकों से भरा जा सकता है। इसके बाद दूसरा स्थान $(n-1)$ तरीकों से भरा जा सकता है। इसके उपरांत तीसरा स्थान $[n-2)$ तरीकों से भरा जा सकता है …….. और $r$ वाँ स्थान $(n-(r-1)]$ तरीकों से भरा जा सकता है। अतः $r$ रिक्त स्थानों को उत्तरोत्तर भरने के तरीकों की संख्या $=n(n-1)(n-2) \ldots$ $(n-(r-1))$ या $n(n-1)(n-2) \ldots(n-r+1)$

${ }^{n} \mathrm{P}_{r}$ के लिए यह एक बोझिल व्यंजक है और हमें एक ऐसे संकेतन की आवश्यकता है, जिसकी सहायता से इस व्यंजक के विस्तार को घटाया जा सके। प्रतीक $n$ ! (जिसे $n$ क्रमगुणित पढ़ते हैं) इसमें हमारी सहायता करता है। निम्नलिखित विवरण में हम सीखेंगे कि वास्तव में $n$ ! का क्या अर्थ है?

6.3.2 क्रमगुणित संकेतन (Factorial notation)

संकेतन $n$ ! प्रथम $n$ प्राकृत संख्याओं के गुणनफल को व्यक्त करता है अर्थात् $1 \times 2 \times 3 \times \ldots \times(n-1) \times n$ को $n$ ! द्वारा निरूपित किया जाता है। हम इस प्रतीक को ’ $n$ क्रमगुणित पढ़ते हैं। इस प्रकार $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{ ! इत्यादि } \end{aligned} $

हम परिभाषित करते हैं, कि $0 !=1$

इस प्रकार हम लिख सकते हैं, कि $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 { ! } $$

स्पष्टतया सभी प्राकृत संख्या $n$ के लिए

$$ \begin{array}{rlrl} n ! & =n(n-1) ! & \\ & =n(n-1)(n-2) ! & & \text { [ यदि } n \geq 2] \\ & =n(n-1)(n-2)(n-3) ! & & \text { [ यदि } n \geq 3] \end{array} $$

इत्यादि

उदाहरण 5 मान निकालिए

(i) 5 !

(ii) 7 !

(iii) $7 ! -5$ !

हल

(i) $5 ! =1 \times 2 \times 3 \times 4 \times 5=120$

(ii) 7 ! $=1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7=5040$

और

(iii) $ 7 ! - 5! =5040-120=4920$

उदहारण 6 परिकलन कीजिए (i) $\frac{7 \text { ! }}{5 !}$

(ii) $\frac{12 !}{(10 !)(2 !)}$

हल

(i) हम प्राप्त करते हैं, $\frac{7 !}{5 !}=\frac{7 \times 6 \times 5 !}{5 !}=7 \times 6=42$

और

(ii) $\frac{12 !}{(10 !)(2 !)}=\frac{12 \times 11 \times(10 !)}{(10 !) \times(2)}=6 \times 11=66$

उदाहरण 7 मान निकालिए $\frac{n !}{r !(n-r) !}$, जहाँ $n=5, r=2$

हल हमें निम्नलिखित का मान निकालना है $\frac{5 !}{2 !(5-2) !}($ क्योंकि $n=5, r=2)$

यहाँ पर $\quad \frac{5 !}{2 !(5-2) !}=\frac{5 !}{2 ! \times 3 !}=\frac{5 \times 4}{2}=10$

उदाहरण 8 यदि $\frac{1}{8 !}+\frac{1}{9 !}=\frac{x}{10 !}$, तो $x$ ज्ञात कीजिए।

हल यहाँ पर $\frac{1}{8 !}+\frac{1}{9 \times 8 !}=\frac{x}{10 \times 9 \times 8 !}$

अतएव $1+\frac{1}{9}=\frac{x}{10 \times 9}$ या $\frac{10}{9}=\frac{x}{10 \times 9}$

अत:

$$ x=100 $$

प्रश्नावाली 6.2

1. मान निकालिए:

(i) 8 !

(ii) 4 !-3 !

Show Answer

Answer

/#missing

2. क्या $3 !+4 !=7 !$ ?

Show Answer

Answer

/#missing

3. $\frac{8 !}{6 ! \times 2 !}$ का परिकलन कीजिए

Show Answer

Answer

/#missing

4. यदि $\frac{1}{6 !}+\frac{1}{7 !}=\frac{x}{8 !}$, तो $x$ का मान ज्ञात कीजिए।

Show Answer

Answer

/#missing

5. $\frac{n !}{(n-r) !}$, का मान निकालिए जब

(i) $n=6, r=2$

(ii) $n=9, r=5$.

Show Answer

Answer

/#missing

6.3.3 ${ }^{n} P_{r}$ के लिए सूत्र की व्युत्पत्ति (Derivation of the formula for ${ }^{n} P_{r}$ )

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

आइए हम उस अवस्था पर वापस चलें जहाँ हमने निम्नलिखित ज्ञात किया था:

$$ { }^{n} \mathrm{P}_{r}=n(n-1)(n-2) \ldots(n-r+1) $$

इसके अंश और हर को $(n-r)(n-r-1) \ldots 3 \times 2 \times 1$, से गुणा करने पर, हमें प्राप्त होता है कि

$ { }^{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) !}, $

इस प्रकार $\quad \quad \quad{ }^{n} \mathrm{P}_{r}=\frac{n !}{(n-r) !}$, जहाँ $0<r \leq n$

यह ${ }^{n} \mathrm{P}_{r}$ पहले से अधिक सुविधाजनक व्यंजक है।

विशेष रूप से जब $r=n$, तो ${ }^{n} \mathrm{P}_{n}=\frac{n !}{0 !}=n$ !

क्रमचयों की गणना, केवल उन तरीकों की गणना है, जिनमें एक समय में कुछ या सभी वस्तुओं का विन्यास किया गया हो। एक भी वस्तु के बिना विन्यास की संख्या बराबर है उस संख्या के जिसमें सभी वस्तुओं को छोड़कर विन्यास किया गया हो और हमें ज्ञात है कि ऐसा करने का केवल एक तरीका है। इसी कारण से हमने ${ }^{n} \mathrm{P}_{0}=1$ परिभाषित किया है।

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

अतः सूत्र (1), $r=0$ के लिए भी लागू है।

अत: $\quad{ }^{n} \mathrm{P}_{r}=\frac{n !}{(n-r) !}, 0 \leq r \leq n$.

प्रमेय $2 n$ विभिन्न वस्तुओं में से एक समय में $r$ वस्तुओं को लेकर बने क्रमचयों की संख्या, जबकि वस्तुओं के पुनरावृत्ति की अनुमति हो, $n^{r}$ होती है।

इसकी उपपत्ति पिछले प्रमेय की उपपत्ति के समान है, अतः इसको पाठक के लिए छोड़ दिया गया है।

अब हम ${ }^{n} \mathrm{P}$ के सूत्र की उपयोगिता को स्पष्ट करने के लिए पिछले अनुच्छेद के कुछ प्रश्नों को इस सूत्र के प्रयोग द्वारा सरल कर रहे हैं।

उदाहरण 1 में शब्दों की अभीष्ट संख्या $={ }^{4} \mathrm{P}_{4}=4$ ! = 24 जब पुनरावृत्ति की अनुमति नहीं हैं। यदि पुनरावृत्ति की अनुमति हो, तो शब्दों की अभीष्ट संख्या $4^{4}=256$ होगी।

NUMBER शब्द के अक्षरों में से 3 अक्षरों वाले चयनित शब्दों की संख्या $={ }^{6} \mathrm{P}_{3}=\frac{6 !}{3 !}=$ $4 \times 5 \times 6=120$, यहाँ इस प्रश्न में भी पुनरावृत्ति की अनुमति नहीं है। यदि पुनरावृत्ति की अनुमति हो, तो शब्दों की अभीष्ट संख्या $6^{3}=216$ होगी।

12 व्यक्तियों के एक समुदाय से एक अध्यक्ष और एक उपाध्यक्ष के चयन के तरीकों की संख्या, यह मानकर कि एक व्यक्ति एक से अधिक पद पर नहीं रह सकता है, स्पष्टतया

$$ { }^{12} \mathrm{P}_{2}=\frac{12 !}{10 !}=11 \times 12=132 $$

6.3.4 क्रमचय, जब सभी वस्तुएँ भिन्न-भिन्न नहीं हैं (Permutations when all the objects are not distinct objects)

मान लीजिए कि हमें शब्द ROOT के अक्षरों के पुनर्विन्यास के तरीकों की संख्या ज्ञात करनी है। इस दशा में, सभी अक्षर भिन्न-भिन्न नहीं है। यहाँ $2 \mathrm{O}$ हैं जो समान प्रकार के अक्षर हैं। हम इन दोनों $\mathrm{O}$ को अस्थाई रूप से भिन्न-भिन्न मान लेते हैं जैसे $\mathrm{O} _{1}$ और $\mathrm{O} _{2}$. अब इस दशा में 4 विभिन्न अक्षरों में से एक समय में सभी को लेकर बनने वाले क्रमचयों की संख्या 4 ! है। इन क्रमचयों में से एक क्रमचय $\mathrm{RO} _{1} \mathrm{O} _{2} \mathrm{~T}$ पर विचार कीजिए। इसके संगत, यहाँ पर 2 ! क्रमचय $\mathrm{RO} _{1} \mathrm{O} _{2} \mathrm{~T}$ तथा $\mathrm{RO} _{2} \mathrm{O} _{1} \mathrm{~T}$ ऐसे हैं जो कि समान क्रमचय होते यदि $\mathrm{O} _{1}$ तथा $\mathrm{O} _{2}$ को भिन्न-भिन्न नहीं माना गया होता अर्थात् यदि $\mathrm{O} _{1}$ तथा $\mathrm{O} _{2}$ दोनों क्रमचय में $\mathrm{O}$ होते। अतएव, क्रमचयों की अभीष्ट संख्या$=\frac{4 !}{2 !}=3 \times 4=12$

इस बात को नीचे स्पष्ट किया गया है: क्रमचय जब $\mathrm{O} _{1}, \mathrm{O} _{2}$ भिन्न-भिन्न हैं। क्रमचय जब $\mathrm{O} _{1}, \mathrm{O} _{2}$ दोनों $\mathrm{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{TO} _{2} \\ \mathrm{RO} _{2} \mathrm{TO} _{1}\end{array}\right] \longrightarrow \mathrm{ROTO}$

$\left.\begin{array}{c}\mathrm{TO} _{1} \mathrm{RO} _{2} \\ \mathrm{TO} _{2} \mathrm{RO} _{1}\end{array}\right] \longrightarrow \mathrm{TORO}$

$\left.\begin{array}{l}\mathrm{RTO} _{1} \mathrm{O} _{2} \\ \mathrm{RTO} _{2} \mathrm{O} _{1}\end{array}\right] \longrightarrow \mathrm{RTOO}$

$\left.\begin{array}{c}\mathrm{TRO} _{1} \mathrm{O} _{2} \\ \mathrm{TRO} _{2} \mathrm{O} _{1}\end{array}\right] \longrightarrow \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}$

आइए अब हम शब्द INSTITUTE के अक्षरों के पुनर्विन्यास के तरीकों की संख्या ज्ञात करें। इस दशा में 9 अक्षर हैं, जिनमें $\mathrm{I}$ दो बार तथा $\mathrm{T}$ तीन बार आता है।

अस्थाई रूप से, हम इन समान अक्षरों को भिन्न-भिन्न मान लेते हैं जैसे $\mathrm{I} _{1}, \mathrm{I} _{2}, \mathrm{~T} _{1}, \mathrm{~T} _{2}, \mathrm{~T} _{3}$. 9 विभिन्न अक्षरों में से एक समय में सभी को लेने से बने क्रमचयों की संख्या 9 ! है। इनमें से एक क्रमचय माना कि $\mathrm{I} _{1} \mathrm{NT} _{1} \mathrm{SI} _{2} \mathrm{~T} _{2} \mathrm{UET} _{3}$ पर विचार कीजिए। यदि $\mathrm{I} _{1}, \mathrm{I} _{2}$ समान नहीं हों और $\mathrm{T} _{1}$, $\mathrm{T} _{2}, \mathrm{~T} _{3}$ एक जैसे न हों तो $\mathrm{I} _{1}, \mathrm{I} _{2}$ का 2 ! तरीकों से तथा $\mathrm{T} _{1}, \mathrm{~T} _{2}, \mathrm{~T} _{3}$ का 3 ! तरीकों से विन्यास किया जा सकता है। यदि $\mathrm{I} _{1}, \mathrm{I} _{2}$ समान हों तथा $\mathrm{T} _{1}, \mathrm{~T} _{2}, \mathrm{~T} _{3}$ समान हो, तो $2 ! \times 3$ ! क्रमचय समान होगें। इस प्रकार पूछे गए विभिन्न क्रमचयों की कुल संख्या $\frac{9 !}{2 ! 3 !}$ है।

हम निम्नलिखित प्रमेय का कथन (बिना उपपत्ति) व्यक्त कर सकते हैं।

प्रमेय $3 n$ वस्तुओं के क्रमचयों की संख्या, जहाँ $p$ वस्तुएँ समान प्रकार की और शेष भिन्न प्रकार की हैं $=\frac{n !}{p !}$.

वस्तुतः इस संबंध में एक अधिक व्यापक प्रमेय है जो नीचे वर्णित है:

प्रमेय $4 n$ वस्तुओं के क्रमचयों की संख्या $\frac{n !}{p_{1} ! p_{2} ! \ldots p_{k} !}$ है।, जहाँ $p_{1}$ वस्तुएँ एक प्रकार की, $p_{2}$ वस्तुएँ दूसरे प्रकार की $, \ldots, p_{k}$ वस्तुएँ $k$ वाँ प्रकार की और शेष (यदि कोई है) विभिन्न प्रकार की हैं।

उदाहरण 9 ALLAHABAD शब्द के अक्षरों से बनने वाले क्रमचयों की संख्या ज्ञात कीजिए।

हल यहाँ पर 9 अक्षर हैं, जिनमें A, 4 बार आया है, 2 बार $\mathrm{L}$ आया है तथा शेष विभिन्न प्रकार के हैं। अतएव विन्यासों की अभीष्ट संख्या

$$ =\frac{9 !}{4 ! 2 !}=\frac{5 \times 6 \times 7 \times 8 \times 9}{2}=7560 $$

उदाहरण 10 1 से 9 तक के अंकों का प्रयोग करके कितनी 4 अंकीय संख्याएँ बनाई जा सकती हैं, यदि अंकों की पुनरावृत्ति की अनुमति नहीं है?

हल यहाँ पर अंकों का क्रम महत्वपूर्ण है, उदाहरण के लिए 1234 तथा 1324 दो भिन्न-भिन्न संख्याएँ हैं। अतः 4-अंकीय संख्याओं की संख्या 9 विभिन्न अंकों में से एक समय में 4 अंकों को लेकर बनने वाले क्रमचयों की संख्या के बराबर है।

इस प्रकार 4 -अंकीय संख्याओं की अभीष्ट संख्या $={ }^{9} \mathrm{P}_{4}=\frac{9 !}{(9-4) !}=\frac{9 !}{5 !}=9 \times 8 \times 7 \times 6=3024$.

उदाहरण 11 100 से 1000 के बीच स्थित कितनी संख्याएँ हैं, जिन्हें अंक $0,1,2,3,4,5$ से बनाया जा सकता है, यदि अंकों के पुनरावृत्ति की अनुमति नहीं है।

हल 100 से 1000 के बीच स्थित प्रत्येक संख्या एक 3 अंकीय संख्या है। प्रथम हम 6 अंकों में से एक समय में 3 अंकों को लेकर बनने वाले क्रमचयों की संख्या की गणना करते हैं। यह संख्या ${ }^{6} \mathrm{P} _{3}$ है परंतु इन क्रमचयों में वे भी सम्मिलित हैं, जिनमें 0 , सैकड़े के स्थान पर है। उदाहरण के लिए 092,042 …. इत्यादि और ये ऐसी संख्याएँ है जो वास्तव में 2 अंकीय हैं। अतः अभीष्ट संख्या को ज्ञात करने के लिए, इस प्रकार की 2 अंकीय संख्याओं के ${ }^{6} \mathrm{P} _{3}$ में से घटाना पड़ेगा। अब इन 2 -अंकीय संख्याओं की संख्या ज्ञात करने के लिए, हम 0 को सैकड़े के स्थान पर स्थिर कर देते हैं और शेष 5 अंको से एक समय में दो अंकों को लेकर बनने वाले पुनर्विन्यासों की संख्या ज्ञात करते हैं। यह संख्या ${ }^{5} \mathrm{P} _{2}$ है।

अतः अभीष्ट संख्या $\quad={ }^{6} P_3-{ }^{5} P_2=\frac{6 !}{3 !}-\frac{5 !}{3 !}$

$ =4 \times 5 \times 6-4 \times 5=100 $

उदाहरण 12 $n$ का मान ज्ञात कीजिए, इस प्रकार कि (i) ${ }^{n} \mathrm{P} _{5}=42{ }^{n} \mathrm{P} _{3}, n>4$ (ii) $\frac{{ }^{n} \mathrm{P} _{4}}{{ }^{n-1} \mathrm{P} _{4}}=\frac{5}{3}, n>4$

हल (i) दिया है कि

$$ { }^{n} \mathrm{P} _{5}=42{ }^{n} \mathrm{P} _{3} $$

या $\quad \quad \quad \quad$ $n(n-1)(n-2)(n-3)(n-4)=42 n(n-1)(n-2)$

क्योंकि $\quad \quad \quad \quad n>4$ इसलिए $n(n-1)(n-2) \neq 0$

अतएव, दोनों पक्षों को $n(n-1)(n-2)$, से भाग देने पर

$$\begin{array}{ll} {} & (n-3(n-4)=42 \\ \text{या}\quad\quad & n^{2}-7 n-30=0 \\ \text{या} & n^{2}-10 n+3 n-30 \\ \text{या} & (n-10)(n+3)=0 \\ \text{या} & n-10=0 \text{ या } \quad n+3=0 \\ \text{या} & n=10 \quad \text{ या } \quad n=-3 \end{array}$$

क्योंकि $n$ ॠण संख्या नहीं हो सकती है अतः $n=10$

(ii) दिया है कि $\frac{{ }^n \mathrm{P}_4}{{ }^{n-1} \mathrm{P}_4}=\frac{5}{3}$

इस प्रकार $\quad \quad 3 n(n-1)(n-2)(n-3)=5(n-1)(n-2)(n-3)(n-4)$

या $\quad \quad3 n=5(n-4) \quad[$ क्योंकि $(n-1)(n-2)(n-3) \neq 0, n>4]$

या $\quad \quad n=10$.

उदाहरण 13 ज्ञात कीजिए $r$, यदि $5{ }^{4} \mathrm{P} _{r}=6{ }^{5} \mathrm{P} _{r-1}$.

हल यहाँ पर $5{ }^{4} P_r=6{ }^{5} P _{r-1}$

या $ \quad\quad5 \times \frac{4 !}{(4-r) !}=6 \times \frac{5 !}{(5-r+1) !} $

या $ \quad\quad\frac{5 !}{(4-r) !}=\frac{6 \times 5 !}{(5-r+1)(5-r)(5-r-1) !} $

या $\quad(6-r)(5-r)=6$

या $\quad r^{2}-11 r+24=0$

या $\quad r^{2}-8 r-3 r+24=0$

या $\quad(r-8)(r-3)=0$

या $\quad r=8$ or $r=3$.

अतः $\quad r=8,3$.

उदाहरण 14 DAUGHTER शब्द के अक्षरों से 8 अक्षर वाले विन्यासों की संख्या ज्ञात कीजिए, यदि

(i) सब स्वर एक साथ रहें।

(ii) सब स्वर एक साथ नहीं रहें।

हल (i) DAUGHTER शब्द में 8 विभिन्न अक्षर हैं, जिनमें से 3 स्वर हैं, अर्थात् $A, U$ तथा $E$ क्योंकि सभी स्वरों को एक साथ रहना है इसलिए हम कुछ समय के लिए उनको सम्मिलित रूप से एक वस्तु (AUE) मान लेते हैं। यह अकेली वस्तु शेष 5 वस्तुओं (अक्षरों) के साथ मिलकर 6 वस्तुएँ हो जाती हैं। फिर हम 6 वस्तुओं में से एक समय में सभी को लेकर बनने वाले क्रमचयों की संख्या की गणना करते हैं। यह संख्या ${ }^{6} \mathrm{P}_{6}=6$ ! है। इनमें से प्रत्येक क्रमचय के संगत हमें तीन स्वरों $\mathrm{A}, \mathrm{U}$, $\mathrm{E}$ में से सभी को एक समय में लेकर 3 ! क्रमचय बनते हैं। अतएव गुणन सिद्धांत से क्रमचयों की अभीष्ट संख्या $=6 ! \times 3 !=4320$.

(ii) यदि हमें उन क्रमचयों की संख्या ज्ञात करनी है, जिनमें सभी स्वर एक साथ नहीं हैं, तो हमें पहले 8 अक्षरों में से एक समय में सभी को साथ लेकर बनने वाले विन्यासों की संभव संख्या ज्ञात करनी होगी, जो 8 ! है। फिर इस संख्या से हमें सब स्वरों के एक साथ रहने वाली क्रमचयों की संख्या घटानी पड़ेगी।

अतः अभीष्ट संख्या

$$ \begin{aligned} 8 !-6 ! \times 3 ! & =6 !(7 \times 8-6) \\ & =2 \times 6 !(28-3) \\ & =50 \times 6 !=50 \times 720=36000 \end{aligned} $$

उदाहरण 15 4 लाल, 3 पीली तथा 2 हरी डिस्कों को एक पंक्ति में कितने प्रकार से व्यवस्थित किया जा सकता है, यदि एक ही रंग की डिस्कों में कोई अंतर नहीं है ?

हल डिस्कों की कुल संख्या $4+3+2=9$ है। इन 9 डिस्कों में से 4 डिस्कें एक प्रकार की (लाल), 3 डिस्कें दूसरे प्रकार की (पीली) तथा 2 डिस्कें तीसरे प्रकार की (हरी) हैं।

इस प्रकार डिस्कों को व्यवस्थित करने की संख्या $\frac{9 !}{4 ! 3 ! 2 !}=1260$.

उदाहरण 16 INDEPENDENCE शब्द के अक्षरों से बनने वाले विन्यासों की संख्या ज्ञात कीजिए। इन विन्यासों में से कितने विन्यासों में,

(i) शब्द $\mathrm{P}$ से प्रारंभ होते हैं?

(ii) सभी स्वर सदैव एक साथ रहते हैं?

(iii) स्वर कभी भी एक साथ नहीं रहते हैं?

(iv) शब्द $\mathrm{I}$ से प्रारंभ होते हैं और उनका अंत $\mathrm{P}$ से होता है ?

हल यहाँ पर 12 अक्षर है, जिनमें से $\mathrm{N}$ तीन बार, $\mathrm{E}$ चार बार $\mathrm{D}$, दो बार आता है और शेष अक्षरों में सभी भिन्न-भिन्न हैं।

इसलिए विन्यासों की अभीष्ट संख्या $=\frac{12 !}{3 ! 4 ! 2 !}=1663200$

(i) हम $\mathrm{P}$ को सबसे बाएँ स्थान पर स्थिर कर देते हैं और फिर शेष 11 अक्षरों के विन्यास की गणना करते हैं। अतएव $\mathrm{P}$ से प्रारंभ होने वाले शब्दों की अभीष्ट संख्या

$$ =\frac{11 !}{3 ! 2 ! 4 !}=138600 \text {. } $$

(ii) प्रदत्त शब्द में 5 स्वर हैं, जो कि 4 बार $\mathrm{E}$ है तथा 1 बार $\mathrm{I}$ है क्योंकि कि इनको सदैव एक साथ रहना है, इसलिए इनको कुछ समय के लिए एक अकेली वस्तु EEEEI समझ लेते हैं। यह अकेली वस्तु शेष 7 वस्तुओं के साथ मिलकर कुल 8 वस्तुएँ हो जाती हैं। इन 8 वस्तुओं जिनमें 3 बार $\mathrm{N}$ है, तथा दो बार $\mathrm{D}$ है के विन्यासों की संख्या $\frac{8 !}{3 ! 2 !}$ है। इनमें से प्रत्येक विन्यास के संगत 5 स्वर $\mathrm{E}, \mathrm{E}, \mathrm{E}, \mathrm{E}$ तथा $\mathrm{I}$ के विन्यासों की संख्या $\frac{5 !}{4 !}$ है। इसलिए गुणन सिद्धांत द्वारा विन्यासों की अभीष्ट संख्या

$$ =\frac{8 !}{3 ! 2 !} \times \frac{5 !}{4 !}=16800 $$

(iii) विन्यासों की अभीष्ट संख्या $=$ विन्यासों की कुल संख्या (बिना किसी प्रतिबंध के) - विन्यासों की संख्या, जिनमें सभी स्वर एक साथ रहते हैं

$$ =1663200-16800=1646400 $$

(iv) हम I तथा $\mathrm{P}$ को दोनों सिरों पर स्थिर कर देते हैं (I बाएँ सिरे पर और $\mathrm{P}$ दाएँ सिरे पर). इस प्रकार हमारे पास 10 अक्षर शेष रहते हैं।

अतः विन्यासों की अभीष्ट संख्या $=\frac{10 !}{3 ! 2 ! 4 !}=12600$

प्रश्नावली 6.3

1. 1 से 9 तक के अंकों को प्रयोग करके कितने 3 अंकीय संख्याएँ बन सकती हैं, यदि किसी भी अंक को दोहराया नहीं गया है?

Show Answer

Answer

/#missing

2. किसी भी अंक को दोहराए बिना कितनी 4 अंकीय संख्याएँ होती हैं?

Show Answer

Answer

/#missing

3. अंक $1,2,3,4,6,7$ को प्रयुक्त करने से कितनी 3 अंकीय सम संख्याएँ बनाई जा सकती हैं, यदि कोई भी अंक दोहराया नहीं गया है?

Show Answer

Answer

/#missing

4. अंक $1,2,3,4,5$ के उपयोग द्वारा कितनी 4 अंकीय संख्याएँ बनाई जा सकती है, यदि कोई भी अंक दोहराया नहीं गया है? इनमें से कितनी सम संख्याएँ होंगीं?

Show Answer

Answer

/#missing

5. 8 व्यक्तियों की समिति में, हम कितने प्रकार से एक अध्यक्ष और एक उपाध्यक्ष चुन सकते हैं, यह मानते हुए कि एक व्यक्ति एक से अधिक पद पर नहीं रह सकता है?

Show Answer

Answer

/#missing

6. यदि ${ }^{n-1} \mathrm{P} _{3}:{ }^{n} \mathrm{P} _{4}=1: 9$ तो $n$ ज्ञात कीजिए।

Show Answer

Answer

/#missing

7. $r$ ज्ञात कीजिए, यदि (i) ${ }^{5} \mathrm{P} _{r}=2{ }^{6} \mathrm{P} _{r-1}$ (ii) ${ }^{5} \mathrm{P} _{r}={ }^{6} \mathrm{P} _{r-1}$.

Show Answer

Answer

/#missing

8. EQUATION शब्द के अक्षरों में से प्रत्येक को तथ्यतः केवल एक बार उपयोग करके कितने अर्थपूर्ण या अर्थहीन, शब्द बन सकते हैं?

Show Answer

Answer

/#missing

9. MONDAY शब्द के अक्षरों से कितने, अर्थपूर्ण या अर्थहीन, शब्द बन सकते हैं, यह मानते हुए कि किसी भी अक्षर की पुनरावृत्ति नहीं की जाती है, यदि

(i) एक समय में 4 अक्षर लिए जाते हैं?

(ii) एक समय में सभी अक्षर लिए जाते हैं?

(iii) सभी अक्षरों का प्रयोग किया जाता है, किंतु प्रथम अक्षर एक स्वर है?

Show Answer

Answer

/#missing

10. MISSISSIPPI शब्द के अक्षरों से बने भिन्न-भिन्न क्रमचयों में से कितनों में चारों I एक साथ नहीं आते हैं ?

Show Answer

Answer

/#missing

11. PERMUTATIONS शब्द के अक्षरों को कितने तरीकों से व्यवस्थित किया जा सकता है, यदि

(i) चयनित शब्द का प्रारंभ $\mathrm{P}$ से तथा अंत $\mathrm{S}$ से होता है।

(ii) चयनित शब्द में सभी स्वर एक साथ हैं?

(iii) चयनित शब्द में $\mathrm{P}$ तथा $\mathrm{S}$ के मध्य सदैव 4 अक्षर हों ?

Show Answer

Answer

/#missing

6.4 संचय (Combinations)

मान लीजिए कि 3 लॉन टेनिस खिलाड़ियों $\mathrm{X}, \mathrm{Y}, \mathrm{Z}$ का एक समूह है। 2 खिलाड़ियों की एक टीम बनानी है। इसको हम कितने प्रकार से कर सकते हैं? क्या $\mathrm{X}$ और $\mathrm{Y}$ की टीम, $\mathrm{Y}$ तथा $\mathrm{X}$ की टीम से भिन्न है ? यहाँ पर खिलाड़ियों का क्रम महत्त्वपूर्ण नहीं है। वास्तव में टीम बनाने के केवल तीन ही संभव तरीके हैं। यह $\mathrm{XY}, \mathrm{YZ}$ तथा $\mathrm{ZX}$ हैं (आकृति 6.3)।

आकृति 6.3

यहाँ पर, प्रत्येक चयन, 3 विभिन्न वस्तुओं में से एक समय में 2 को लेकर बना हुआ, संचय कहलाता है।किसी संचय में चयनित वस्तुओं का क्रम महत्वपूर्ण नहीं है।

अब कुछ और उदाहरणों पर विचार करते हैं।

बारह व्यक्ति एक कमरे में मिलते हैं और प्रत्येक व्यक्ति अन्य सभी व्यक्तियों से हाथ मिलाता है। ‘हाथ मिलाने’ की कुल संख्या का निर्धरण हम किस प्रकार करते हैं। $\mathrm{X}$ का $\mathrm{Y}$ से हाथ मिलाना तथा $Y$ का $X$ से हाथ मिलाना दो भिन्न हाथ मिलाना नहीं हैं। यहाँ क्रम महत्वपूर्ण नहीं है। ‘हाथ मिलाने’ की कुल संख्या उतनी ही है, जितनी 12 विभिन्न वस्तुओं में से एक समय में 2 वस्तुओं को लेकर बनने वाले संचयों की संख्या है।

सात बिंदु एक वृत्त पर स्थित हैं। इन बिंदुओं में से किन्हीं भी दो को मिलाकर कितनी जीवाएँ खींची जा सकती हैं। यहाँ जीवाओं की कुल संख्या उतनी ही है, जितनी 7 विभिन्न वस्तुओं में से एक समय में 2 वस्तुओं को लेकर बनने वाले संचयों की संख्या है।

अब हम $n$ विभिन्न वस्तुओं में से एक समय में $r$ वस्तुओं को लेकर बनने वाले संचयों की संख्या, जिसे प्रतीक ${ }^{n} \mathrm{C}_{r}$ से प्रकट करते हैं, ज्ञात करने के लिए सूत्र प्राप्त करते हैं।

मान लीजिए कि हमारे पास 4 भिन्न-भिन्न वस्तुएँ $\mathrm{A}, \mathrm{B}, \mathrm{C}$ और $\mathrm{D}$ हैं। इनमें से एक समय में 2 वस्तुओं को लेकर यदि इसे संचय बनाना चाहें, तो ये संचय $\mathrm{AB}, \mathrm{AC}, \mathrm{AD}, \mathrm{BC}, \mathrm{BD}, \mathrm{CD}$ हैं। यहाँ पर $\mathrm{AB}$ तथा $\mathrm{BA}$ एक ही संचय है, क्योंकि वस्तुओं का क्रम संचय को परिवर्तित नहीं करता है। इसी कारण से हमने BA, CA, DA, CB, DB तथा DC को इस सूची में सम्मिलित नहीं किया है। इस प्रकार 4 विभिन्न वस्तुओं में से एक समय में 2 वस्तुओं को लेकर बनने वाले संचयों की संख्या 6 है, अर्थात् ${ }^{4} \mathrm{C} _{2}=6$.

इस सूची के प्रत्येक संचय के संगत, हमें 2 ! क्रमचय मिल सकते हैं, क्योंकि प्रत्येक संचय की 2 वस्तुओं को 2 ! तरीकों से पुनर्व्यवस्थित किया जा सकता है। इसलिए, क्रमचयों की संख्या $={ }^{4} \mathrm{C} _{2} \times 2$ !,

दूसरी तरफ 4 विभिन्न वस्तुओं में से एक समय में 2 वस्तुओं को लेकर बनने वाले क्रमचयों की संख्या $={ }^{4} \mathrm{P} _{2}$.

अतएव $\quad { }^{4} P_2= ^{4} C_2 \times 2 !$ या $\frac{4 !}{(4-2) ! 2 !}= ^{4} C_2$

अब, मान लीजिए कि हमारे पास 5 विभिन्न वस्तुएँ $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{E}$ हैं। इनमें से एक समय में 3 वस्तुओं को लेकर, यदि हम संचय बनाते हैं, तो ये $\mathrm{ABC}, \mathrm{ABD}, \mathrm{ABE}, \mathrm{BCD}, \mathrm{BCE}, \mathrm{CDE}$, $\mathrm{ACE}, \mathrm{ACD}, \mathrm{ADE}, \mathrm{BDE}$ इन ${ }^{5} \mathrm{C} _{3}$ संचयों में से प्रत्येक के संगत 3 ! क्रमचय हैं, क्योंकि प्रत्येक संचय की तीन वस्तुओं को 3 ! तरीकों से पुनर्व्यवस्थित किया जा सकता है। इसलिए क्रमचयों की कुल संख्या $={ }^{5} \mathrm{C} _{3} \times 3$ !

अत: $\quad{ }^{5} \mathbf{P} _{3}={ }^{5} \mathbf{C} _{3} \times 3$ ! या $\frac{5 !}{(5-3) ! 3 !}={ }^{5} \mathrm{C} _{3}$

ये उदाहरण, क्रमचय तथा संचय के बीच संबंध दर्शाने वाली, निम्नलिखित प्रमेय की ओर संकेत करते हैं:

प्रमेय $5{ }^{n} \mathrm{P} _{r}={ }^{n} \mathrm{C} _{r} \quad r !, 0<r \leq n$.

उपपत्ति ${ }^{n} \mathrm{C} _{r}$ संचयों में से प्रत्येक के संगत $r$ ! क्रमचय हैं, क्योंकि प्रत्येक संचय के $r$ वस्तुओं को $r$ ! तरीकों से पुनर्व्यवस्थित किया जा सकता है।

अतः $n$ विभिन्न वस्तुओं में से, एक समय में $r$ वस्तुओं को लेकर बनने वाले क्रमचयों की कुल संख्या ${ }^{n} \mathrm{C} _{r} \times r$ !. है। दूसरी ओर यह संख्या ${ }^{n} \mathrm{P} _{r}$ है।

इस प्रकार $ { }^{n} P_r={ }^{n} C_r \times r !, 0<r \leq n $

टिप्पणी 1. उपर्युक्त परिणाम से $\frac{n !}{(n-r) !}={ }^{n} \mathrm{C}_{r} \times r$ !,अर्थात् $\quad{ }^{n} C_r=\frac{n !}{r !(n-r) !}$.

विशेष रूप से, यदि $r=n$, तो ${ }^{n} \mathrm{C}_{n}=\frac{n !}{n ! 0 !}=1$.

2. हम परिभाषित करते हैं कि ${ }^{n} \mathrm{C} _{0}=1$, अर्थात् $n$ विभिन्न वस्तुओं में से केवल उन तरीकों की संख्या की गणना करना है जहाँ कुछ भी वस्तु लिए बिना बनाए गए संचयों की संख्या 1 मानी जाती है। संचयों की गणना करना, जिनमें एक समय में कुछ या सभी वस्तुओं का चयन किया जाता है। कुछ भी वस्तु लिए बिना चयन करना, इस बात के समान है कि सभी वस्तुओं को छोड़ दिया गया है और हमें ज्ञात है कि ऐसा करने का केवल मात्र एक तरीका है। इसी प्रकार, हम परिभाषित करते हैं कि ${ }^{n} \mathrm{C} _{0}=1$.

3. क्योंकि $\frac{n !}{0 !(n-0) !}=1={ }^{n} \mathrm{C} _{0}$, इसलिए, सूत्र ${ }^{n} \mathrm{C} _{r}=\frac{n !}{r !(n-r) !}, r=0$ के लिए भी उपयुक्त है।

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

4. $\quad{ }^{n} \mathrm{C} _{n-r}=\frac{n !}{(n-r) !(n-(n-r)) !}=\frac{n !}{(n-r) ! r !}={ }^{n} \mathrm{C} _{r}$, अर्थात्, $n$ वस्तुओं में से $r$ वस्तुओं का चयन करना, $(n-r)$ वस्तुओं को अस्वीकार करने के समान है।

5. ${ }^{n} \mathrm{C} _{a}={ }^{n} \mathrm{C} _{b} \Rightarrow a=b$ या $a=n-b$, अर्थात् $n=a+b$

प्रमेय 6 ${ }^{n} \mathrm{C} _{r}+{ }^{n} \mathrm{C} _{r-1}={ }^{n+1} \mathrm{C} _{r}$

उपपत्ति हम जानते हैं $\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} $$

उदाहरण 17 यदि ${ }^{n} \mathrm{C} _{9}={ }^{n} \mathrm{C} _{8}$, तो ${ }^{n} \mathrm{C} _{17}$ ज्ञात कीजिए।

हल हम जानते हैं कि ${ }^{n} C_9={ }^{n} C_8$

अर्थात् $\quad \frac{n !}{9 !(n-9) !}=\frac{n !}{(n-8) ! 8 !}$

या $ \quad\quad\quad \frac{1}{9}=\frac{1}{n-8} \text{ or } n-8=9 \text{ or } n=17 $

इसलिए $ \quad \quad { }^{n} C _{17}={ }^{17} C _{17}=1 . $

उदाहरण 18 2 पुरुषों और 3 महिलाओं के एक समूह से 3 व्यक्तियों की एक समिति बनानी है। यह कितने प्रकार से किया जा सकता है? इनमें से कितनी समितियाँ ऐसी हैं, जिनमें 1 पुरुष तथा 2 महिलाएँ हैं?

हल यहाँ क्रम का महत्व नहीं है। अतः हमें संचयों की गणना करनी है। यहाँ पर समितियों की संख्या उतनी ही है, जितनी 5 विभिन्न व्यक्तियों में से एक समय में 3 को लेकर बनने वाले संचयों की संख्या है। इसलिए समिति बनाने के तरीकों की अभीष्ट संख्या $={ }^{5} \mathrm{C}_{3}=\frac{5 !}{3 ! 2 !}=\frac{4 \times 5}{2}=10$.

पुनः 2 पुरुषों में से 1 को चुनने के ${ }^{2} \mathrm{C} _{1}$ तरीके हैं तथा 3 महिलाओं में से 2 चुनने के ${ }^{3} \mathrm{C} _{2}$ तरीके हैं। इसलिए, इस प्रकार की समितियों की अभीष्ट संख्या

$$ ={ }^{2} C_1 \times{ }^{3} C_2=\frac{2 !}{1 ! 1 !} \times \frac{3 !}{2 ! 1 !}=6 $$

उदाहरण 19 52 ताशों की एक गड्डी से 4 पत्तों को चुनने के तरीकों की संख्या क्या है? इन तरीकों में से कितनों में

(i) चार पत्ते एक ही प्रकार (suit) के हैं?

(ii) चार पत्ते चार, भिन्न प्रकार (suit) के हैं?

(iii) तस्वीरें हैं?

(iv) दो पत्ते लाल रंग के और दो काले रंग के हैं?

(v) सभी पत्ते एक ही रंग के हैं?

हल 52 पत्तों में से 4 पत्तों को चुनने के उतने ही तरीके हैं, जितने 52 विभिन्न वस्तुओं में से एक समय में 4 वस्तुओं को ले कर बनने वाले संचय हैं। इसलिए, तरीकों की अभीष्ट संख्या

$$ ={ }^{52} \mathrm{C}_{4}=\frac{52 !}{4 ! 48 !}=\frac{49 \times 50 \times 51 \times 52}{2 \times 3 \times 4}=270725 $$

(i) गड्डी में पत्ते चार प्रकार के हैं ईंट, चिड़ी, हुकुम, पान और प्रत्येक के 13 पत्ते हैं। इसलिए 4 ईंट के पत्ते चुनने के ${ }^{13} \mathrm{C} _{4}$ तरीके हैं। इसी प्रकार 4 चिड़ी के पत्ते चुनने के ${ }^{13} \mathrm{C} _{4} 4$ हुकुम के पत्ते चुनने के ${ }^{13} \mathrm{C} _{4}$ तथा 4 पान के पत्ते चुनने के ${ }^{13} \mathrm{C} _{4}$ तरीके हैं।

इसलिए तरीकों की अभीष्ट संख्या $={ }^{13} C_4+{ }^{13} C_4+{ }^{13} C_4+{ }^{13} C_4$.

$$ =4 \times \frac{13 !}{4 ! 9 !}=2860 $$

(ii) प्रत्येक प्रकार के 13 पत्ते हैं। इसलिए ईंट के 13 पत्तों में से 1 चुनने के ${ }^{13} \mathrm{C}_{1}$ तरीके हैं, पान के 13 पत्तों में से 1 चुनने के ${ }^{13} \mathrm{C} _{1}$, चिड़ी के 13 पत्तों में से 1 चुनने के ${ }^{13} \mathrm{C} _{1}$ तरीके हैं। अतः गुणन सिद्धांत द्वारा, तरीकों की अभीष्ट संख्या

$$ ={ }^{13} C_1 \times{ }^{13} C_1 \times{ }^{13} C_1 \times{ }^{13} C_1=13^{4} $$

(iii) गड्डी में कुल 12 तस्वीरें हैं और इन 12 पत्तों में से 4 पत्ते चुनने हैं। इसे ${ }^{12} \mathrm{C} _{4}$ तरीकों से किया जा सकता है। इसलिए तरीकों की अभीष्ट संख्या $=\frac{12 !}{4 ! 8 !}=495$.

(iv) गड्डी में 26 लाल रंग के और 26 काले रंग के पत्ते हैं। अतः तरीकों की अभीष्ट संख्या

$$ \begin{aligned} & ={ }^{26} \mathrm{C} _{2} \times{ }^{26} \mathrm{C} _{2} \\ & =\frac{26 !}{2 ! 24 !}^{2}=(325)^{2}=105625 \end{aligned} $$

(v) 26 लाल रंग के पत्तों में से 4 पत्ते ${ }^{26} \mathrm{C} _{4}$ तरीकों से चुने जा सकते हैं। 26 काले रंगे के पत्तों में से 4 पत्ते ${ }^{26} \mathrm{C} _{4}$ तरीकों से चुने जा सकते हैं।

अत: तरीकों की अभीष्ट संख्या $={ }^{26} C_4+{ }^{26} C_4$ $$ =2 \times \frac{26 !}{4 ! 22 !}=29900 . $$

प्रश्नावली 6.4

1. यदि ${ }^{n} \mathrm{C} _{8}={ }^{n} \mathrm{C} _{2}$, तो ${ }^{n} \mathrm{C} _{2}$ ज्ञात कीजिए।

Show Answer

Answer

/#missing

2. $n$ का मान निकालिए, यदि

(i) ${ }^{2 n} \mathrm{C} _{2}:{ }^{n} \mathrm{C} _{2}=12: 1$

(ii) ${ }^{2 n} \mathrm{C} _{3}:{ }^{n} \mathrm{C} _{3}=11: 1$

Show Answer

Answer

/#missing

3. किसी वृत्त पर स्थित 21 बिंदुओं से होकर जाने वाली कितनी जीवाएँ खींची जा सकती हैं?

Show Answer

Answer

/#missing

4. 5 लड़के और 4 लड़कियों में से 3 लड़के और 3 लड़कियों की टीमें बनाने के कितने तरीके हैं?

Show Answer

Answer

/#missing

5. 6 लाल रंग की, 5 सफेद रंग की और 5 नीले रंग की गेंदों में से 9 गेंदों के चुनने के तरीकों की संख्या ज्ञात कीजिए, यदि प्रत्येक संग्रह में प्रत्येक रंग की 3 गेंदें हैं।

Show Answer

Answer

/#missing

6. 52 पत्तों की एक गड्डी में से 5 पत्तों को लेकर बनने वाले संचयों की संख्या निर्धारित कीजिए, यदि प्रत्येक संचय में तथ्यतः एक इक्का है।

Show Answer

Answer

/#missing

7. 17 खिलाड़ियों में से, जिनमें केवल 5 खिलाड़ी गेंदबाज़ी कर सकते हैं, एक क्रिकेट टीम के 11 खिलाड़ियों का चयन कितने प्रकार से किया जा सकता है, यदि प्रत्येक टीम में तथ्यतः 4 गेंदबाज़ हैं?

Show Answer

Answer

/#missing

8. एक थैली में 5 काली तथा 6 लाल गेंद हैं। 2 काली तथा 3 लाल गेदों के चयन के तरीकों की संख्या निर्धारित कीजिए।

Show Answer

Answer

/#missing

9. 9 उपलब्ध पाठ्यक्रमों में से, एक विद्यार्थी 5 पाठ्यक्रमों का चयन कितने प्रकार से कर सकता है, यदि प्रत्येक विद्यार्थी के लिए 2 विशिष्ट पाठ्यक्रम अनिवार्य हैं?

Show Answer

Answer

/#missing

विविध उदाहरण

उदाहरण 20 INVOLUTE शब्द के अक्षरों से, अर्थपूर्ण या अर्थहीन प्रत्येक 3 स्वरों तथा 2 व्यंजनों वाले, कितने शब्दों की रचना की जा सकती है?

हल शब्द INVOLUTE, में I,O,E, तथा U, 4 स्वर और N, V, L तथा T, 4 व्यंजन हैं

4 में से 3 स्वरों के चयन के तरीकों की संख्या $={ }^{4} C_{3}=4$.

4 में से 2 व्यंजनों के चयन के तरीकों की संख्या $={ }^{4} \mathrm{C}_{2}=6$.

अतः 3 स्वरों तथा 2 व्यंजनों के संचय की संख्या $4 \times 6=24$.

अब, इन 24 संचयों में से प्रतयेक में 5 अक्षर हैं, जिन्हें परस्पर एक दूसरे के साथ 5! प्रकार से विन्यासित किया जा सकता है। अतएव विभिन्न शब्दों की अभीष्ट संख्या $24 \times 5 !=2880$.

उदाहरण 21 किसी समूह में 4 लड़कियाँ और 7 लड़के हैं। इनमें से 5 सदस्यों की एक टीम का चयन कितने प्रकार से किया जा सकता है, यदि टीम में (i) एक भी लड़की नहीं है ? (ii) कम से कम एक लड़का तथा एक लड़की है? (iii) कम से कम 3 लड़कियाँ हैं ?

हल (i) क्योंकि टीम में कोई भी लड़की सम्मिलित नहीं है, इसलिए केवल लड़कों का चयन करना है। 7 लड़कों में से 5 लड़कों का चयन ${ }^{7} \mathrm{C} _{5}$ प्रकार से किया जा सकता है। अतः अभीष्ट संख्या $={ }^{7} \mathrm{C} _{5}=\frac{7 !}{5 ! 2 !}=\frac{6 \times 7}{2}=21$

(ii) क्योंकि प्रत्येक टीम में कम से कम एक लड़की तथा एक लड़का है, इसलिए टीम निम्नलिखित प्रकार से चयनित होगी:

(a) 1 लड़का तथा 4 लड़कियाँ

(b) 2 लड़के तथा 3 लड़कियाँ

(c) 3 लड़के तथा 2 लड़कियाँ

(d) 4 लड़के तथा 1 लड़की

1 लड़का तथा 4 लड़कियों का चयन ${ }^{7} C_1 \times{ }^{4} C_4$ प्रकार से किया जा सकता है।

2 लड़के तथा 3 लड़कियों का चयन ${ }^{7} C_2 \times{ }^{4} C_3$ प्रकार से किया जा सकता है।

3 लड़के तथा 2 लड़कियों का चयन ${ }^{7} C_3 \times{ }^{4} C_2$ प्रकार से किया जा सकता है।

4 लड़के तथा 1 लड़की का चयन ${ }^{7} C_4 \times{ }^{4} C_1$ प्रकार से किया जा सकता है।

अत: अभीष्ट संख्या

$ \begin{aligned} & ={ }^{7} C_1 \times{ }^{4} C_4+{ }^{7} C_2 \times{ }^{4} C_3+{ }^{7} C_3 \times{ }^{4} C_2+{ }^{7} C_4 \times{ }^{4} C_1 \\ & =7+84+210+140=441 \end{aligned} $

(iii) क्योंकि टीम में कम से कम 3 लड़कियाँ हैं, इसलिए टीम की रचना निम्नलिखित प्रकार से हो सकती है: (a) 3 लड़ियाँ तथा 2 लड़के अथवा (b) 4 लड़कियाँ तथा 1 लड़का।

नोट कीजिए कि टीम में सभी 5 लड़कियाँ नहीं हो सकतीं, क्योंकि समूह में केवल 4 लड़कियाँ हैं।

3 लड़कियों तथा 2 लड़कों का चयन ${ }^{4} C_3 \times{ }^{7} C_2$ प्रकार से किया जा सकता है।

4 लड़कियों तथा 1 लड़के का चयन ${ }^{4} C_3 \times{ }^{7} C_2$ प्रकार से किया जा सकता है।

इसलिए अभीष्ट संख्या

$ ={ }^{4} C_3 \times{ }^{7} C_2+{ }^{4} C_4 \times{ }^{7} C_1=84+7=91 $

उदाहरण 22 AGAIN शब्द के अक्षरों से बनने वाले, अर्थपूर्ण या अर्थहीन, शब्दों की संख्या ज्ञात कीजिए। यदि इन शब्दों को इस प्रकार लिखा जाए जिस प्रकार किसी शब्दकोश में लिखा जाता है, तो 50 वाँ शब्द क्या है?

हल AGAIN शब्द में 5 अक्षर हैं, जिनमें $\mathrm{A}$ दो बार आता है। इसलिए शब्दों की अभीष्ट संख्या $=\frac{5 !}{2 !}=60$

$A$ से प्रारंभ होने वाले शब्दों की संख्या ज्ञात करने के लिए, हम $A$ को सबसे बाएँ स्थान पर स्थिर कर देते हैं, और फिर शेष 4 भिन्न अक्षरों का, एक समय में सभी को लेकर पुनर्विन्यासित करते हैं। इन विन्यासों की संख्या उतनी ही है, जितनी 4 विभिन्न वस्तुओं से, एक समय में सभी को लेकर बनने वाले क्रमचयों की संख्या है। अतएव $A$ से प्रारंभ होने वाले शब्दों की संख्या $=4 !=24$ फिर $\mathrm{G}$ से प्रारंभ होने वाले शब्दों की संख्या $=\frac{4 !}{2 !}=12$ क्योंकि $\mathrm{G}$ को सबसे बाएँ स्थान पर स्थापित करने के बाद हमारे पास अक्षर $A, A, I$ तथा $N$ शेष रहते हैं। इसी प्रकार I से प्रारंभ होने वाले शब्दों की संख्या 12 है। इस प्रकार अभी तक प्राप्त शब्दों की संख्या $=24+12+12=48$ अब 49 वाँ शब्द NAAGI है। अत: 50 वाँ शब्द NAAIG है।

उदाहरण $231,2,0,2,4,2,4$ अंकों के प्रयोग द्वारा 1000000 से बड़ी कितनी संख्याएँ बन सकती हैं?

हल क्योंकि 1000000 एक 7 अंकीय संख्या है और प्रयोग किए जाने वाले अंकों की भी संख्या 7 है, इसलिए केवल 7 अंकीय संख्याओं की ही गणना उत्तर में की जाएगी। इसके अतिरिक्त क्योंकि रचित संख्याओं को 1000000 से बड़ा होना चाहिए, अतः उन संख्याओं को 1,2 या 4 से प्रारंभ होना चाहिए।

1 से प्रारंभ होने वाली संख्याओं की संख्या $=\frac{6 !}{3 ! 2 !}=\frac{4 \times 5 \times 6}{2}=60$, क्योंकि जब 1 को सबसे बाएँ स्थान पर स्थापित कर देते हैं, तो फिर शेष अंक $0,2,2,2,4,4$, को पुनर्विन्यासित करते हैं, जिनमें 2 , तीन बार तथा 4 , दो बार आते हैं।

2 से प्रारंभ होने वाली संख्याओं की कुल संख्या $=\frac{6 !}{2 ! 2 !}=\frac{3 \times 4 \times 5 \times 6}{2}=180$

4 से प्रारंभ होने वाली संख्याओं की कुल संख्या $=\frac{6 !}{3 !}=4 \times 5 \times 6=120$

अतः रचित संख्याओं की अभीष्ट संख्या $=60+180+120=360$

वैकल्पिक विधि

7 अंकीय संख्याओं का विन्यास स्पष्टतया $\frac{7 !}{3 ! 2 !}=420$ है किंतु इनमें वे संख्याएँ भी सम्मिलित हैं, जिनमें 0 सबसे बाएँ स्थान पर है। इस प्रकार के विन्यासों की संख्या $\frac{6 !}{3 ! 2 !}=60$ ( 0 के सबसे बाएँ स्थान पर स्थिर करके)। अतएव, संख्याओं की अभीष्ट संख्या $=420-60=360$

टिप्पणी यदि प्रदत्त सूची के एक या एक से अधिक अंकों की पुनरावृत्ति होती है, तो यह मान लेते हैं, कि किसी भी संख्या में अंकों को उतनी ही बार प्रयोग किया जा सकता है जितनी बार वे सूची में दिए गए हैं, अर्थात्, उपर्युक्त प्रश्न में 1 तथा 0 केवल एक बार प्रयोग किए जा सकते हैं, जबकि 2 तथा 4 , क्रमशः 3 तथा 2 बार प्रयोग किए जा सकते हैं।

उदाहरण 245 लड़कियों और 3 लड़कों को एक पंक्ति में कितने प्रकार से बैठा सकते हैं, जब कि कोई भी दो लड़के एक साथ नहीं बैठते हैं?

हल हम पहले 5 लड़कियों को बैठा देते हैं। इसे 5 ! प्रकार से कर सकते हैं। इस प्रकार के प्रत्येक विन्यास में, तीन लड़कों को केवल गुणा से चिह्नित स्थानों पर बैठाया जा सकता है।

$$ \times G \times G \times G \times G \times G \times $$

गुणा से चिह्नित 6 स्थानों पर 3 लड़को को ${ }^{6} \mathrm{P}_{3}$ तरीकों से बैठाया जा सकता है। अतः गुणन सिद्धांत से, इन तरीकों की कुल संख्या

$$ \begin{aligned} & =5 ! \times{ }^{6} P_{3}=5 ! \times \frac{6 !}{3 !}\\ & =4 \times 5 \times 2 \times 3 \times 4 \times 5 \times 6=14400 \end{aligned} $$

अध्याय 6 पर विविध प्रश्नावली

1. DAUGHTER शब्द के अक्षरों से, कितने अर्थपूर्ण या अर्थहीन शब्दों की रचना की जा सकती है, जबकि प्रत्येक शब्द में 2 स्वर तथा 3 व्यंजन हों ?

Show Answer

Answer

/#missing

2. EQUATION शब्द के अक्षरों से कितने, अर्थपूर्ण या अर्थहीन, शब्दों की रचना की जा सकती है, जबकि स्वर तथा व्यंजक एक साथ रहते हैं?

Show Answer

Answer

/#missing

3. 9 लड़के और 4 लड़कियों से 7 सदस्यों की एक समिति बनानी हैं यह कितने प्रकार से किया जा सकता है, जबकि समिति में,

(i) तथ्यत: 3 लड़कियाँ हैं ?

(ii) न्यूनतम 3 लड़कियाँ हैं?

(iii) अधिकतम 3 लड़कियाँ हैं?

Show Answer

Answer

/#missing

4. यदि शब्द EXAMINATION के सभी अक्षरों से बने विभिन्न क्रमचयों को शब्दकोष की तरह सूचीबद्ध किया जाता है, तो $\mathrm{E}$ से प्रारंभ होने वाले प्रथम शब्द से पूर्व कितने शब्द हैं?

Show Answer

Answer

/#missing

5. $0,1,3,5,7$ तथा 9 अंकों से, 10 से विभाजित होने वाली और बिना पुनरावृत्ति किए कितनी 6 अंकीय संख्याएँ बनाई जा सकती हैं ?

Show Answer

Answer

/#missing

6. अंग्रेज़ी वर्णमाला में 5 स्वर तथा 21 व्यंजन हैं। इस वर्णमाला से 2 भिन्न स्वरों और 2 भिन्न व्यंजनो वाले कितने शब्दों की रचना की जा सकती है?

Show Answer

Answer

/#missing

7. किसी परीक्षा के एक प्रश्नपत्र में 12 प्रश्न हैं जो क्रमशः 5 तथा 7 प्रश्नों वाले दो खंडों में विभक्त हैं अर्थात् खंड I और खंड II. एक विद्यार्थी को प्रत्येक खंड से न्यूनतम 3 प्रश्नों का चयन करते हुए कुल 8 प्रश्नों को हल करना है। एक विद्यार्थी कितने प्रकार से प्रश्नों का चयन कर सकता है?

Show Answer

Answer

/#missing

8. 52 पत्तों की एक गड्डी में से 5 पत्तों के संचय की संख्या निर्धारित कीजिए, यदि 5 पत्तों के प्रत्येक चयन (संचय) में तथ्यतः एक बादशाह है।

Show Answer

Answer

/#missing

9. 5 पुरुषों और 4 महिलाओं को एक पंक्ति में इस प्रकार बैठाया जाता है कि महिलाएँ सम स्थानों पर बैठती हैं। इस प्रकार के कितने विन्यास संभव हैं?

Show Answer

Answer

/#missing

10. 25 विद्यार्थियों की एक कक्षा से, 10 का चयन एक भ्रमण-दल के लिए किया जाता है। 3 विद्यार्थी ऐसे हैं, जिन्होंने यह निर्णय लिया है कि या तो वे तीनों दल में शमिल होंगे या उनमें से कोई भी दल में शामिल नहीं होगा। भ्रमण-दल का चयन कितने प्रकार से किया जा सकता है?

Show Answer

Answer

/#missing

11. ASSASSINATION शब्द के अक्षरों के कितने विन्यास बनाए जा सकते हैं, जबकि सभी ’ $S$ ’ एक साथ रहें?

Show Answer

Answer

/#missing

सारांश

  • गणना का आधारभूत सिद्धांतः यदि एक घटना $m$ विभिन्न तरीकों से घटित हो सकती है, तद्योपरांत एक दूसरी घटना $n$ विभिन्न तरीकों से घटित हो सकती है, तो प्रदत्त क्रम में घटनाओं के घटित होने की संख्या $m \times n$ है।

  • $n$ विभिन्न वस्तुओं में से एक समय में $r$ को लेकर बनने वाले क्रमचयों की संख्या, जबकि पुनरावृत्ति की अनुमति नहीं है, ${ }^{n} \mathrm{P} _{r}$ द्वारा प्रकट की जाती है और ${ }^{n} \mathrm{P} _{r}=\frac{n !}{(n-r) !}$, जहाँ $0 \leq r \leq n$.

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

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

  • $n$ विभिन्न वस्तुओं में से एक समय में $r$ को लेकर बनने वाले क्रमचयों की संख्या, जबकि पुनरावृत्ति की अनुमति है, $n^{r}$ है।

  • $n$ वस्तुओं में से एक समय में सभी को लेकर बनने वाले क्रमचयों की संख्या $\frac{n !}{p _{1} ! p _{2} ! \ldots p _{k} !}$ है जहाँ $p _{1}$ वस्तुएँ एक प्रकार की, $p _{2}$ वस्तुएँ दूसरे प्रकार की, $\ldots, p _{k}$ वस्तुएँ $k$ वें प्रकार की और शेष सभी वस्तुए, यदि कोई हैं तो विभिन्न प्रकार की हैं:

  • $n$ विभिन्न वस्तुओं में से एक समय में $r$ को लेकर बनने वाले संचयों की संख्या को ${ }^{n} \mathrm{C} _{r}$ से प्रकट करते हैं और ${ }^{n} \mathrm{C} _{r}=\frac{n !}{r !(n-r) !}, 0 \leq r \leq n$.

ऐतिहासिक पृष्ठभूमि

भारत में क्रमचय और संचय की संकल्पना की अवधारणा जैन धर्म के अभ्युदय और संभवतः और पहले हुई है। तथापि इसका श्रेय जैनियों को ही प्राप्त है, जिन्होंने ‘विकल्प’ शीर्षक के अंतर्गत इस विषय को गणित के स्वसंपन्न प्रकरण के रूप में विकसित किया।

जैनियों में महावीर (सन् 850 ई. के लगभग) संभवतः विश्व के प्रथम गणितज्ञ हैं, जिन्होंने क्रमचय और संचय के सूत्रों को देकर श्रेयस्कर कार्य किया।

ईसा के पूर्व छठी शताव्दी में सुश्रुत ने अपने औषधि विज्ञान की सुप्रसिद्ध पुस्तक सुश्रुत-संहिता में उद्घोषित किया कि 6 विभिन्न रसों से एक साथ एक, दो, …, आदि लेकर 63 संचय बनाए जा सकते हैं। ईसा से तीसरी शताब्दी पूर्व संस्कृतविद् पिंगल ने दिए गए अक्षरों के समूह से एक, दो, …, इत्यादि लेकर बनाए गए संचयों की संख्या ज्ञात करने की विधि का वर्णन अपने सुप्रसिद्ध ग्रंथ छंद सूत्र में किया है। भास्कराचार्य (जन्म 1114 ई.) ने अपनी प्रसिद्ध पुस्तक लीलावती में अंकपाश शीर्षक के अंतर्गत क्रमचय और संचय प्रकरण पर उत्कृष्ट कार्य किया है। महावीर द्वारा प्रदत्त ${ }^{n} \mathrm{C} _{r}$ और ${ }^{n} \mathrm{P} _{r}$ के सूत्रों के अतिरिक्त भास्कराचार्य ने विषय संबंधी अनेक प्रमेयों और परिणामों का उल्लेख किया है।

भारत के बाहर क्रमचय और संचय संबंधी प्रकरणों पर कार्य का शुभारंभ चीनी गणितज्ञों द्वारा उनकी सुप्रसिद्ध पुस्तक आई किंग (I-King) में वर्णित है। इस कार्य के सन्निकट काल को बता पाना कठिन है, क्योंकि 213 ई. पूर्व में तत्कालीन सम्राट ने आदेश दिया था कि सभी पुस्तकें तथा हस्तलिखित पाण्डुलिपियाँ जला दी जाएं। सौभाग्यवश इसका पूर्ण रूप से पालन नहीं हुआ। यूनानी और बाद में लैटिन गणितज्ञों ने भी क्रमचय और संचय के सिद्धांत पर कुछ छिटपुट कार्य किये हैं।

कुछ अरबी और हेत्रो लेखकों ने भी क्रमचय और संचय की संकल्पनाओं का प्रयोग ज्योतिष के अध्ययन के लिए किया। उदाहरणतः Rabbi ben Ezra ने ज्ञात ग्रहों की संख्या से एक बार में एक, दो, …, आदि लेकर बनाए संचयों की संख्या ज्ञात की। यह कार्य 1140 ई. पूर्व में हुआ ऐसा प्रतीत होता है कि Rabbi ben Ezra को ${ }^{n} \mathrm{C} _{r}$ का सूत्र ज्ञात नहीं था, तथापि वे इससे परचित थे कि $n$ और $r$ के कुछ विशेष मानों के लिए ${ }^{n} \mathrm{C} _{r}={ }^{n} \mathrm{C} _{n-r}$ होता है। सन 1321 ई. में हीब्रु लेखक, Levi Ben Gerson ने ${ }^{n} \mathrm{P} _{r},{ }^{n} \mathrm{P}$ के सूत्रों के साथ ${ }^{n} \mathrm{C} _{r}$ के व्यापक सूत्रों को बतलाया।

प्रथम ग्रंथ जिसमें क्रमचय और संचय विषय पर पूर्ण और क्रमबद्ध कार्य Ars Conjectandi है जिसका लेखन स्विस गणितज्ञ Jacob Bernoulli (1654-1705 ई.) ने किया। इसका प्रकाशन उनके मरणोपरांत 1713 ई. में हुआ। इस पुस्तक में मुख्यतः क्रमचय और संचय के सिद्धांतों का ठीक उसी प्रकार वर्णन है जैसा कि हम आजकल करते हैं।



Table of Contents