Multiplication Principle

In the last article, we discussed why do we need the counting principles in data science. In this article, we discuss the multiplication principle. So, let’s get started.

Let’s understand the multiplication principle with the help of an example:

Say we visit a restaurant that offers south-Indian dishes, north-Indian dishes, some beverages, and a combo as well which includes one item from each category. We are interested in knowing if we can have a different combo every day of the month.

We are interested in counting the total number of such possible combinations and if the count is greater than 30, that means we can have a different combo on every day of the month.

Let’s answer this question by selecting the south-Indian dish first, and we know that there are 5 south-Indian dishes from which we can choose, so we could choose any of the 5 dishes here. Now irrespective of what we choose for the south-Indian dish, we have 3 options for north-Indian dishes that means we can choose a north-Indian dish in 3 ways, and similarly, we have 3 choices for Beverages.

We can choose any of the 5 dishes from south-Indian dishes and irrespective of the choice of south-Indian dish, we have 3 options for north-Indian dishes and again irrespective of what north-Indian dish we choose, we have 3 option of choosing a beverage. We can say that the choice of item from each category is independent of what is selected from another category or in other words, the choices from each category are independent.

So, in turn we have a total of ‘5 * 3 * 3’ possible combos in this case and this is an example of multiplication principle in practice.

Let’s take another example, say we have 8 boys and 12 girls in a classroom and we want to form a committee which contains exactly 1 boy and 1 girl and we are interested in knowing the total number of ways of doing this task.

So, here again, we can choose any one of the 8 boys meaning we have 8 different ways of selecting a boy in this case and now irrespective of the boy chosen as part of the committee, we can choose any of the 12 girls. So, the total number of ways of forming the committee is ‘8*12’ i.e 96.

Special Cases

Let’s understand how we can make a sequence of ‘k’ objects from a given ’n’ objects with repetition. Let’s understand this statement better with the help of an example.

Say there is a fitness enthusiast and he/she can do one of the following 10 exercises every day and he/she wants to select an exercise for every day and if interested, they can repeat the exercise meaning they can choose the same exercise again and again.

And this is actually an instance of:

So, we want to put items in a sequence and those items could be 1 of the 10 exercises, so we want to make a sequence of 7 items from a given set of 10 items.

Let’s approach this problem using the multiplication principle.

We have 7 independent decisions to make(one for each day). For the first decision, we have 10 choices(we can choose any 1 of the 10 exercises), and since the exercises can be repeated that means we again have 10 choices for the second decision(second day).

Similarly, for the remaining days of the week, we have 10 choices on every day and now we can use the multiplication principle on these independent decisions and the total number of ways of making a decision would be ‘10⁷’.

Let’s look at one more example:

We have 26 alphabets in the English language and we want to make a word of 5 letters and it does not matter if the word is a valid word or invalid word.

So, again we have to make 5 decisions and for each decision, we have 26 choices, so using the same approach, we can say that the total number of possible words is ‘26⁵’.

Sequences without Repetition

Now we are interested in making a sequence of ‘k’ elements from a given ’n’ elements when the repetition of the elements is not allowed:

Let’s solve this task taking the gym example where a person can try out from 10 different exercises and the person can perform only one of the 10 exercises on a given day and they can not repeat the same exercise more than once in a week.

When stating the multiplication, we specified that the decision at each step should be independent of each other, but in this case, the decision at each step are not independent because let’s say we selected ‘Walking’ exercise on Day 1, then the possible options for Day 2 depends on Day 1 choice(as ‘Walking’ can not in the list of possible options) and decisions don’t seem to be independent of each other

Turns out we can still apply the multiplication principle, we don’t really care if the decisions being independent, what we really care about is the number of choices at each step be independent.

Let’s see what this means: We have 10 choices for Day 1(and say we selected ‘Walking’, so ‘walking’ is out from the list and we are left with the remaining 9 options to choose from for Day 2; so the number of choices that we have on the second day if we select ‘Walking’ on the first day is 9)

Let’s say we have selected ‘Running’ on the first day instead of ‘Walking’ so ‘running’ is out from the list but any of the remaining 9 choices is still available to us

So, turns out that whether we choose ‘Walking’ or ‘Running’ on the first day, we still have the 9 choices on the second day(these choices are the not the same but the number of the choices is the same), similarly, we can choose any of the 10 exercises(and not just from ‘walking’ or ‘running’) on the first day and we’ll have a total of 9 options to choose from for the second day.

Similarly, we can say that irrespective of what we choose on the first 2 days(say Zumba and running), we are always left with a total of 8 choices on 3rd day and that is what we care about, the number of choices at each step when we are making a sequence of choices or sequence of decisions should be independent of what we have chosen on the previous day and as long as that happens, we can apply the multiplication principle.

So, in this scenario, what will happen is, we have 10 choices on Day 1, we have a total of 9 choices(irrespective of what we choose on Day 1) on Day 2, a total of 8 choices of Day 3 and so on for the remaining days of the week.

So, the answer of the main question about the number of possible sequences(total possible sequence of the exercise regime) we can have is: ‘10 * 9 * 8 * 7 * 6 * 5 * 4'

Let’s take another example:

There are 9 digits(0 is not allowed) from which we can choose from and we want to create a sequence of 3 digits and we are not allowed to repeat digits, that means we choose from any of the 9 digits for the first slot of the 3 digit numbers, any of the 8 digits(1 digit is already selected for the first slot and we cannot repeat the digit) for the second slot and any of the remaining 7 digits for the third slot.

And the total number of such possible sequences would be: ‘9 * 8 * 7’

Let’s add a twist on top of the current task:

