Tuesday, 5 August 2014

CHAPTER 4 - Application 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 formula will do no good! A good deal of thinking is required.
Lets start with proving certain combination assertions.
     Example: 1    

Prove that ^n{C_r}{ = ^n}{C_{n - r}}
Solution: 1

We can easily prove this relation using the expression we obtained for ^n{C_r} :
^n{C_r} = \dfrac{{n!}}{{r!(n - r)!}} = \dfrac{{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}
Generalising this logic, we obtain ^n{C_r}{ = ^n}{C_{n - r}}
     Example: 2   

Prove that ^n{C_r}{ = ^{n - 1}}{C_r}{ + ^{n - 1}}{C_{r - 1}}
Solution: 2

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 ^{n - 1}{C_{r - 1}} be 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: 3     

Prove that ^n{P_r}{ = ^{n - 1}}{P_r} + {r^{n - 1}}{P_{r - 1}}
Solution: 3

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: 4      

(a) Prove that ^n{C_r} = \dfrac{n}{r}\,\,{\,^{n - 1}}{C_{r - 1}}
(b) Prove that ^n{C_r} = \dfrac{{n - r + 1}}{r}\,{\,^n}{C_{r - 1}}
Solution: 4-(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 3persons, 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 \dfrac{{6 \times {\,^5}{C_3}}}{4}.
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} = \dfrac{{n \times {\,^{n - 1}}{C_{r - 1}}}}{r}
Solution: 4-(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 (convince yourself about this by thinking of a particular example). The actual number of r-group is thus
^n{C_r} = \dfrac{{(n - r + 1) \times {\,^n}{C_{r - 1}}}}{r}
Post a Comment