This is the first post in a series of posts on combinatorial analysis, which is a study on counting, e.g. finding effective methods for counting the number of ways to arrange objects and for counting the number of ways events can occur. Many problems in mathematics, e.g. in probability theory, require the counting of the number of ways an event can occur. Permutations and combinations are basic ideas in counting. Both ideas are based on an idea called the multiplication principle. This post focuses on the multiplication principle. The next post is on permutations and combinations.
The Multiplication Principle
Let’s start with some examples.
Jack is buying ice cream – two scoops of ice cream of the same flavor on either a cone or a cup. The available flavors are vanilla, strawberry, chocolate, butter pecan, mint chocolate chips and rocky road. How many possible arrangements of ice cream are available for Jack?
The answer is 2 x 6 = 12 arrangements. The following lists out all the possibilities.
Cone-Mint Chocolate Chips
Cup-Mint Chocolate Chips
With the cone option, there are 6 choices for flavors. With the cup option, there are also 6 choices for flavors. So the total number of possible choices would be 6 + 6 = 2 x 6 = 12.
Of course, if Jack only limits his purchase to his most favorite ice cream (say mint chocolate chips), then there would be only two choices, cone or cup. But if he is indifferent to the flavors, there would be 12 arrangements as listed above.
The listing in Example 1 suggests a general principle.
The Multiplication Principle
If one event can occur in ways and another event can occur independent of the first event in ways, then the two events successively can occur in ways.
Of course, the principle just described has an obvious generalization. Instead of just considering two events, we can count how many ways a series of events can occur. As long as the events are independent, the total number of ways all events occurring in a row is obtained by simply multiplying the numbers of possible occurrences of the individual events.
The following is a menu for a banquet. Assuming that each guest can only pick one item for each course, how many different possible dinner decisions are possible?
This problem is mentioned in previous post. Using the multiplication principle, the answer is 4 x 2 x 3 x 2 = 48 choices.
Remark. For the multiplication principle to apply, the events must be independent. This means that the number of occurrences of the one event is not restricted by the previous event. If a guest in the banquet is indifferent to all items in the menu (if taken individually) but does not like to mix certain items (e.g. he does not like to have French onion soup to go with goat cheese salad), then he or she might not have 48 choices. The following example illustrates that for a certain kind of dependency between events, the multiplication principle can still apply.
A PIN code for a bank ATM machine is a 4-digit number. Determine the following:
- How many PIN codes are possible?
- How many PIN codes are possible if no repetition of digits is allowed?
- How many PIN codes are possible if the first two digits form a number less than or equal to 33 and the last two digits form a number that is at least 3 times the first two digits?
There are many possible codes. If no digits can repeat, then there are
different codes. For the no repetition case, there are 10 choices for the first digit. Once the first digit is fixed, there are only 9 choices for the second digit. Once the first two digits are fixed, there are 8 choices for the third digit. Then the fourth digit has 7 choices once the first three digits are fixed. Though the number of choices for each digit is limited by the previous digit, it is the same regardless the value of the previous digits. Thus the principle still applies.
The third problem illustrates a dependency that makes the multiplication principle not applicable. For example, if the first two digits are 01, the last two digits would be 03, 04, 05, 06, …, 99 for a total of 97 possibilities. If the first two digits are 02, then there are 94 possibilities for the last two digits (06, 07, …, 99). As the number for the first two digits increases to 33, the number of choices for the last two digits would decrease. The largest possibility for the first two digits would be 33 and there is only one choice for the last two digits (99). Thus the multiplication principle would not work here. The answer is not obtained by multiplication. It is obtained by adding up all the possibilities as the first two digits go from 01 to 33. We perform the calculation in Excel and the answer is 1617. Of course, the third problem is not a realistic way to obtain pass codes. It is just an illustration of a case where the multiplication principle does not apply.
We look at more examples.
In how many ways can 9 students (4 males and 5 females) stand in a row for a group photo
- if there is no restriction on the standing positions?
- if the females must stand together and the males must stand together?
- if the females must stand together?
If the students can stand anywhere they want, there are 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880 ways of arranging these 9 students in a row. For the first spot, there are 9 students to choose from and there are 8 students to choose from for the second spot and so on. A convenient notation for the answer is 9! (read 9 factorial). It simply means that it is the product of all the integers from 9 down to 1.
By the same reasoning, there are 5! = 120 ways of arranging 5 persons in a row. There are 4! = 24 ways of arranging 4 people standing in a row. If the females stand on the left and the males stand on the right, then there are 120 x 24 = 2,880 arrangements in a row for the 9 students. The answer is 2 x 120 x 24 = 5,760 since there is also the case of males standing on the left and females on the right.
The third problem requires that only the females must stand together. The use of the multiplication principle is subtle. If the females must stand together, think of all the females as one unit. There are 5 units – 4 males and one combined unit of females. There are 5! ways of arranging the 5 units. Within the combined unit of females, there are 5! ways of arranging the 5 females. Thus the answer is 5! x 5! = 120 x 120 = 14,400.
The next example shows that the multiplication principle is invaluable in calculating large numbers.
In general, longer passwords are stronger passwords. The principle of counting discussed here can be used to quantify the strength. Consider an 8-character password consisting of letters from English. To start, let’s say the letters in the password are all upper case or all lower case, i.e. the password is case insensitive. Then the number of possible passwords would be
That’s over 208.8 billions possibilities. What if the password is case sensitive? If each character in the password can be in upper case or in lower case, then each character has 52 choices (26 upper case letters and 26 lower case letters). Then the number of possible passwords would be
That’s over 53 trillions possible passwords! Of course, the length of the password by itself may not mean strength. For example, people may use familiar words to form the password. One of the famous examples would have to be “Password”. In addition to being long enough, the characters in the passwords should be randomly chosen if possible.
To make the 8-character password even stronger, we can include numbers in addition to letters. Then the total number of possibilities is
which is over 218 trillions.
The factorial concept introduced in Example 4 is a useful tool in counting. If is a positive integer, the number is defined to be the product of all the positive integers less than or equal to .
For convenience, we define 0! = 1. In Example 4, 9! is the number of ways of ordering 9 people in a row. In general, is the number of ordered arrangements of distinct objects. There will be more discussion about this interpretation of factorial in the next post.
Example 3 and Example 5 concern with finding the number of possible ordered arrangements of objects for use in setting passwords or pass codes. Here’s is an example involving license plates. When a motor vehicle authority (or some relevant governmental body) designs license plates for automobiles, one important goal is to have a sufficiently large number of possibilities to accommodate all the vehicles in that jurisdiction. Suppose that the license plate has 7 characters. The first character is a number and the next three characters are letters. The last three characters are numbers.
- What is the total number of possibilities in this license plate design?
- If the motor vehicle authority is beginning to issue license plates with the first digit being 3, how many license plates will the authority have to issue before switching to using 4 as the first digit?
- Twelve tasks are to be assigned to twelve workers. What is the total different number of job assignments?
- In how many ways can four students be randomly selected to receive four cash prizes ($10, $20, $30, $40)?
- In how many ways can 4 boys and 4 girls stand together in a row for a group photo?
- In how many ways can 4 boys and 4 girls stand together in a row for a group photo if people of the same gender must be together?
- In how many ways can 4 boys and 4 girls stand together in a row for a group photo if only the girls must be together?
- In how many ways can 4 boys and 4 girls stand together in a row for a group photo if no people of the same gender can stand together?