Permutations and Combinations Set 2

Go back to  'SOLVED EXAMPLES'

Example – 20

Give combinatorial arguments to prove that

\[\sum\limits_{r = 1}^n r  \cdot {}^n{C_r} = n \cdot {2^{n - 1}}\]

Solution:  Let us first interpret what the left hand side of this assertion says.

Suppose we have a group of n people. We select a sub-group of size r from the group of n people. This can be done in  \({}^n{C_r}\) ways. Once the sub-group has been formed, we select a leader of that sub-group, and send that sub-group on an excursion. The leader can be selected in r ways. Thus, the total number of different ways in which an r - group can be formed with a unique leader is  \(r \times {\,^n}{C_r}\)    .

Now r can take any integer value from 1 to n, i.e. \(1 \le r \le n\)  . Thus, the total number of all possible sub-groups, each sub-group being assigned a unique leader, will be \(\sum\limits_{r = 0}^n r  \cdot {}^n{C_r}\)  which is the left hand side of our assertion.

To prove this equal to the right hand side, we count the sub-groups from a different angle. We count all those sub-groups in which a particular person, say A, is the leader.

Since A is the leader, A is fixed in our sub-group. For each of the remaining (n – 1) people, we have two options.  We either put the person in the group led by A or we don’t. Thus, the total number of sub-groups in which A is the leader will be

\[\underbrace {2 \times 2 \times 2 \times ... \times 2}_{(n - 1)\,\,{\rm{times}}} = {2^{n - 1}}\]

Since any of the n persons can be the leader, and under each person’s leadership, \({2^{n - 1}}\)   groups can be formed,   the total number of sub-groups, each sub-groups under some unique person’s leadership is   \(n \cdot {2^{n - 1}}\) . This proves our assertion that

\[\sum\limits_{r = 1}^n r  \cdot {}^n{C_r} = n \cdot {2^{n - 1}}\]

Example – 21

A composition of a natural number N is a sequence of non-zero integers  \(\left\{ {{a_1},{\rm{ }}{a_2}{\rm{ }}..........{\rm{ }}{a_k}} \right\}\)  which add up to N. How many compositions of N exist?

Solution:   Let us make the question more clear by taking a particular example for N, say N = 4.

As described in the question, the compositions of N = 4 will be \(\left\{ 4 \right\},\,\,\left\{ {1,\,\,3} \right\},\,\left\{ {2,2} \right\},\,\,\left\{ {3,1} \right\},\,\,\left\{ {1,1,2} \right\},\left\{ {1,2,1} \right\},\,\,\left\{ {2,\,1,1} \right\}\,\,{\rm{and}}\,\,\left\{ {1,\,1,\,1,1} \right\}\)   which are 8 in number.

Observe carefully the compositions listed out. How can we characterize each of these compositions mathematically? Recall the problem of finding the number of non-negative solutions of the integral equation \({x_1} + {x_2} + ....... + {x_n} = r\) where each solution corresponded to a unique permutation of r  “ 1 “symbols and n - 1 "\(\fbox{}\)"  symbols. Can we do something like that here? In other words, can we represent each composition in another form whose permutations are easier to count?

It turns out that we can, as follows:

\[\begin{align}
  & \{4\}\qquad\qquad=\quad 1\ \ \ \ \ \ \ 1\ \ \ \ \ \ 1\ \ \ \ \ \ \,1 \\ 
 & \{1,3\}\quad \qquad=\quad 1\ \; +1\ \ \ \ \ \ 1\ \ \ \ \ \,\,\,1 \\ 
 & \{3,1\}\quad \qquad=\quad 1\ \ \ \ \ \ \,1\ \ \ \ \ \; 1\ \ \ +1 \\ 
 & \{2,2\}\qquad\quad=\quad 1\ \ \ \ \ \ \ 1\ \ +1\ \ \ \ \ \ \,1 \\ 
 & \{1,1,2\}\qquad =\quad  1\ \ \ +1\ +1\ \ \ \ \ \ \ 1 \\ 
 & \{1,2,1\}\qquad=\quad  1\ \ \ \ +1\ \ \ \ \ 1\ \  +1 \\ 
 & \{2,1,1\}\qquad = \quad 1\ \;\;\;\;\;\;\;1\  +1\;+1 \\ 
 & \{1,1,1,1\}\quad \,=\quad 1\ \ \ \ +1\ \ +1\,+1  
\end{align}\]

