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.

Image for post
Image for post
Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

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.

Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post

And this is actually an instance of:

Image for post
Image for post

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⁷’.

Image for post
Image for post
Image for post
Image for post

Let’s look at one more example:

Image for post
Image for post

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.

Image for post
Image for post

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⁵’.

Image for post
Image for post

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:

Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post

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

Image for post
Image for post

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.

Image for post
Image for post

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)

Image for post
Image for post

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

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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'

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

Let’s take another example:

Image for post
Image for post

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.

Image for post
Image for post

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

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

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

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

Image for post
Image for post
Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post

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

Image for post
Image for post

Here is an example:

Image for post
Image for post
Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post

So, we can state this in 3 different ways:

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

We can transform it in the following way:

Image for post
Image for post
Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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:

Image for post
Image for post

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.

Image for post
Image for post

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

Written by

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store