Section 1.3 – Two Better Methods (Part 2)
Examples
Example 1 – Counting Children
If a couple has three children, how many combinations of boys and girls do they have?
The way that I like to do these problems is by first drawing a line for each of the possible choices.
| first child | second child | third child |
Next, I'll put the number of options for each category on the line. In our child situation, each of the three "events" has the same two options: the child is either a boy or a girl.
| 2 | 2 | 2 | ||
| first child | second child | third child |
The Multiplication Rule tells us that the total number of possible families is equal to the product of all the individual "events" or 2 · 2 · 2 = 8.
Example 2 – Calculating Addresses
Whenever a machine connects to a network, e.g. your computer connecting to the Internet, it has to be given its own unique, numeric address called an IP address. In the current version of the address system, called IP v4, every IP address is made up of four numbers, each number ranging from 0 to 255, e.g. 100.103.94.1 or 122.5.2.1. How many different IP v4 addresses are there?
We can calculate this using my "line method" from the previous example. An IP address is made up of four numbers so we have four choices to make:
| first number | second number | third number | fourth number |
We can put 256 different numbers from 0 to 255 in each of the four blocks.
| 256 | 256 | 256 | 256 | |||
| first number | second number | third number | fourth number |
If we multiply the number of options for each choice together, we get 256 · 256 · 256 · 256 = 4, 294, 967, 296 different IP addresses.
Example 3 – Custom License Plates
A state allows car owners to choose their own license plate number. The number has to start with five letters and end with a single number. How many possible license plates are there?
Our custom license plates have a total of six characters (five letters plus a final number) so we're going to need to fill six blanks.
| first letter | second letter | third letter | fourth letter | fifth letter | last digit |
Each of the letter spots can have any of the 26 English letters; the numeric spot can have any of the 10 digits from 0 to 9.
| 26 | 26 | 26 | 26 | 26 | 10 | |||||
| first letter | second letter | third letter | fourth letter | fifth letter | last digit |
Now we can use the Multiplication Rule to get the total number of license plate numbers:
26 · 26 · 26 · 26 · 26 · 10 = 118, 813, 760 numbers
Example 4 – Social Security Numbers
A US Social Security Number is a ten digit number divided into three parts: a three digit number, a two digit number and a four digit number, e.g. 987-65-4320. There are a few limitations on how Social Security numbers are generated?
- Numbers with all 0's in any of the three groups, e.g. 000-12-1234 or 123-00-1234, aren't allowed.
- Numbers with 666 or any number between 900 and 999 in the first group aren't allowed.
- Numbers from 987-65-4320 to 987-65-4329 are reserved for companies to use in advertising
Based on these rules, how many possible US Social Security Numbers are there.
Don't be put off by the list of rules. We can start this off using the line method that we've used for all of our other problems.
| group one | group two | group three |
The first group is a three digit number which means it has 1000 possibilities (including 000). Rule (1) tells us that we have to exclude 000 which takes the number of choices down to 999. Rule (2) excludes 666 which takes the number of choices to 998 and it excludes the 100 numbers between 900 and 999 which makes the total number of possible choices 898.
| 898 | ||||
| group one | group two | group three |
The only limitation on the second group is that it can't be 00 which means that it can be any number between 01 and 99 which gives us 99 possible choices. Similarly, the third number can be anything from 0001 to 9999 which gives it 9999 possible choices.
| 898 | 99 | 9999 | ||
| group one | group two | group three |
Applying the multiplication rule gives us (so far) 898 · 99 · 9999 = 888, 931, 098 possible numbers.
At this point, we still haven't considered rule (3). It excludes the ten numbers between 987-65-4320 and 987-65-4329. The easiest way to apply that is just to subtract out those 10 numbers from our total which gives us a final answer of 888931098 - 10 = 888, 931, 088 possible Social Security Numbers.
It may not have been obvious but, on the last part of Example 4, where we applied rule (3), we used the Addition Rule. To see how, think of the Social Security numbers as being divided into two groups: advertising numbers and not advertising numbers. Because the two groups have no numbers in common, the Addition Rule tells us that the total number of Social Security numbers is
(non-advertising numbers) + (advertising numbers) = (total number of numbers)
We had already calculated that, including both types of numbers, there were 888, 931, 098 possible values and rule (3) told us that there were 10 non-advertising numbers. If we substitute those values into our Addition Rule equation, it becomes
(non-advertising numbers) + 10 = 888931098
Solving that equation for (non-advertising numbers) gives us
(non-advertising numbers) = 888931098 - 10 = 888931088
Notice how that equation is the same thing as I got from just saying, "Subtract out the numbers that we don't want."
Example 5 – Subsets of a Set
Suppose you have a set with 5 elements in it, e.g. A = {a, b, c, d, e}. How many subsets does the set have?
To answer this, we're going to have to think about the situation a little differently than in previous problems. Like the previous problems, it helps to think in terms of making choices but the key here is going to be in deciding what those choices are.
When I'm choosing a subset, I have to look at each of the five elements and answer the question, "Is this element in the subset or isn't it?" To do that, I'll start with five spaces, one for each element.
| a | b | c | d | e |
Now, for each element, I have two possible choices: Either it's in the subset or it isn't. If I put a 2 in each space, it becomes
| 2 | 2 | 2 | 2 | 2 | ||||
| a | b | c | d | e |
Now, the Multiplication Rule tells us that the total number of subsets must be 2 · 2 · 2 · 2 · 2 = 32.