Permutations and Combinations Set 4

Go back to  'SOLVED EXAMPLES'

Example – 28

5 balls are to be placed in 3 boxes. Each box can hold all the 5 balls. In how many ways can we place the balls into the boxes so that no box remains empty, if

(a)  balls and boxes are all different

(b)  balls are identical but boxes are different

(c)  balls are different but boxes are identical

(d) balls as well as boxes are identical

(e)  balls as well as boxes are identical, but the boxes are kept in a row.

Solution: One of the constraints that should always be satisfied is that no box should remain empty. Thus, each box should get at least one ball. This means that the distribution of balls can have the configuration    ( 1, 1, 3) or (1, 2, 2). Only in these two configurations does no box remain empty.

\[\left\{ \begin{array}{l} {\rm{Readers\;might\; observe\;some similarity\; between \;this \;problem \;and \;Example\,-\,14\; }}\\{\rm{where\; we\; discussed\; division\; of\; a\; deck\; of\; cards\; into\; groups\,}}{\rm{. \;Observe\; carefully\;}}\\ {\rm{which \;part \;in \;this\; problem\; corresponds\; to \;which\; case\; in\; Example\,  -\,  14}}\end{array} \right\}\]

(a)  In this case, the balls and the boxes are all different. If you observe carefully, you will note that this case is equivalent to dealing cards to players. Here, we are dealing balls (all different) into boxes (all different). In the card game, we were dealing cards (all different) to players (all different).

Suppose we distribute the balls in the configuration (3, 1, 1). We first divide the group of balls into this configuration. This can be done in \(^5{C_3}\)  ways since we just need to select a group of 3 balls and our division will be accomplished. Once the division of the group of balls into 3-subgroups in the configuration (3, 1, 1) has been done, we can permute the 3 sub-groups among the 3 different boxes in 3! ways.

Thus, the number of ways to achieve the (3, 1, 1) configuration is  \(^5{C_3} \times 3! = 60\)

We now find the number of ways to achieve the (1, 2, 2) configuration .

We first select 2 balls out of the 5 which can be done in \(^5{C_2}\) ways. We then select 2 balls from the remaining 3, which can be done in \(^3{C_2}\)  ways. Thus simple division into the configuration (2, 2, 1) can be achieved in \(\begin{align}\frac{{^5{C_2} \times {\,^3}{C_2}}}{{2!}}\end{align}\)  ways. Division by 2! is required since two subgroups are of the same size and right now we are just dividing into sub groups so the order to the sub-groups doesn’t matter. Once division has been accomplished, we permute the 3 subgroups so formed amongst the 3 different boxes is 3! ways.

Thus, the number of ways to achieve the (2, 2, 1) configuration is  \(\begin{align}\frac{{^5{C_2} \times {\,^3}{C_2}}}{{2!}} \times 3!\,\, = \,\,90\end{align}\)

The total number of ways is 60 + 90 = 150

To make things more clear, let us list down in detail the various configurations possible for the 3 different boxes, A, B & C:

 

Box - A Box - B Box - C Number of ways
1 1 3 20
1 3 1 20
3 1 1 20
1 2 2 30
2 1 2 30
2 2 1 30

Total:150

(b) The balls are now identical so it doesn’t matter which ball goes into which box. What matters is only the configuration of the distribution.

By simple enumeration, only 6 configurations exist for this case. (The notation [a, b, c] implies that Box - A has a balls, Box - B has b balls and Box - C has c balls.)

\[\begin{array}{l}\left[ {1,\,1,3} \right] &  & \left[ {1,\,3,1} \right] &  & \left[ {3,1,1} \right]\\ \left[ {1,\,2,2} \right] &  & \left[ {2,\,1,2} \right] &  & \left[ {2,2,1} \right]\end{array}\]

Thus, 6 possible ways exist for this case

(c)  The boxes are identical. This means that it does not matter which sub-group of balls you put in which box. What matters is only the division of the group of balls. This case is akin to the one where you have to divide a deck of cards into sub-groups. (you aren’t required to distribute those sub-groups to players).

