Counting Principles
Lesson · Beginner
Combinatorics
Addition Principle
If a choice can be made in several mutually exclusive ways, the numbers of possibilities are added.
If one option can occur in m ways and another option can occur in n ways, and the two options cannot occur at the same time, then the total number of possibilities is
More generally,
Use the Addition Principle when the problem involves choosing one case OR another case.
Multiplication Principle
If a process consists of several successive choices, multiply the number of possibilities at each step.
If the first step can be completed in m ways and, for each of these, the second step can be completed in n ways, then the entire process can be completed in
ways.
More generally, if successive steps have
choices, then the total number of outcomes is
Use the Multiplication Principle when the problem involves completing one step AND another step.
Complement Principle
Sometimes it is easier to count all possible outcomes and subtract the outcomes that we do not want.
Equivalently, if A is a set of outcomes,
where U is the set of all possible outcomes.
The Complement Principle is especially useful for conditions such as:
• at least one
• not all
• none
• at least one occurrence of a particular type
A student may choose either one of 7 algebra books or one of 5 geometry books.
How many choices are possible?
The student chooses an algebra book or a geometry book.
The two cases are mutually exclusive, so by the Addition Principle,
A restaurant offers 4 main dishes, 3 side dishes, and 5 drinks.
How many meals consisting of one main dish, one side dish, and one drink are possible?
There are
choices for the main dish,
choices for the side dish, and
choices for the drink.
By the Multiplication Principle,
How many three-digit positive integers have no repeated digits?
The hundreds digit has
choices.
After choosing it, the tens digit has
choices, since 0 is allowed but the first digit cannot be repeated.
The units digit then has
choices.
Therefore,
How many odd two-digit numbers with distinct digits are there?
Case 1: The tens digit is odd
There are 5 choices for the tens digit:
After choosing the tens digit, the units digit must be odd and distinct from it, so there are 4 choices.
Case 2: The tens digit is even
There are 4 choices for the tens digit:
The units digit can be any of the 5 odd digits.
Therefore,
First, fill the units digit because it is the most limiting position.
Priority: Handle the Most Limiting Case First
The units digit must be odd, so it has 5 choices.
After choosing the units digit, the tens digit can be any nonzero digit except the chosen units digit, giving 8 choices.
There are
odd two-digit numbers in total.
The unfavorable numbers with repeated digits are
so there are 5 unfavorable numbers.
How many three-digit positive integers contain at least one digit 7?
It is easier to count the complement.
There are 900 three-digit positive integers in total.
To count the numbers containing no digit 7, the hundreds digit has 8 choices, while the tens and units digits each have 9 choices.
Therefore,
How many integers from 1000 through 9999 are divisible by 5 and have no repeated digits?
A number divisible by 5 must end in either 0 or 5.
Case 1: The last digit is 0
Priority: Handle the Most Limiting Case First
Fix the last digit as 0. The thousands digit then has 9 choices, the hundreds digit has 8 choices, and the tens digit has 7 choices.
Case 2: The last digit is 5
Fix the last digit as 5. The thousands digit has 8 choices, since it cannot be 0 or 5.
After choosing the thousands digit, the hundreds digit has 8 choices and the tens digit has 7 choices.
Therefore,
Suppose 8 people are on a train, and each person can get off at any of 3 stations.
Each of the 8 people has 3 choices.
Therefore, the number of possibilities is
not
When counting n-digit positive integers, the first digit cannot be 0.
Thus, a four-digit number does not have 10 choices for its first digit.
When making several choices, some choices may have more restrictions than others.
Count the most restricted choice first. After making that choice, count the remaining possibilities.
For example, suppose we want to form a three-digit even number using distinct digits from
The units digit is the most restricted because the number must be even. It has only
choices:
After choosing the units digit, the hundreds digit has
choices, and the tens digit has
choices.
Therefore,
Why is this useful?
Mathematically, you do not always have to choose the most restrictive part first. But doing so usually makes the counting much simpler and helps prevent mistakes.