# Examples on Permutations and Combinations Set 1

** APPLICATIONS OF BASICS **

Our approach in the applications of the basic concepts of counting will be to keep everything really basic - and try to do everything from a first principles approach. Memorization of formulae will do no good! A good deal of thinking is required.

Lets start with proving certain combinatorial assertions.

**Example – 3 **

Prove that \(^n{C_r}{ = ^n}{C_{n - r}}\)

**Solution: ** We can easily prove this relation using the expression we obtained for \(^n{C_r}\) :

\[^n{C_r} = \frac{{n!}}{{r!(n - r)!}} = \frac{{n!}}{{(n - r)!(n - (n - r))!}}{ = ^n}{C_{n - r}}\]

However, what we would really like is not an analytical justification like the one above but a logical justification, that involves no mathematical manipulations and is instead purely based on the interpretation of \(^n{C_r}\) .

For this example, let us discuss such a logical justification in a good amount of detail.

Suppose you have a group of 6 letters, say {*A, B, C, D, E, F*}. Out of this group, you want to count the number of subsets containing 4 letters. Consider a particular selection of 4 letters, say {*B, D, E, F*}. This selection can equivalently be obtained if we say that we *exclude* the group {*A, C*} from our original group of 6 letters. This means that each selected group of 4 letters corresponds to an excluded group of 2 letters. The number of (selected) 4-letter groups will therefore equal the number of (excluded) 2-letter groups, or in other words, to count the number of 4 letter groups, we can equivalently count the number of 2-letter groups. Thus,

\[^6{C_4}{ = ^6}{C_2}\]

Generalizing this logic, we obtain \(^n{C_r}{ = ^n}{C_{n - r}}\)

**Example – 4 **

Prove that \(^n{C_r}{ = ^{n - 1}}{C_r}{ + ^{n - 1}}{C_{r - 1}}\)

**Solution: ** You can prove this assertion yourself very easily analytically. Let us discuss a logical justification.

The left hand side of this assertion says that we have a group of *n* people out of which we want to select a subset of *r* people; more precisely, we want to count the number of such *r*-subsets.

Fix a particular person in this group of *n* people, say person *X*. Now, all the *r*-groups that we form will either contain *X* or not contain *X*. These are the only two options possible.

To count the number of groups that contain *X*, we proceed as follows: we already have *X*; we need (*r* – 1) more people from amongst (*n* – 1) people still available for selection. Thus, such groups will be \(^{n - 1}{C_{r - 1}}\) in number.

For the number of groups that do not contain *X* we need to select *r* people from amongst (*n* –1) options available. Therefore, such groups are \(^{n - 1}{C_r}\) in number. The total number of *r*-groups are hence \(^{n - 1}{C_{r - 1}}{ + ^{n - 1}}{C_r}\) in number, which is the same as \(^n{C_r}\) . With this example, you should begin to realise the beauty of the logic and skill required in this subject.

**Example – 5 **

Prove that \(^n{P_r}{ = ^{n - 1}}{P_r} + {r^{n - 1}}{P_{r - 1}}\)

**Solution: ** The analytical justification is again very straightforward and is left to you as an exercise.

The left hand side of this assertion says that we need to count the number of arrangements of *n* people, taken* r *at a time.

We again fix a particular person, say person *X*. All the possible *r*-arrangements will either contain *X* or not contain *X*. These are the only two (mutually exclusive) cases possible.

If we do not keep *X* in our permutation, we have* r* people to select from a potential group of (*n* – 1) people. The number of arrangements not containing *X* will therefore be \(^{n - 1}{P_r}.\)

To count the number of permutations containing *X*, we first seat *X* in one of the* r* seats available. This can be done in *r* ways. The remaining (*r* – 1) seats can be filled by (*n* –1) people in \(^{n - 1}{P_{r - 1}}\) ways. Thus, the number of arrangements containing *X* is \(r \cdot {}^{n - 1}{P_{r - 1}}\) .

These arguments prove that \(^n{P_r}{ = ^{n - 1}}{P_r} + r{ \cdot ^{n - 1}}{P_{r - 1}}\)

**Example – 6 **

**(a)** Prove that \(\begin{align}^n{C_r} = \frac{n}{r}\,\,{\,^{n - 1}}{C_{r - 1}}\end{align}\) **(b)** Prove that \(\begin{align}^n{C_r} = \frac{{n - r + 1}}{r}\,{\,^n}{C_{r - 1}}\end{align}\)

**Solution: (a)** Let us consider this assertion in a particular example, say with *n* = 6 and *r* = 4. This will make things easier to understand.

Our purpose is to select 4 people out of 6 people, say the set {*A, B, C, D, E, F*}. To select a group of 4, we can first select a single person : this can be done in 6 ways. The rest of the 3 people can now be selected in \(^5{C_3}\) ways. The total number of groups possible would thus be \(6 \times {\,^5}{C_3}\) . But some careful thought will show that we have ‘overcounted’, doing the calculation this way.

Suppose that in our first step, we select *A*. While selecting the remaining 3 persons, we then select *B*, *C*, *D* thus forming the group {*A*, *B*, *C*, *D*}. But this same group would have been formed had we selected *B* in our first step and *A*, *C*, *D* in the second step, or *C* in the first step and *A*, *B*, *D* in the second step, or *D* in the first step and *A*, *B*, *C* in the second step. We have thus counted the group {*A*, *B*, *C*, *D*} 4 times in the figure \(6 \times {\,^5}{C_3}.\) The actual number of groups will hence be \(\begin{align}\frac{{6 \times {\,^5}{C_3}}}{4}.\end{align}\)

