Skip main navigation

New offer! Get 30% off one whole year of Unlimited learning. Subscribe for just £249.99 £174.99. New subscribers only T&Cs apply

Find out more

The Division Principle

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.

The Multiplcation Principle is suitable to count sets that are obtained through an ordered sequence of steps. When the order does not count, it cannot be directly applied since from the final outcome it may be impossible to derive the outcomes of the various steps. The Division Principle is there to help us, let’s listen to Carlo explaining how.

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now