Subtraction Principle

In the last article, we discussed the multiplication principle and we saw different types of problems and in particular, if there is some restriction, constraints for some slots, then in such problems the idea is to always address the restriction first and we order the decisions in a way that the number of choices at each step should be independent of choices made at previous steps.

In this article, let’s discuss the case where we are not able to transform the problem in a way that the number of choices at each step is independent irrespective of all the re-ordering of the decisions.

Let’s take an example:

Let’s first deal with the restriction part, say we place a vowel in the last slot, then we have 5 choices for the last slot and we then have 25 choices for the second slot and then 24 choices for the first slot.

If we solve it this way, that means the last character is always going to be a vowel.

This will give us sequences which will have at least one vowel but also the last character is a vowel, it will not give us sequences of the following form where the original constraint is satisfied(at least one vowel in the word) but the last character is not a vowel:

This word satisfies the criteria(one vowel is present) but by using the approach we discussed, we can not have this word in the sequence, as we are not allowing ‘t’ to be the last character(we are choosing the last character only from vowels).

So, the approach that we discussed above will not allow for sequences that have at least a vowel but the last character is not a vowel. What we are doing is actually more restrictive than what is being asked and as a result, we’ll end up with smaller sequences than what would have been created.

We can’t deal with this by finalizing the second character first, if we fix the second slot first, then we are going to get sequences where at least one vowel is present and the second character is a vowel. And we’ll not get the sequences of the following form:

This sequence satisfies the given condition but if we do the decision making in this way by selecting the character for the second slot first, we again miss some of the words.

So, we are not being able to re-arrange our decisions in a way that we exactly satisfy the original constraints specified in the problem, what we are able to do is to put in some additional constraints as well.

The way to solve such problems with at least ‘k’ restrictions is to use the subtraction principle which is as follows:

Let’s say set A is the all possible set of three-letter sequences that we can create:

Let’s say the area denoted by B in the above image corresponds to all the sequences with at least one vowel and the area denoted by C represents the sequences that do not have one vowel.

Now, we know that counting the number of elements in set B is hard for us by using the multiplication principle.

Let’s say somehow we can compute the total number of elements in set A as well as in set C, then we can say that the number of elements in set B is given as the difference of elements in A and the elements in C.

In our case, set A would represent the set of all 3 letter words with no letter repeated.

Set B represents all three-letter words with no letter repeated and with at least one vowel.

Set C is the set of all the sequences with no letter repeated and no vowels.

Let’s see how to count the number of elements in set A: since we have to fill in 3 slots such from a total of 26 alphabets such that no letter is repeated, it can be easily computed using the multiplication principle

Now the set C is for 3 letter sequences which do not contain any vowel and the repetition is also not allowed that means we have to fill in 3 slots using 21 alphabets and therefore the count of elements in C is given as:

And using the counts of set A and set C, we can count the number of elements in set B as:

Let’s take one more example:

Whenever we see the term at least in the constraints, we can be sure that it will tricky to solve just using the multiplication principle and we should rely more on the subtraction principle.

So, the sequences of the following form are allowed as per the requirement of this problem:

Solving this using the subtraction principle, set A, in this case, would be the set of all 5 letter sequences(there is no restriction on the repetition of the alphabets), set B contains all the 5 letter words containing at least two consecutive letters which are the same and set C would be the set of all 5 letter sequences containing no two consecutive letters which are the same(so set B and set C are compliments of each other and the union of set B and set C gives us set A).

For set A, we can fill in each of the 5 slots using the 26 choices so the total number of elements in set A would be 26⁵

Let’s count the number of elements in set C:

There are 26 choices for the first letter, say we have chosen the alphabet as ‘f’, then since C is a set of all the sequences where no two consecutive letters are the same, that means we can not choose ‘f’ in the second slot and we can choose from any of the remaining 25 alphabets, say we choose ‘t’ for the second slot, now again the possible choices for the third slot are 25(as we can not choose ‘t’ and the repetition of letters is allowed) and similarly we have 25 choices for the 4th slot and for the 5th slot as well.

So, we have a situation where we have the number of choices at each step and the number of choices at each step is independent of the number of choices at the previous step

So, the total number of elements in set C would be the following as per the multiplication principle:

And now we can count of the elements in the set B as the subtraction of elements in the set A and set C:

So, leveraging the subtraction principle on top of the multiplication principle, we are able to solve this task.

References: PadhAI