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

Solution: 1

We can easily prove this relation using the expression we obtained for  : 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 . For this example, let us discuss such a logical justification in a good amount of detail. Suppose you have a group of  letters, say . Out of this group, you want to count the number of subsets containing  letters. Consider a particular selection of  letters, say . This selection can equivalently be obtained if we say that we exclude the group from our original group of  letters. This means that each selected group of  letters corresponds to an excluded group of  letters. The number of (selected) -letter groups will therefore equal the number of (excluded) - letter groups, or in other words, to count the number of  letter groups, we can equivalently count the number of -letter groups. Thus, Generalising this logic, we obtain

Example: 2

Prove that

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  people out of which we want to select a subset of  people; more precisely, we want to count the number of such -subsets. Fix a particular person in this group of  people, say person . Now, all the -groups that we form will either contain  or not contain . These are the only two options possible. To count the number of groups that contain , we proceed as follows: we already have ; we need  more people from amongst people still available for selection. Thus, such groups will  be in number. For the number of groups that do not contain  we need to select  people from amongst  options available. Therefore, such groups are in number. The total number of -groups are hence  in number, which is the same as . With this example, you should begin to realise the beauty of the logic and skill required in this subject.

Example: 3

Prove that

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  people, taken  at a time. We again fix a particular person, say person . All the possible -arrangements will either contain  or not contain . These are the only two (mutually exclusive) cases possible. If we do not keep  in our permutation, we have  people to select from a potential group of  people. The number of arrangements not containing  will therefore be  To count the number of permutations containing , we first seat  in one of the  seats available. This can be done in  ways. The remaining seats can be filled by  people in  ways. Thus, the number of arrangements containing  is . These arguments prove that

Example: 4

(a) Prove that  (b) Prove that

Solution: 4-(a)

Let us consider this assertion in a particular example, say with  and . This will make things easier to understand. Our purpose is to select  people out of  people, say the set . To select a group of , we can first select a single person : this can be done in  ways. The rest of the 3 people can now be selected in  ways. The total number of groups possible would thus be . But some careful thought will show that we have ‘overcounted’, doing the calculation this way. Suppose that in our first step, we select . While selecting the remaining persons, we then select  thus forming the group . But this same group would have been formed had we selected  in our first step and  in the second step, or  in the first step and  in the second step, or  in the first step and  in the second step. We have thus counted the group  times in the figure The actual number of groups will hence be  We now generalise this: to select  people out of a group of , we first select one person; this can be done in  ways. The remaining  persons can be selected in  ways. The total number of -groups thus becomes . However, as described earlier, in this figure each group has been counted  times. The actual number of -groups is therefore

Solution: 4-(b)

The logic for this part is similar to that of part - To select  people out of , we first select  people out of . This can be done in  ways. We now have  persons remaining for selection out of which we have to choose  more person. This can therefore be done in  ways. The total number of -groups thus becomes  However, each -group has again been counted  times in this figure (convince yourself about this by thinking of a particular example). The actual number of -group is thus