Permutations and Combinations Set 3

Go back to  'SOLVED EXAMPLES'

Example – 24

Consider n points in a plane such that no three of them are collinear. These n points are joined in all possible ways by straight lines. Of these straight lines so formed, no two are parallel and no three are concurrent. Find the number of the points of intersection of these lines exclusive of the original n points.

Solution:   To gain more insight into the problem, let us consider the case when n = 4.

Fig. 15

We originally have 4 points in the plane labelled as A, B, C and D. When we draw all the straight lines possible (by joining every possible pair of points), we see that 3 new intersection points are generated, labelled as 1, 2 and 3.

As we now discuss the general case, refer to this figure for help.

Since we have n points, the number of straight lines that can be generated is equal to the number of pairs of points that can be selected from n  points, which is equal to \({}^n{C_2}\) . Every pair of straight lines so generated will intersect at some point. Thus, the total number of intersection points if we count this way should be equal to the number of pairs of straight lines possible from the  \({}^n{C_2}\) lines, which    is \({}^{({}^n{C_2})}{C_2}\) .

However, observe that in this number, the original intersection points have also been counted, and that too multiple times. Lets determine how many times a particular point, say A has been counted.(n – 1) lines pass through A. Thus \({}^{n - 1}{C_2}\)  pairs of straight lines are possible from these (n – 1) lines. Thus,  A has been counted \({}^{n - 1}{C_2}\)  times. This means that the n original points have been counted \(n \times {}^{n - 1}{C_2}\)  times.

To calculate the new intersection points, we subtract this number from the (supposed) number  of intersection points we obtained earlier.

Thus, the actual number of new intersection points is

\[{}^{({}^n{C_2})}{C_2} - n \times {}^{n - 1}{C_2}\]

\[\begin{align}{}  \qquad\qquad\qquad\qquad\qquad&= \frac{{\frac{{n(n - 1)}}{2}\left( {\frac{{n(n - 1)}}{2} - 1} \right)}}{2} - \frac{{n \times (n - 1)(n - 2)}}{2}\\&= \frac{{n(n - 1)({n^2} - n - 2)}}{8} - \frac{{n(n - 1)(n - 2)}}{2}\\ &= \frac{{n(n - 1)\{ ({n^2} - n - 2) - 4(n - 2)\} }}{8}\\&= \frac{{n(n - 1)({n^2} - 5n + 6)}}{8}\\ &= \frac{{n(n - 1)(n - 2)(n - 3)}}{8}\end{align}\]

Verify that this formula works for n = 4

Example – 25

How many 4 letters strings can be formed from the letters of the work INEFFECTIVE ?

Solution: Observe that some letters repeat more than once:

Letter E F I C T V N
Frequency 3 2 2 1 1 1 2

   