On the right hand side, we have 4 “1”s and thus 3 blank spaces between the 4 “1” s. We can insert “+” signs in these blank spaces; each different arrangement of  “+” signs in these blank spaces will correspond to a different composition.

To count the number of these arrangements, we proceed as follows: For each blank space, we have 2 options, we can either insert or not insert a “+” sign into that space. There are 3 blank spaces; so the total number of all arrangements of “+” signs in the 3 blank spaces is 2 × 2 × 2 = 8 (which is the number of compositions we already listed out).

In the general case, we will have (N – 1) blank spaces and 2 options for each such blank space. Thus, the total number of ways in which we can arrange “+” signs in these blank spaces, and therefore, the total number of compositions, will be  \(\underbrace {2 \times 2 \times 2 \times ........2}_{\left( {N - 1} \right)\,\,{\rm{times}}} = {2^{N - 1}}\)

Example – 22

Prove logically the following assertion:

\[\sum\limits_{k = 0}^n {{2^k} \cdot {\,^n}{C_k} = {3^n}} \]

Solution: Suppose that we have to form a string of length n, consisting of only letters from the set {A, B, C}. Thus, we have 3 options to fill any particular place in the string:

We fill that place with either A, B or C. Thus the total number of different strings oflength n would be\[\underbrace {3 \times 3 \times 3 \times ........ \times 3}_{n\,\,{\rm{times}}}\,\,\, = {3^n}\]

We now approach the task of formation of these strings from a different perspective.

Suppose that our string contains a total of rA” s. How many such strings will exist? We first select r places out of n which we will fill with “A”. This can be done in nCr ways.  For each of the remaining (n ­– r) places, we have two options; we either fill it with “B” or “C”. Thus, the number of strings containing rA” s will be \(^n{C_r}{.2^{n - r}}\).

Now we vary r from 0 to n and thus get the total number of strings as

\[\sum\limits_{r = 0}^n {{\,^n}{C_r} \cdot {2^{n - r}}}  = \sum\limits_{k = 0}^n {{\,^n}{C_{n - k}} \cdot {2^k}\,\,\,\,\,\,} \left( {{\rm{where}}\,\,k = n - r} \right)\]

\[ = \sum\limits_{k = 0}^n {{\,^n}{C_k} \cdot {2^k}} \left( {{\rm{since}}\,{\,^n}{C_{n - k}} = {\,^n}{C_k}} \right)\] .

Thus, \(\sum\limits_{k = 0}^n {{\,^n}{C_k} \cdot {2^k}}  = {3^n}\)

Example – 23

Prove logically the following assertion:

\[{\,^n}{C_r} + {\,^{n - 1}}{C_r} + {\,^{n - 2}}{C_r} + ...... + {\,^r}{C_r} = {\,^{n + 1}}{C_{r + 1}}\]

Solution:   The right hand side says that we have to select (r  + 1) people out of a group of (n +1).

To do so, we list down the following (mutually exclusive) cases which exhaust all the possible cases:

(1)        The group contains \({A_1}\):

  \(^n{C_r}\)  ways (since we have to select r people  more apart from\({A_1}\) from n that are available for selection)

(2)        The group does not contain ways \({A_1}\) but contains \({A_2}\):

    \(^{n - 1}{C_r}\) (since we have to select r people  more apart from \({A_2}\)  from (n – 1)   that are  available for selection)

(3)       The group does not contain \({A_1}\) and\({A_2}\) but contains \({A_3}\)      :

  \(^{n - 2}{C_r}\) ways (since we have to select r people more apart from \({A_3}\)  from (n – 2) that are available for selection)

.

.

.

(nr) The group does not contain \({A_1},{A_2}...{A_{n - r-1}}\) but contains \({A_{n - r }}\):     

  \(^r{C_r}\)  ways (since we have to select r people more apart from Anr from the (r+1) that are available for selection

(nr + 1) The group does not contain \({A_1},{A_2}...{A_{n - r}}\) but contains \({A_{n - r + 1}}\) :

\(^r{C_r}\) ways (since we have to select r more  people apart from  \({r_{n - r + 1}}\)  from the remaining r that are available for selection)

Convince yourself that all these cases are mutually exclusive and exhaust all the possibilities. Thus, the total number of (r + 1) - groups from (n + 1) people is

\[{}^{n + 1}{C_{r + 1}} = {}^n{C_r} + {}^{n - 1}{C_r} + {}^{n - 2}{C_r} + ... + {}^r{C_r}\]

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