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.
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
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.
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
(a) Prove that
(b) Prove that
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
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