This means that our string of 4 letters could contain repeated letters. (It’s thus obvious that we cannot  straightway use \({}^n{P_r}\)  to evaluate the number of strings.

In such a case, we divide the types of strings that we can form into different mutually exclusive cases:

Case 1:      All 4 letters are different

In this case, we have 7 letters to choose from and we have to arrange them in 4 places. The number of such strings will be \({}^7{P_4} = 840\)

Case 2:      2 letters are same, the other 2 are different

We have 3 types of letters (E, F and I) that can be repeated twice. Thus, the twice-repeated letter can be selected in 3 ways. Once that is done, the rest of the 2 letters can be selected from amongst the remaining 6 options in \({}^6{C_2} = 15\)  ways. Once we’ ve formed the combination of the 4 letters we can permute them in  \(\begin{align}\frac{{4!}}{{2!}} = 12\end{align}\) ways. The “2!” occurs in the denominator because of the twice-repeated letter.

Thus, the total number of such strings will be \(3 \times 15 \times 12 = 540\) .

Case 3:      2 letters are the same, the other 2 are also the same

For example, the string “EFEF” will be such a string.

There are 2 letters now that we want to be twice-repeated; observe that there are only 3 types of letters (E, F and I) that can be twice repeated. Thus, the letters that will occur in the string can be selected in \({}^3{C_2} = 3\)  ways. Once that is done, we can permute the 4 letters in \(\begin{align}\frac{{4!}}{{2!2!}} = 6\end{align}\)  ways.

The total number of such strings is therefore 3×6=18.

Case 4: 3 letters are the same, the 4th is different

Only “E” can be repeated thrice so that E must occur in this string. The 4 th letter can be selected in 6 ways. Then, the combination so formed can be permuted in \(\frac{{4!}}{{3!}} = 4\) ways.

The number of such strings is 6 × 4 = 24.

Verify that these four cases are mutually exclusive and they exhaust all the possibilities.

The total number of strings is 840 + 540 + 18 + 24 = 1422

Example – 26

(a) In how many ways can 3 girls and 9 boys be seated in 2 vans, each having numbered seats with 3 seats in the front and 4 seats at the back?

(b) How many seating arrangements are possible if 3 girls should sit together in a back row on adjacent seats?

Solution: (a) We have 12 people to seat and 14 available seats. We first select the 12 seats on which to seat these people. This can be done in   \({}^{14}{C_{12}}\) ways.

Once that is done, we can permute the 12 people amongst these 12 seats in 12! ways.

Thus, the total number of seating arrangements is \({}^{14}{C_{12}} \times 12!\)  .

(b) Since the 3 girls need to be seated together in one back row, we first select the back row. This can be done in 2 ways since there are 2 vans. In this row, 3 adjacent seats can be selected in 2 ways.

\[\begin{gathered}\underbrace {\begin{array}{*{20}{c}}{\boxed{}}&{\boxed{}}&{\boxed{}} \end{array}}_{}\,\,\,\,\,\,\boxed{} &  & \boxed{}\,\,\,\,\,\,\underbrace {\begin{array}{*{20}{c}}{\boxed{}}&{\boxed{}}&{\boxed{}}\end{array}}_{} \hfill \\{\text{                    selection of 3 adjacent seats }} \hfill \\{\text{                    }}\,\,\,{\text{can be done in 2 ways}}{\text{.}} \hfill \\\end{gathered} \]

In the 3 adjacent seats, the 3 girls can be permuted in 3! ways.

Thus, the girls can be seated in 2×2×3! = 24 ways. We now have 11 remaining seats. The 9 boys can be seated in these 11 seats in \({}^{{\rm{11}}}{P_9}\)  ways.

Thus, the total number of ways to seat the entire group is \(24 \times {}^{{\rm{11}}}{P_9} = 24 \times \frac{{11!}}{{2!}} = 12 \times 11! = 12!\) .

Example – 27

We have 3n objects, of which n are identical and the rest are all different. In how many ways can we select n objects from this group ?

Solution: To select n objects, we select k objects from the identical ones and the remaining (nk) from the different ones. ( k will vary from 0 to n) As discussed somewhere earlier, from the group containing identical objects, there will always be only 1 way of selection. From the group of 2n non-identical objects, (nk) objects can be selected in \({}^{2n}{C_{n - k}}\)   ways.

Thus, the group of n objects containing k identical objects and the remaining (nk) as non-identical objects can be formed in   \(1 \times {}^{2n}{C_{n - k}} = {}^{2n}{C_{n - k}}\) ways. The total number of ways is S where

\[S = \sum\limits_{k = 0}^n {{}^{2n}{C_{n - k}} = {}^{2n}{C_n} + {}^{2n}{C_{n - 1}} + ...{}^{2n}{C_0}} \]

A closed-form expression for S can be obtained by the following manipulation :

\[2S = 2({}^{2n}{C_n} + {}^{2n}{C_{n - 1}} + ... + {}^{2n}{C_0})\]

\[\,\,\,\,\,\,\, = \left\{ \begin{array}{l}{}^{2n}{C_n} + {}^{2n}{C_{n - 1}} + ... + {}^{2n}{C_0}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + \\{}^{2n}{C_n} + {}^{2n}{C_{n - 1}} + ... + {}^{2n}{C_0} \end{array} \right\}\] \[\,\,\,\,\,\,\, = \left\{ \begin{array}{l}{}^{2n}{C_n} + {}^{2n}{C_{n - 1}} + ... + {}^{2n}{C_0}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + \\{}^{2n}{C_n} + {}^{2n}{C_{n + 1}} + ... + {}^{2n}{C_{2n}} \end{array} \right\}\left( \begin{array}{l}{\rm{For all the terms in the }}\\{\rm{lower row, we can use}}\\{}^{{\rm{2}}n}{C_r} = {}^{{\rm{2}}n}{C_{2n - r}}\end{array} \right)\]

\[\,\,\,\,\,\,\,\, = {}^{2n}{C_n} + ({}^{2n}{C_0} + {}^{2n}{C_1} + {}^{2n}{C_2} + ... + {}^{2n}{C_{2n}})\]

\[\,\,\,\,\,\,\,\, = {}^{2n}{C_n} + {2^{2n}}\left( {This{\rm{ }}step{\rm{ }}uses{\rm{ }}the{\rm{ }}result{\rm{ }}of{\rm{ }}example{\rm{ }} - {\rm{ }}7} \right)\]

\[ \Rightarrow S\, = \frac{1}{2} \cdot {}^{2n}{C_n} + {2^{2n - 1}}\]

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