10.4. Combined Use of Sum and Product Rule

So now we have seen 2 basic counting rules but it turns out that we encounter scenarios where we have to combine both these 2 rules that means we can encounter problems which will require us to apply both the sum rule as well as the product rule.

In discrete mathematics, counting problems can often require the application of more than one counting rule. While the sum rule helps us count the total number of ways to accomplish tasks where options are disjoint (i.e., they do not overlap), the product rule is used for situations where tasks can be broken down into independent subtasks. Many problems combine both approaches to arrive at a solution.

Consider organizing a party where you need to either invite friends or colleagues. The sum rule helps you count distinct options for choosing either group (friends or colleagues), while the product rule comes into play when deciding how many of each can attend from larger groups.

So suppose we are interested to find out the number of passwords of length either 6 or 7 or 8 characters. That means the password can be either of length 6 or of length 7 or of length 8. The restriction is that each character can belong to the set A to Z or the numeric 0 to 9. That means the characters could be your English alphabets or digits and we also want passwords to have at least 1 digit.

We want to count how many valid passwords can be created given specific criteria about their length and character set. The length can be 6, 7, or 8 characters, and at least one of these must be a digit. This scenario requires the use of both the sum and product rules to account for the three lengths separately.

Think of it like a menu where you have different sizes of drinks: small, medium, and large (6, 7, or 8 characters). You are also required to put at least one ice cube (at least one digit) in each drink. For each size, you count the combinations that fit the condition and then sum them up for the final total.

Now how do we find the cardinality of the set P_6, P_7, and P_8. So let's see the logic of counting or finding the cardinality of the set P_6: the set is the set of all valid passwords of length 6. That means it should have exactly 6 characters, which could be either English characters or digits, and it should have at least 1 digit.

To find the valid passwords of length 6, we consider all the possible strings of length 6 using our character set (36 options: 26 letters + 10 digits). However, we need to subtract the invalid strings that don't meet the criteria of having at least one digit. Using the product rule, we find the total possibilities and then subtract those cases that only use letters.

Imagine you're baking a cake and you can choose from fruits (letters) and chocolate chips (digits). You first calculate all the possible combinations, then you remove combinations that don’t have any chocolate chips, ensuring you have a sweet and legitimate cake.

So now what is the cardinality of the set of all strings of length 6? Well, it is 36^6, and this I get by applying the product rule. Why 36? Because I have 6 positions to fill. That means I can identify 6 sub tasks and each position has 36 options.

When calculating all strings of length 6, we can think of each character position as a decision point where we can choose from 36 characters. Therefore, for each character, we have these options, which gives us a total of 36^6 combinations for all positions combined.

Think of a safe with 6 dials, and on each dial, you can choose from 36 numbers or letters. The total possible combinations give you a robust count of how many patterns you can possibly create in your secure vault.

So again here I am applying the product rule. And now if I subtract 26^6 from 36^6 that will give me the cardinality of P_6. The same logic you can apply to find out P_7 and similar logic you can apply to find out P_8. And if you sum those 3 quantities that will give you the required answer.

After calculating the total possible strings and subtracting invalid ones (those with no digits), we repeat the same logic for lengths 7 and 8. The combined total of valid passwords across these lengths gives the desired count. Thus, we aggregate these values using the sum rule.

Consider each length of password as a different set of candy jars. You count the valid candies in each jar (the valid passwords of different lengths), then combine the totals to know how many sweets you have in all jars.

--