Fundamental Counting Principle
The fundamental counting principle is a rule used to count the total number of possible outcomes in a situation. It states that if there are \( n\) ways of doing something, and \( m\) ways of doing another thing after that, then there are \( n\times m\) ways to perform both of these actions. In other words, when choosing an option for \(n\) and an option for \(m\), there are \( n\times m\) different ways to do both actions.
Basic Examples
Lily is trying to decide what to wear. She has shirts in the following colors: red, purple, and blue, and she has pants in the following colors: black and white. How many different outfits can Lily choose from (assuming she selects one shirt and one pair of pants)?
We know from the definition of the rule of product that if there are \(n\) options for doing one thing (like choosing a shirt), and \(m\) options for doing another thing (like choosing a pair of pants), then there are \(n \times m\) total combinations we can choose from. In this case, there are \(3\) options for choosing a shirt, and there are \(2\) options for choosing pants. Thus, there are \(3 \times 2 = 6\) total options.
Here is a table where each row represents a possible outfit.
Shirt Pants Red Black Blue Black Purple Black Red White Blue White Purple White As expected, there are \(6\) possible combinations. \(_\square\)
In the example above, there were two things to choose: a shirt and a pair of pants. However, the rule of product can extend to however many things to choose from. For example, if there are \(n\) choices for a shirt, \(m\) choices for a pair of pants, \(x\) choices for a pair of shoes, and \(y\) choices for a hat, the rule of product states that there are \(n \times m \times x \times y\) total possible combinations.
There are \(8\) daily newspapers and \(5\) weekly magazines published in Chicago. If Colin wants to subscribe to exactly one daily newspaper and one weekly magazine, how many different choices does he have?
Colin has \(8\times5=40\) choices. \(_\square\)
Intermediate Examples
Calvin wants to go to Milwaukee. He can choose from \(3\) bus services or \(2\) train services to head from home to downtown Chicago. From there, he can choose from 2 bus services or 3 train services to head to Milwaukee. How many ways are there for him to get to Milwaukee?
Since Calvin can either take a bus or a train downtown , he has \( 3+2 =5\) ways to head downtown (Rule of sum). After which, he can either take a bus or a train to Milwaukee, and hence he has another \( 2+3=5\) ways to head to Milwaukee (Rule of sum). Thus in total, he has \( 5 \times 5 = 25\) ways to head from home to Milwaukee (Rule of product). \(_\square\)
Six friends Andy, Bandy, Candy, Dandy, Endy, and Fandy want to sit in a row at the cinema. If there are only six seats available, how many ways can we seat these friends?
For the first seat, we have a choice of any of the 6 friends. After seating the first person, for the second seat, we have a choice of any of the remaining 5 friends. After seating the second person, for the third seat, we have a choice of any of the remaining 4 friends. After seating the third person, for the fourth seat, we have a choice of any of the remaining 3 friends. After seating the fourth person, for the fifth seat, we have a choice of any of the remaining 2 friends. After seating the fifth person, for the sixth seat, we have a choice of only 1 of the remaining friends. Hence, by the rule of product, there are \( 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\) ways to seat these 6 people. More generally, this problem is known as a permutation. There are \( n! = n \times (n-1) \times (n-2) \times \cdots \times 1\) ways to seat \( n\) people in a row. \(_\square\)
My toy piano keyboard has 7 distinct white notes: letters A-G in English alphabet. I'm going to create a melody by playing three random notes. I am not allowed to repeat any notes and the melody cannot be ended with E, F or G. How many different melodies can I play?
Examples:
- C G A is permitted.
- A F A isn't permitted because of repetition.
- A B E is not permitted because of last note rule.
How many positive divisors does \( 2000 = 2^4 5^3\) have?
Any positive divisor of 2000 must have the form \( 2^a 5^b\), where \( a\) and \( b\) are integers satisfying \( 0 \leq a \leq 4, 0 \leq b \leq 3\). There are 5 possibilities for \( a\) and 4 possibilities for \( b\), hence there are \( 5 \times 4 = 20\) (rule of product) positive divisors of 2000 in all. \(_\square\)