Permutations and Combinations Set 5

Go back to  'SOLVED EXAMPLES'

Example – 32

We have 21 identical balls available with us which we need to be distributed amongst 3 boys  A, B and C such that A always gets an even number of balls. How many ways of doing so are possible?

Solution: The only constraint is that A should get an even number of balls. There’s no constraint on the minimum number of balls a boy should get. This means that a boy can also not be given any ball.

We can represent the number of balls given to A by 2x since A must get an even number of balls. If we represent the number of balls given to B and C by y and z, we should have

\[2x + y + z = 21...{\rm{ }}\left( 1 \right)\]

This means that to find the number of distributions possible, we find the number of non-negative integral solutions to the equation (1).

Note that x can take a maximum value of 10 and a minimum value of 0.

We rearrange (1) so that we get an integral equation with y and z as variables, treating x as a constant

\[y + z = 21 - 2x....{\rm{ }}\left( 2 \right)\]

The number of non-negative integer solutions of (2) is

\[^{21 - 2x + 2\, - 1}{C_1} = \,\,\,\,\,{\,^{22 - 2x}}{C_1} = 22 - 2x\]

We now add the number of solutions so obtained for all the possible values of x. The total number of solutions is therefore \(\sum\limits_{x = \,0}^{10} {\left( {22 - 2x} \right) = 132.} \)

Note: An alert reader must have noticed that we can form arbitrarily complex integer equations. For example, what do we do if we intend to find out the number of non-negative integer solutions to the equation

\[{\alpha _1}{x_1} + {\alpha _2}{x_2} + ...........{\alpha _n}{x_n} = r\]

where the \({\alpha _i}'s\)  are integers that are not necessarily equal to unity.

In addition, what if we impose constraints on \(x_i^′\,s\) the themselves say, we define an upper and lower bound for xi , i.e

\[{l_i} \le {x_i} \le {u_i}\]

For example, how do we distribute 20 apples among 4 boys such that each boy gets more than 2 apples but less that 8 apples, in addition to the constraint that one of the boys, say A, must always get an even number of apples? Think about it. We will revisit the  problem of such general integral equations in example - 39 and in the chapter on Binomial Theorem. There we’ll learn to solve such problems using the Multinomial theorem.

Example – 33

Find the sum of the divisors of 120. Generalise the result for an arbitrary natural number N.

Solution: The divisors of 120 are listed out below:

{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}

The sum of these divisors is 360. We have to determine an elegant way to deduce this sum because we cannot repeat everytime the procedure of listing down all the factors and summing them.

For this purpose, we again resort to the use of the prime factorization form.

\[120 = {2^3} \cdot {3^1} \cdot {5^1}\]

The sum of the divisors will be

\(S = \sum\limits_{\scriptstyle0\, \le \,\,i\,\, \le \,3\atop {\scriptstyle0\, \le \,j\, \le \,1\atop \scriptstyle0\, \le \,k\, \le \,1}} {{2^i} \cdot {3^j} \cdot {5^k}} \)

This notation is simply a shorthand which implies that we vary the integral indices i, j and k (in their respective allowed ranges) and this way we will have listed down all the factors and hence evaluated the required sum.

To generate the expression for the sum S, we can alternatively use the following method:

\[S = \left( {1 + {2^1} + {2^2} + {2^3}} \right)\left( {1 + {3^1}} \right)\left( {1 + {5^1}} \right)\]

Did you realize the trick? Writing S this way also gives rise to all the factors. You are urged to convince yourself about this by expanding this expression and observing that all possible factors will be generated.

Thus, S can now be simply evaluated as follows:

\[S = \left( {1 + {2^1} + {2^2} + {2^3}} \right)\,\,\left( {1 + {3^1}} \right)\,\,\left( {1 + {5^1}} \right)\]

\[\begin{array}{l}= 15 \times 4 \times 6\\= 360\end{array}\]  This is the same result that we got earlier!

To do the general case, assume that the prime factorization form of N is

\[N = p_1^{{\alpha _1}}p_2^{{\alpha _2}}........p_n^{{\alpha _n}}\]

where the  \(\alpha _i^′\) are all positive integers and the \(p_i^′s\) are all primes. The sum S f of all the factors will be

\({S_f} = \left( {1 + {p_1} + p_1^2 + .....p_1^{{\alpha _1}}} \right)\,\,\left( {1 + {p_2} + p_2^2 + ..... + p_2^{{\alpha _2}}} \right).........\left( {1 + {p_n} + p_n^2 + .....p_n^{{\alpha _n}}} \right)\)

 Example – 34

Find the sum of all the five-digit numbers that can be formed using the digits 1, 2, 3, 4 and 5 if no digit is repeated.

Solution: This problem can be solved very easily if we view it from an individual digit’s perspective. Suppose that we only consider the digit “4”. How many numbers will there be with “4” in the units place?

\[\left. \begin{gathered} \boxed{}\,\,\boxed{}\,\,\boxed{}\,\,\boxed{}\,\,4 \hfill \\ \boxed{}\,\,\boxed{}\,\,\boxed{}\,\,\boxed{}\,\,4 \hfill \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\, \vdots \,\,\,\, \hfill \\\,\,\,\,\,\,\,\,\,\,\,\,\,\, \vdots  \hfill \\\hfill \\\boxed{}\,\,\boxed{}\,\,\boxed{}\,\,\boxed{}\,\,4 \hfill \\ \end{gathered}\right\}\,\,\,\,\,\,\,\,\begin{array}{*{20}{c}}  \begin{gathered}{\text{There are 24 numbers with 4 in the }} \hfill \\{\text{units place because the remaining }} \hfill \\{\text{four digits can be permuted among }} \hfill \\{\text{the remaining 4 places in 4! = 24 ways}} \hfill \\ \end{gathered}\end{array}\]