We now generalise this: to select *r* people out of a group of *n*, we first select one person; this can be done in *n* ways. The remaining (*r* – 1) persons can be selected in \(^{n - 1}{C_{r - 1}}\) ways. The total number of *r*-groups thus becomes \(n \times {}^{n-1}{C_{r - 1}}\) . However, as described earlier, in this figure each group has been counted *r* times. The actual number of *r*-groups is therefore

\[^n{C_r} = \frac{{n \times {\,^{n - 1}}{C_{r - 1}}}}{r}\]

**(b)** The logic for this part is similar to that of part -(a)

To select *r *people out of *n*, we first select (*r* – 1) people out of *n*. This can be done in \(^n{C_{r - 1}}\) ways. We now have \(n - (r - 1) = (n - r + 1)\) persons remaining for selection out of which we have to choose 1 more person. This can therefore be done in (*n – r *+* *1)ways. The total number of *r*-groups thus becomes \((n - r + 1) \times {\,^n}{C_{r - 1}}.\)

However, each *r*-group has again been counted *r* times in this figure (convice youself about this by thinking of a particular example). The actual number of *r*-group is thus

\[^n{C_r} = \frac{{(n - r + 1) \times {\,^n}{C_{r - 1}}}}{r}\]

**Example – 7**

Prove that \(^n{C_0} + {\,^n}{C_1} + {\,^n}{C_2} + .......... + {\,^n}{C_n} = {2^n}\)

**Solution:** This looks like a tough one! Lets first interpret what the left side means. \(^n{C_0}\) is the number of ways in which we can select ‘nothing’ out of *n* things (there will obviously be only one such way: that we do nothing!). \(^n{C_1}\) is the number of ways in which we can select 1 thing out of *n*. \(^n{C_r}\) is the number of ways of selecting *r* things out of *n*. We want the value of the sum \(\mathop {\mathop \sum \limits_{r = 0} }\limits^n {\,^n}{C_r}\) , which is the number of all groups possible of any size what so ever. Thus, our selection could be any size from 0 to *n *(both inclusive); what we want is the total number of selections possible.

For example, consider the set {*A*, *B*, *C*}. The set of all possible selections that can be made from this set is \(\left\{ {\phi ,\left\{ A \right\},\left\{ B \right\},\left\{ C \right\},\left\{ {AB} \right\},\left\{ {AC} \right\},\left\{ {BC} \right\},\left\{ {ABC} \right\}} \right\}.\) Thus, 8 total different selections are possible (note that \(8 = {2^3}\) )

To count the total number of selections possible if we have *n* persons, we adopt an individual’s perspective. An individual can either be or not be in our selection. Thus, we have two choices with respect to any individual; we either put him in our group or do not put him in our group.

These two choices apply to every individual. Also, choosing or not choosing any individual is independent of choosing or not choosing another. Thus, the total number of ways in which an arbitrary number of individuals can be selected from *n* people is \(\underbrace {2 \times 2 \times 2 \times ........ \times 2}_{n\,\,{\rm{times}}} = {2^n}\)

This proves that

\[\sum\limits_{i = 0}^n {^n{C_i} = {2^n}} \]

**Example – 8 **

Prove that \(^{n + m}{C_r} = {\,^n}{C_0}{\,^m}{C_r} + {\,^n}{C_1}{\,^m}{C_{r - 1}} + {\,^n}{C_2}^n{C_{r - 2}} + ......... + {\,^n}{C_r}^m{C_0}\)

**Solution: ** We interpret the left hand side as the number of ways of select *r* people out of a group of (*n* + *m*) people.

Let this group of (*n* + *m*) people consist of *n* boys and *m* girls. A group of *r* people can be made in the following ways:

\[{{\bf{Sl}}{\bf{.}}}\] |
\[{{\bf{Group \;contains}}}\] |
\[{{\bf{No\;}}{\bf{. of\; ways \;possible}}}\] |

\[{\rm{1}}\] \[{\rm{2}}\] \[{\rm{3}}\] \[{\rm{.}}\] \[{\rm{.}}\] \[{\rm{.}}\] \[r{\rm{.}}\] \[(r + 1)\] |
\[{\text {0 boys, }}r{\text { girls}}\] \[{\text {1 boy, (}}r - 1{\text {) girls}}\] \[{\text {2 boys, (}}r - 2{\text {) girls}}\] \[\] \[\] \[\] \[{\text {(}}r - 1{\text {) boys, 1 girl}}\] \[r{\text { boys, 0 girl}}\] | \[^n{C_0} \times {\,^m}{C_r}\] \[^n{C_1} \times {\,^m}{C_{r - 1}}\] \[^n{C_2} \times {\,^m}{C_{r - 2}}\] \[\] \[\] \[\] \[^n{C_{r - 1}} \times {\,^m}{C_1}\] \[^n{C_r} \times {\,^m}{C_0}\] |

This table is self-explanatory. The ( *r* + 1) types of groups that have been listed are mutually exclusive. Thus, the total number of *r*-groups is

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