The Division Principle

As we saw, the multiplication principle applies when you want to count order instructions. Because we have to recover the partial outcomes uniquely from the final outcome, and this cannot be applied, for instance, as we saw in an example, when you want to obtain a set, for instance, of two people among three. Because you cannot recover from the final outcome. That is the set. Who was chosen the first step, and who was chosen the second step? There is another principle that helps us in such a situation, the division principle.

While it is very simple, it simply states that, if you need five grammes of coffee to fulfil one moka pot, then you need 250 grammes of coffee to fulfil 50 moka pots. Let us have a precise statement of the division principle. Well, assume you have two finite sets, X and Y. And assume that each elements of Y, which is a smaller set, corresponds to M elements of X to function from X to Y. So there are exactly M elements of X that are sent to each element of Y. So correspondingly to one element of Y, we have M elements of X.

So the number of elements of X is M times the number of elements of Y, which is often used in order to attain the number of elements of Y, which is, therefore, the number of elements of X divided by M. As an example, we want to count the number of committees. That is the subsets of three people chosen from a group of 27. Well, we know that the multiplication principle cannot be applied. Because if you form a set in three steps, which was the first, the second, and the third element of the group, we cannot recover the partial outcomes from the final outcome.

So we first put them in a sequence, and we consider the set X of the three sequences that we can form with the 27 persons with no repetitions. So we form distinct sequences, which was the first, the second, and the third element of the group. We can apply the multiplication principle, and we have 27 times 26 times 25 possible elements of X. Now, we consider the set of committees of three elements among 27, which is the sets of three elements among 27. Now, let us consider an element ABC of Y, a committee, ABC. How many ordered sequences can we build from ABC? Well, there is the sequence ABC, others. How many?

Well, factor of three permutations of ABC, CAB, BCA, and so on. So we have a six to one correspondence from the set X to the set Y, and therefore, we can apply the division principle. And we obtain that X at six times the number of elements of Y or Y, which is the sets that we want to count, has got the number of elements of X divided by six, so 27 times 26 times 25 divided by 6.