From these 24 numbers, what is the total contribution of the digit “4” to the sum we are required to calculate? Since “4” is at the units place and it occurs 24 times, its contribution will be 4 × 24 = 96

Similarly, there will be 24 numbers where “4” is at the tens place. The total contribution of “4” from these 24 numbers will be 4 × 240 = 960

Proceeding in this way, we see that the total contribution of the digit “4” from all the 120 numbers that can be possibly formed is:

\[\begin{array}{l}4\left( {24 + 240 + 2400 + 24000 + 240000} \right)\\ = 4 \times 24 \times \left( {1 + 10 + 100 + 1000 + 10000} \right)\\ = 4 \times 24 \times \,\,11111 \end{array}\]

This is the contribution to the sum from only the digit “4”. To calculate the entire sum S, we calculate the contributions from all the five digits. Thus, the sum is

\[S = \left( {1 + 2 + 3 + 4 + 5} \right) \times 24 \times 11111\]

= 3999960

Example – 35    DEARRANGEMENTS

Find the number of ways in which 5 different letters can be taken out of their 5 addressed envelopes and put back into the envelopes in such a way that all letters are in the wrong envelope.

Solution: The problem of rearranging objects so that each object is assigned to a place different from its original place is referred to as the problem of dearrangments. Here, we need to find out the number of dearrangements possible with 5 letters and 5 envelopes.

Let us denote by \({D_n} \) the number of dearrangements possible with n things. We will attempts a general solution, that is for an arbitrary n, and then substitute n = 5

Denote by  \({L_i}\)the \({i^{th}}\)   letter and by \({E_i}\), the original envelope of the    \({i^{th}}\) letter.

Consider the envelope\({E_1}\) It can be assigned a wrong letter in (n – 1) ways. Suppose that we assign the letter \({L_2}\) to E

\[\begin{array}{l}{E_1}\,\,\,\,{E_2}\,\,............\,\,{E_n}\\ \nwarrow \\{L_1}\,\,\,\,{L_2}\,\,............\,\,{L_n}\end{array}\]

The dearrangements that can now arise can be divided into two mutually exclusive classes:

(i)  Those in which\({L_1}\) is assigned to \({E_2}\)

(ii)  Those in which \({L_1}\) is not assigned to \({E_2}\)

If \({L_1}\) is assigned to \({E_2}\), we have the following configuration:

\[\begin{array}{l} {E_1}\,\,\,\,{E_2}\,\,............\,\,{E_n}\\\nearrow  \nwarrow \\{L_1}\,\,\,\,{L_2}\,\,............\,\,{L_n} \end{array}\]

In this case, we have a remaining of (n – 2) letters which can be dearranged in\({D_{n - 2}}\) ways.

Suppose the other case now, where we do not assign \({L_1}\) to \({E_2}\). In this case, we have (n – 1) letters to dearrange ( \({L_1}\) will also be counted as a letter to be dearranged since it is being assigned to an envelope other than \({E_2}\)). This can be done in \({D_{n - 1}}\) ways.

Thus, if we give \({L_2}\) to \({E_1}\) the total dearrangements possible are \({{\rm{D}}_{n - 1}}{\rm{ + }}{{\rm{D}}_{n - 2}}\)

Since  \({E_1}\) can assigned a wrong letter in (n –1) ways, the overall total number of dearrangements  \({D_n} \) is

\[{D_n} = \left( {n - 1} \right)\left( {{D_{n - 1}} + {D_{n - 2}}} \right)\]

We have thus related the  \({n^{th}}\)  order 'dearrangements–coefficient' \({D_n} \) to lower order coefficients.

We now have to somehow  use this relation to obtain \({D_n} \) only in terms of n. This is how we do it:

\[{D_n} = \left( {n - 1} \right)\left( {{D_{n - 1}} + {D_{n - 2}}} \right)\]

\[ \Rightarrow  \qquad {D_n} - n{D_{n - 1}} = \left( { - 1} \right)\left( {{D_{n - 1}} - {\,^{\left( {n - 1} \right)}}{D_{n - 2}}} \right)...{\rm{ }}\left( 1 \right)\]