For the configuration (1, 1, 3), the number of ways of division is \({\,^5}{C_3} = 10\) (we just choose 3 balls out the 5 and the division is automatically accomplished.  For the configuration (1, 2, 2), the number of ways of division is \(\begin{align}\frac{{^5{C_2} \times {\,^3}{C_2}}}{{2!}} = 15\end{align}\)    (division by 2! is required since two sub-groups are of the same size, and here the order of the group doesn’t matter)

Thus, the total number of ways is 10 + 15 = 25

(d) This case is quite straightforward. The balls are identical. The boxes are identical too. The only 2 possible configuration are (1, 1, 3) and (1, 2, 2). There can be no permutation of these configurations since the boxes are indistinguishable. Thus, only 2 ways of division exist.

(e)  If we keep the boxes in a row, we have inherently ordered them and made them non-identical, since the boxes can be numbered now.

Therefore, in this case, the balls are identical but the boxes are different so this question becomes the same as the one in part - (b)

Example – 29         PIRATES OF THE CARRIBEAN

In the Caribbean Sea, 13 pirates, while plundering an English ship, come upon a chest full of gold. Since the pirates have found the chest simultaneously, no one can claim the chest as his own.

To protect the chest from the avarices of the pirates, the pirate leader Captain Jack Sparrow suggests a scheme. “We must put a certain number of locks on this chest and distribute their keys amongst ourselves in such a way  that it can be opened only when 7 or more then 7 pirates dicide to open it. In other words, only when a majority of the 13 pirates agree should the chest be able to be opened.”

How can this scheme be implemented? What would be the minimum number of locks required and how must their keys be distributed?

Solution: This interesting problem can be easily solved solved by the application of the elementary concepts developed in this chapter.

Let us rephrase our problem slightly.

We want that only a group of 7 or more pirates should be able to open the chest. This means that whenever such a majority group decides to open the chest, they should have amongst themselves the keys to all the locks on the chest.

Suppose on the other hand, that only 6 pirates decide to open the chest. Then there should be at least one lock on the chest whose key(s) are not with anyone amongst that group of 6. Thus, that single lock will prevent the minority group of 6 pirates from opening the chest.

This is the approach we now follow. For every possible group of 6 pirates, we put a lock on the chest and distribute 7 keys of the lock amongst the remaining 7 pirates. That lock will prevent our group of 6 pirates from opening the chest.

Such a lock will exist for every group of 6 pirates. Thus, whenever any group of 6 pirates decides to open the  chest, they will be prevented by one lock whose keys are with the other 7 pirates (the case when even less than 6 pirates decide to open the chest is automatically solved because then there will be more than one lock to prevent that group from opening the chest)

Also, whenever any group of 7 pirates decides to open the chest, there is no lock whose key is not amongst one of the 7 members of that group. Thus, any group of 7 pirates (or more) will be able to open the chest.

Thus, what we need to do is put \(^{13}{C_6}\left( { = {\,^{13}}{C_7}} \right)\) locks on the chest and for each lock, we select a group of 7 pirates, make 7 keys of that lock and give one key to each member of this group.

Example – 30

Prove that (n!)! is divisible by (n!) (n–1)!

Solution: We can equivalently show that \(\begin{align}\frac{{\left( {n!} \right)!}}{{{{\left( {n!} \right)}^{\left( {n - 1} \right)!}}}}\end{align}\)   is an integer.

To keep things easier, let us take n = 6. Thus, we need to show that   \(\begin{align}\frac{{\left( {6!} \right)!}}{{{{\left( {6!} \right)}^{5\,!}}}}\end{align}\)  is an integer. (You must appreciate the magnitude of the numbers we are dealing with here!)

Consider the following sequence of symbols:

\[a{  _1}a{ _1}a{  _1}a{  _1}a{ _1}a{_1}a{ _2}a{  _2}a{  _2}a{_2}a{  _2}a{  _2}....................{a_{120}}{a_{120}}{a_{120}}{a_{120}}{a_{120}}{a_{120}}\]

This is a sequence of symbols whose length is 720, because each symbol a i occurs 6 times in this sequence and there are in total 120 symbols, and thus the total number of symbols is 6 × 120 = 720. Let us find the number of permutations of this string. Since there are 120 ‘types’ of symbols, each symbol being repeated 6 times, we will have to divide by 6! a total of 120 times, i.e, the number of permutations of this string will be

\[\begin{align}{}&\frac{{\left( {720} \right)!}}{{\underbrace {6!\,\, \times \,\,6!\,\, \times \,\,6!\,\, \times .......}_{120\,\,{\rm{times}}}6!}}\\ &= \frac{{\left( {6!} \right)!}}{{{{\left( {6!} \right)}^{5!}}}}\end{align}\]

Since the number of permutations of any string must obviously be an integer, the term \(\begin{align} = \frac{{\left( {6!} \right)!}}{{{{\left( {6!} \right)}^{5!}}}}\end{align}\)   must be an integer!

We can now easily generalise this result.

Example – 31       

n persons  are seated around a circular table. In how many ways can we select 3 persons such that no 2 of them are adjacent to each other on the table?

Solution: We will solve this problem by first considering the total number of selections possible and then subtracting from this, the number of cases where 2 persons or all the 3 persons are adjacent.

Observe the following figure for reference.

Fig. 16

The total number of ways of selecting 3 persons out of these n is \({\,^n}{C_3}.\)

Let us count the cases where only 2 of the 3 persons are adjacent. 2 adjacent people can be selected as follows:

\(\left\{ {{P_1}{P_2}} \right\}\,\,{\rm{or}}\,\,\left\{ {{P_2}{P_3}} \right\}\,\,{\rm{or}}\,\,\left\{ {{P_3}{P_4}} \right\}...............\,{\rm{or}}\,\,\left\{ {{P_n}{P_1}} \right\}\)

Thus, there are n ways in which 2 adjacent persons can be selected. Once these 2 have been selected (for example, say we select {P 2P3}), we can select the third non-adjacent person in (n – 4) ways (since for example, if we selected {P 2P3}, we cannot select P 1> or P 4). Thus the cases where only 2 of the 3 people are adjacent are n (n – 4) in number.

We now count the cases where all 3 persons are adjacent. 3 persons can be adjacent in the following manner:

\(\left\{ {{P_1}{P_2}{P_3}} \right\}\,{\rm{or}}\,\,\left\{ {{P_2}{P_3}{P_4}} \right\}\,{\rm{or}}\,..................\,{\rm{or}}\left\{ {{P_n}{P_1}{P_2}} \right\}\)

Thus, observe that there are n ways of selecting 3 persons who are adjacent.

Finally, the number of ways to select 3 persons such that no 2 are adjacent is

\[\begin{array}{l}^n{C_3} - n\left( {n - 4} \right) - n\\ = \frac{{n\left( {n - 1} \right)\left( {n - 2} \right)}}{6} - n\left( {n - 4} \right) - n\\= \frac{1}{6}n\left( {n - 4} \right)\left( {n - 5} \right) \end{array}\]

Learn from the best math teachers and top your exams

  • Live one on one classroom and doubt clearing
  • Practice worksheets in and after class for conceptual clarity
  • Personalized curriculum to keep up with school