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