But if we substitute \(n \to \left( {n - 1} \right)\)  we get

\[{D_{n - 1}} - \left( {n - 1} \right){D_{n - 2}} = \left( { - 1} \right)\left( {{D_{n - 2}} - \left( {n - 2} \right){D_{n - 3}}} \right)...{\rm{ }}\left( 2 \right)\]

We substitute (2) back into (1) to get

\[\begin{array}{l}{D_n} - n{D_{n - 1}} = {\left( { - 1} \right)^2}\left( {{D_{n - 2}} - \left( {n - 2} \right){D_{n - 3}}} \right)\\= {\left( { - 1} \right)^3}\left( {{D_{n - 3}} - \left( {n - 3} \right){D_{n - 4}}} \right)\,\,\,\,\left\{ \begin{array}{l}{\rm{By\;the\;same\;}}\\ {\rm{ process}} \end{array} \right\} \end{array}\]

\[ = {\left( { - 1} \right)^{n - 2}}\left( {{D_2} - 2{D_1}} \right)\]

It is obvious that \({D_1} \) = 0 since one letter cannot be dearranged while\({D_2} \) = 1 because two letters can be dearranged in only one way : by exchanging them.

Thus,

\[{D_n} - n{D_{n - 1}} = {\left( { - 1} \right)^{n - 2}}...{\rm{ }}\left( 3 \right)\]

We still have not obtained a relation involving only \({D_n} \). We do it using (3) repeatedly

\[\begin{array}{l}{D_n} - n{D_{n - 1}} = {\left( { - 1} \right)^{n - 2}} = {\left( { - 1} \right)^n}\\  \Rightarrow   \frac{{{D_n}}}{{n!}} - \frac{{{D_{n - 1}}}}{{\left( {n - 1} \right)!}} = \frac{{{{\left( { - 1} \right)}^n}}}{{n!}}\left( {Division{\rm{ }}byn!} \right)\end{array}\]

Now we substitute \(n \to \left( {n - 1} \right),\,\,\,n \to \left( {n - 2} \right)\) .... successively and add the corresponding sides of all the relations so obtained to get

\[\frac{{{D_n}}}{{n!}} - \frac{{{D_1}}}{{1!}} = \frac{{{{\left( { - 1} \right)}^n}}}{{n!}} + \frac{{{{\left( { - 1} \right)}^{n - 1}}}}{{\left( {n - 1} \right)!}} + \frac{{{{\left( { - 1} \right)}^{n - 2}}}}{{\left( {n - 2} \right)!}} + ...... + \frac{{{{\left( { - 1} \right)}^2}}}{{2!}}\]

Since\({D_1} \) = 0, we finally get

\[{D_n} = n!\left( {\frac{1}{{2!}} - \frac{1}{{3!}} + \frac{1}{{4!}} - ........\frac{{{{\left( { - 1} \right)}^n}}}{{n!}}} \right)\]

\[ = n!\left( {1 - \frac{1}{{1!}} + \frac{1}{{2!}} - \frac{1}{{3!}} + ...\frac{{{{\left( { - 1} \right)}^n}}}{{n!}}} \right)\,\,\,\,\,\,\left\{ \begin{gathered} {\text{The first two terms "1"}}\,{\text{and}}\,\,{\text{}}\frac{{\text{1}}}{{{\text{1!}}}}{\text{}} \\ {\text{ are just added to make the }} \\ {\text{series look more sequenced}} \\ \end{gathered} \right\}\]

This is the number of dearrangements possible with n things For n = 5, we have

\[{{\rm{D}}_{\rm{5}}} = 5!\left( {1 - \frac{1}{{1!}} + \frac{1}{{2!}} - \frac{1}{{3!}} + \frac{1}{{4!}} - \frac{1}{{5!}}} \right)\]

\[ = 44\]

Thus, there are 44 ways to rearrange the letters back into their envelopes so that each letter goes to a wrong envelope.

Since n = 5 is a small number, we could have worked out an alternative solution as follows:

\[{\rm{No}}{\rm{. of \;dearrangemets }} = \,\,\left\{ \begin{array}{l}{\rm{Total\;No\;}}{\rm{. \;of \;arrangements\, - }}\\{\rm{No\;}}{\rm{.\; of\;ways\;in\;which\;all\;letters\;go\;to\;}}\\{\rm{correct\;envelopes\, -\, No\;}}{\rm{. \;of\; ways\; in\; }}\\{\rm{which\; one\; letter goes\; to\; incorrect\; envelope\, - \,}}\\{\rm{No\;}}{\rm{.\; of\; ways\; in\; which\; two\; letters\; go\; to\; incorrect\; }}\\{\rm{envelope, - }}.............................{\rm{\;and\; so\; on\;}}\end{array} \right\}\]

You are urged to work out the solution by this way

Learn math from the experts and clarify doubts instantly

  • Instant doubt clearing (live one on one)
  • Learn from India’s best math teachers
  • Completely personalized curriculum