So, again we are supposed to create a sequence of 3 elements but because the number has to be odd, there is a restriction on what the last digit/element/slot would be(we now have only 5 choices for the last slot).

For the first slot, we still have the 9 choices, and similarly, for the second slot, we still have the 8 choices available.

Now for the last slot, we won’t always have the 5 choices, for example, say we have chosen the number 1 in the first slot and any even number in the second slot, then in third slot we have 4 choices as the number in the third slot has to be an odd number and we can not repeat the digits(so we are left with the following choices: 3, 5, 7, 9)

And if we have chosen even numbers for the first two slots, then we have a total of 5 choices for the last slot and on a similar basis, if we have chosen the first two numbers as odd numbers, then we have a total of 3 choices for the last slot.

So, depending on the decisions we are taking earlier, the number of choices that are available is changing and this is not a scenario where we can use the multiplication principle.

To use the multiplication principle in such scenarios, we can make our decisions in way that the number of choices in each step are independent.

Since the last slot has some restriction(odd number must come), we can start by selecting the last digit and we know that for the last digit we have a total of 5 choices, then irrespective of what we choose for the last digit, we have a total of 8 choices for the second slot and after selecting the digits for the second and third slot, we are left with a total of 7 choices for the first slot

Now we have re-arranged our decisions in a way that the number of choices at each step is independent of choices we made at previous step and we can now leverage the multiplication principle and the total such numbers would be ‘7 * 8 * 5’

Let’s take one more example:

So, here again, to solve this task, we can first select the alphabet for the last slot and then the values for the remaining slots and this way the number of choices at each step would be independent of choices at other steps and we can leverage the multiplication principle to get the required value.

Let’s take one more example where it is not clear that we are trying to create a sequence

In the example discusses so far, it was obvious that we were forming a sequence where order matters for example in a 3 digit number if we put 1 in the first slot vs when we put 1 in the last slot, we get an entirely different sequence(given that digits can not be repeated) whereas, in the current task, we do not have any notion of 1st person, 2nd person in the sequence.

A sequence is something in which the order of the data elements matters. And to convince you that the order matters in the current case, let’s take an example.

The above-mentioned data tells us that the order matters in this case as well. If we look at the first example, there we have Jack as the President and Mary as Secretary and if we compare it with the last row where we have replaced the positions/posts of these two, then the committee in itself is called as different as the roles, responsibility of each person changed.

So, this is similar to a sequence and in fact, we can think of President post as the first slot to fill and similarly the other posts as the numbered slot in the sequence.

And once the problem is converted to the standard one, we can leverage the multiplication principle to know the total number of ways of forming such a committee.

Let’s discuss one other case where we have to form a sequence of ’n’ elements from given ’n’ objects:

Here is an example:

Now in the first slot, we could any of the 9 pots so we have 9 choices, for the second slot, we have 8 choices(obviously the repetition is not allowed as the same pot could not be in more than one slot simultaneously), similarly we have 7 choices for the third slot and all the way up to the last slot for which we have 1 choice.

So, we can state this in 3 different ways:

This can also be looked as an arrangement problem(so the number of ways in which ’n’ objects can be arranged among themselves is ‘n!’)

And this arrangement is called as permutations.

Let’s see an example as to how the concepts of counting all the possible events tie back to the probability theory:

Say there are 3 persons(A, B, C) who are to be arranged in a sequence(could be some sort of ranking or the order in which they are served food) and we want to find the probability of particular order say ‘CAB’. We know that this sequence ‘CAB’ is one among many possible sequences, as there are 3 elements, a total of 3! sequences, arrangements are possible

Since all the 6 sequences are equally likely, the probability of any such sequence would be 1 divided by the total number of possible outcomes.

So, counting concepts helps us in knowing the total possible outcomes and that then helps in computing the probability.

Now that we are introduced to the factorial notation, let’s see the previously discussed formulas and convert them to a factorial notation as well:

We can transform it in the following way:

Let’s see one example where we have the permutations along with some restrictions on some elements/slots.

Let’s say we have the same pots example but this time we have 5 red pots and 4 yellow pots and we want to know the number of ways in which they can be arranged such that no two red pots are adjacent to each other.

Let’ say we have selected the first pot to be yellow, and then the next one as a red pot, now the moment we choose a red pot, we can be sure that the next one must be yellow one.

And we select a yellow pot for the 4th slot, then a red pot for the 5th slot which implies a yellow pot for the 6th slot and at this point we have used all the 4 yellow pots which means we must the red pots in the remaining slots which will violate the constraints.

If we don’t want two consecutive red pots, then we need to have the red pots in between the yellow pots and this is the only way possible where we have alternate red and yellow pots and the constraints are also satisfied.

But the 5 red pots could be in any order, for example if we number the red pots as 1, 2, 3, 4, 5 then it’s not sort of mandatory to put the red pot number1 at slot 1, it could be in any of the 5 positions where we have a red pot. Similarly, the 4 yellow pots could be in any order.

Now the problem can be broken down into two parts:

Given the five slots for the red pots, what are the number of ways to arrange them? And we know that we have a total of 5 red pots and we want to arrange them in 5 slots, so there are 5! possible ways of doing that.

Now having done this, we can independently arrange the yellow pots into remaining 4 slots and we have another similar case where we have 4 elements(4 yellow pots) and we want to arrange them in 4 slots, so we know that there are a total of 4! ways of doing this.

And now applying multiplication principle on top of it(as we have independent decisions for the internal ordering of red and yellow pots among themselves), we know that the total number of ways of doing this arrangement would be ‘5! * 4!’.

In this article, we discussed the multiplication principle, how to form a sequence of ‘k’ elements from a given set of ’n’ elements when the repetition is allowed, when the repetition is not allowed.

References: PadhAI