The Central Idea
Most elementary counting questions can be organized around two questions:
- Are we choosing one case or another?
- Are we completing one stage and then another?
If the possibilities come from separate alternatives, we usually add. If an outcome is built through successive choices, we usually multiply.
Counting without Listing Everything
Suppose a cafeteria offers \(4\) soups and \(7\) salads, and a customer wants exactly one of those items.
There are
\[ 4+7=11 \]possible choices.
Now suppose the customer chooses one soup and one salad.
Each of the \(4\) soups can be paired with each of the \(7\) salads, so there are
\[ 4\cdot7=28 \]possible meals.
The words or and and often provide useful clues, but the structure of the problem matters more than the wording.
The Sum Principle
The sum principle applies when a collection of outcomes is separated into nonoverlapping cases.
If one case can occur in \(m\) ways and a second, mutually exclusive case can occur in \(n\) ways, then the total number of outcomes is
\[ \boxed{m+n}. \]The cases must not count the same outcome twice.
Example: Choosing One Type of Item
A shelf contains \(6\) mystery novels and \(9\) science-fiction novels. Suppose you choose exactly one book.
You may choose a mystery novel or a science-fiction novel.
\[ 6+9=15. \]Therefore,
\[ \boxed{15} \]books are available as possible choices.
Why the Cases Must Be Disjoint
The simple sum principle assumes that the cases do not overlap.
If an outcome belongs to both cases, adding the case counts includes that outcome twice.
For two finite sets \(A\) and \(B\), the correct general relationship is
\[ |A\cup B|=|A|+|B|-|A\cap B|. \]When \(A\cap B=\varnothing\), this becomes the ordinary sum principle:
\[ |A\cup B|=|A|+|B|. \]Systematic treatment of overlapping cases belongs to inclusion–exclusion.
The Product Principle
The product principle applies when an outcome is created through a sequence of choices.
If a first stage can be completed in \(m\) ways and, for each first-stage choice, a second stage can be completed in \(n\) ways, then the entire two-stage process can be completed in
\[ \boxed{mn} \]ways.
Example: Shirts and Pants
Suppose there are \(5\) shirts and \(3\) pairs of pants.
An outfit requires one shirt and one pair of pants.
Each shirt can be matched with all \(3\) pairs of pants:
\[ 5\cdot3=15. \]Therefore, there are
\[ \boxed{15} \]possible outfits.
Why Multiplication Works
Label the shirts
\[ S_1,S_2,S_3,S_4,S_5 \]and the pants
\[ P_1,P_2,P_3. \]For \(S_1\), there are \(3\) possible pants choices. The same is true for \(S_2\), \(S_3\), \(S_4\), and \(S_5\).
So the total is
\[ 3+3+3+3+3=5\cdot3=15. \]The product principle is repeated addition organized by stages.
More Than Two Stages
The product principle extends to any finite number of stages.
If stage \(1\) has \(n_1\) choices, stage \(2\) has \(n_2\) choices, and so on, with \(n_k\) choices at stage \(k\), then the number of complete outcomes is
\[ \boxed{n_1n_2\cdots n_k}. \]This is sometimes called the multiplication principle or fundamental counting principle.
Example: Building a Meal
A restaurant offers:
- \(4\) entrées;
- \(3\) side dishes;
- \(5\) beverages.
A complete meal contains one choice from each category.
\[ 4\cdot3\cdot5=60. \]Therefore, there are
\[ \boxed{60} \]possible complete meals.
Ordered Outcomes
In a sequential counting problem, the stages often have distinct roles.
Suppose a code contains one letter followed by one digit.
If \(26\) letters and \(10\) digits are allowed, then
\[ 26\cdot10=260 \]codes are possible.
A letter in the first position and a digit in the second position are different kinds of choices, so the positions are inherently ordered.
Repeated Choices May Be Allowed
Suppose a four-digit access code may use any digit from \(0\) through \(9\), and repetition is allowed.
Each position has \(10\) choices:
\[ 10\cdot10\cdot10\cdot10=10^4. \]Therefore,
\[ \boxed{10{,}000} \]codes are possible, including codes that begin with \(0\).
When Choices Change after Each Stage
The number of choices does not need to stay constant from stage to stage.
Suppose three different students are selected from a group of \(8\) to serve as president, vice president, and secretary.
There are \(8\) choices for president, then \(7\) remaining choices for vice president, then \(6\) remaining choices for secretary:
\[ 8\cdot7\cdot6=336. \]Therefore,
\[ \boxed{336} \]officer assignments are possible.
The Product Principle Does Not Require Equal Branches
A common beginner version of the product principle uses the same number of choices at each stage. That is not essential.
The key requirement is that we know how many continuations are available after each relevant choice.
If every first-stage choice has exactly \(n\) second-stage continuations, the count is \(mn\).
If the number of continuations varies, we may need to separate the problem into cases and combine the sum and product principles.
Combining the Two Principles
Many realistic counting problems require both addition and multiplication.
The usual pattern is:
- multiply within each complete case;
- add across disjoint cases.
Symbolically, if case \(A\) has \(ab\) outcomes and case \(B\) has \(cd\) outcomes, with no overlap, then
\[ \boxed{ab+cd} \]outcomes are possible overall.
Example: Two Types of Identification Codes
A system permits either:
- one letter followed by two digits, or
- two letters followed by one digit.
Assume repetition is allowed.
The first type has
\[ 26\cdot10\cdot10=2600 \]possibilities.
The second type has
\[ 26\cdot26\cdot10=6760 \]possibilities.
The two formats are distinct, so the counts add:
\[ \boxed{2600+6760=9360}. \]Example: Routes through Two Hubs
A traveler can go from city \(A\) to city \(D\) through either city \(B\) or city \(C\).
Suppose there are:
- \(3\) routes from \(A\) to \(B\) and \(4\) from \(B\) to \(D\);
- \(2\) routes from \(A\) to \(C\) and \(5\) from \(C\) to \(D\).
Through \(B\):
\[ 3\cdot4=12. \]Through \(C\):
\[ 2\cdot5=10. \]Assuming the two route types are distinct, the total is
\[ \boxed{12+10=22}. \]Think in Terms of Complete Outcomes
A useful discipline is to identify exactly what counts as one complete outcome before doing arithmetic.
For an outfit, one complete outcome might be
\[ (\text{shirt},\text{pants},\text{shoes}). \]For a code, one complete outcome might be
\[ (\text{first symbol},\text{second symbol},\text{third symbol}). \]Once the structure of a complete outcome is clear, the stages of the product principle often become visible.
Sets and the Sum Principle
The sum principle can be stated using finite sets.
If
\[ A\cap B=\varnothing, \]then
\[ \boxed{|A\cup B|=|A|+|B|}. \]More generally, if \(A_1,A_2,\ldots,A_k\) are pairwise disjoint finite sets, then
\[ \boxed{\left|\bigcup_{i=1}^{k}A_i\right| =\sum_{i=1}^{k}|A_i|}. \]Cartesian Products and the Product Principle
The product principle can also be stated using finite sets.
If \(|A|=m\) and \(|B|=n\), then the Cartesian product
\[ A\times B=\{(a,b):a\in A,\ b\in B\} \]contains
\[ \boxed{|A\times B|=mn} \]ordered pairs.
Each first coordinate can be paired with every available second coordinate.
Example: Coordinates on a Small Grid
Suppose
\[ A=\{1,2,3,4\} \]and
\[ B=\{x,y,z\}. \]Then
\[ |A\times B|=4\cdot3=12. \]The product principle counts the \(12\) ordered pairs without requiring us to list them individually.
Restrictions Can Change the Factors
Counting becomes more subtle when restrictions remove choices.
Suppose a three-digit positive integer is formed using decimal digits.
The first digit cannot be \(0\), so it has \(9\) choices. Each later digit has \(10\) choices:
\[ 9\cdot10\cdot10=900. \]Therefore, there are
\[ \boxed{900} \]three-digit positive integers.
Restrictions May Depend on Earlier Choices
Suppose a three-letter string is formed from \(8\) distinct letters with no repetition.
There are \(8\) choices for the first position, \(7\) for the second, and \(6\) for the third:
\[ 8\cdot7\cdot6=336. \]The decreasing factors reflect the restriction against reusing a letter.
Case Splitting Can Restore Uniformity
Sometimes a restriction makes the number of later choices depend on an earlier choice.
In that situation, split the problem into disjoint cases where the number of continuations is easier to describe.
Count each case with the product principle, then combine the case totals with the sum principle.
Example: A Simple Restricted Code
A two-character code is formed from the letters \(A,B,C\) and the digits \(1,2,3,4\). The code must contain one letter and one digit.
There are two possible formats:
- letter–digit;
- digit–letter.
Each format has
\[ 3\cdot4=12 \]outcomes.
The formats are disjoint, so
\[ \boxed{12+12=24}. \]“Or” Does Not Always Mean Add Immediately
The word or suggests alternatives, but overlapping alternatives cannot be added without adjustment.
For example, counting students who study algebra or geometry may involve students who study both.
The simple sum principle is safe only when the cases are disjoint or when the problem has first been reorganized into disjoint cases.
“And” Does Not Always Mean Multiply Immediately
The word and suggests stages, but multiplication requires us to know the number of available continuations.
If later choices depend on earlier choices in irregular ways, a single product may not describe the problem.
We may instead need a decision tree, case analysis, or another counting method.
A Decision Question: Add or Multiply?
Ask:
- Are these separate alternatives for the same final choice? If the alternatives are disjoint, add.
- Are these stages required to build one complete outcome? Multiply the numbers of choices at the stages.
In many problems, both answers occur at different levels.
Example: Transportation Choices
A commuter can travel by bus or by train.
There are \(5\) usable bus routes and \(3\) usable train routes.
If exactly one route is chosen, the total is
\[ 5+3=8. \]This is a sum-principle problem because bus and train routes are alternative ways to make the trip.
Example: Transportation in Two Stages
Suppose a commuter first chooses one of \(4\) routes to a transfer station and then one of \(6\) routes from the station to work.
One complete trip requires both stages:
\[ 4\cdot6=24. \]Therefore,
\[ \boxed{24} \]two-stage trips are possible.
Counting Functions by the Product Principle
Suppose a function maps a three-element set
\[ \{a,b,c\} \]into a four-element set.
Each of the three inputs may be assigned any of \(4\) outputs.
Therefore, the number of possible functions is
\[ 4\cdot4\cdot4=4^3=64. \]Each input assignment is one stage in specifying the entire function.
Binary Strings
A binary string of length \(n\) contains \(n\) positions, and each position may contain either \(0\) or \(1\).
Each position therefore has \(2\) choices.
\[ \boxed{2^n} \]binary strings of length \(n\) are possible.
This is one of the most important recurring uses of the product principle.
Example: Binary Strings of Length Five
A binary string of length \(5\) has
\[ 2\cdot2\cdot2\cdot2\cdot2=2^5=32 \]possibilities.
Therefore,
\[ \boxed{32} \]distinct binary strings have length \(5\).
Finite Sums and Products Already Appear Here
The notation used in these principles generalizes naturally.
If disjoint cases have sizes \(a_1,a_2,\ldots,a_k\), then the total is
\[ \sum_{i=1}^{k}a_i. \]If sequential stages have \(n_1,n_2,\ldots,n_k\) available choices, then the total is
\[ \prod_{i=1}^{k}n_i. \]A later lesson will study finite sums and products as reusable notation and structure in their own right.
Common Error: Adding Sequential Choices
Suppose there are \(4\) appetizers and \(6\) entrées, and a meal contains one of each.
The incorrect count
\[ 4+6=10 \]counts individual menu items, not complete meals.
A meal requires two stages:
\[ \boxed{4\cdot6=24}. \]Common Error: Multiplying Alternative Cases
Suppose a student may enroll in one of \(8\) art electives or one of \(5\) music electives.
If the student chooses exactly one elective, the correct total is
\[ \boxed{8+5=13}. \]Multiplying would incorrectly count pairs containing one art course and one music course.
Common Error: Ignoring Overlap
Suppose \(20\) students participate in chess, \(15\) participate in robotics, and \(6\) participate in both.
Adding
\[ 20+15=35 \]counts the \(6\) students in both groups twice.
The correct count is
\[ 20+15-6=29. \]This is an inclusion–exclusion adjustment, not the simple disjoint sum principle.
Common Error: Forgetting Restrictions
A three-digit positive integer does not have \(10\) choices for every digit.
The first digit cannot be zero, so the correct count is
\[ 9\cdot10\cdot10=900, \]not
\[ 10^3=1000. \]Restrictions must be incorporated at the stage where they become relevant.
Common Error: Treating Dependent Stages as Independent
Suppose two different prizes are awarded to two different students from a class of \(12\).
There are \(12\) choices for the first prize recipient, but only \(11\) remaining choices for the second:
\[ \boxed{12\cdot11=132}. \]Using \(12^2\) would incorrectly allow the same student to receive both prizes.
A Reliable Procedure
- Define one complete outcome.
- Identify whether the problem separates into cases, stages, or both.
- For disjoint alternative cases, add their counts.
- For sequential stages, multiply the available choices.
- Adjust the factors when restrictions remove choices.
- If cases overlap, do not use simple addition without correction.
- Check that every valid outcome is counted.
- Check that no valid outcome is counted more than once.
Example: Full Workflow
A school issues identification codes in one of two formats:
- two letters followed by two digits;
- one letter followed by three digits.
Repetition is allowed.
First format:
\[ 26\cdot26\cdot10\cdot10=67{,}600. \]Second format:
\[ 26\cdot10\cdot10\cdot10=26{,}000. \]Because the two formats are disjoint, add:
\[ 67{,}600+26{,}000=93{,}600. \]Therefore,
\[ \boxed{93{,}600} \]identification codes are possible.
Practice 1: Sum Principle
A store has \(14\) desktop computers and \(11\) laptop computers. If a customer buys exactly one computer, how many choices are available?
Practice 2: Product Principle
A sandwich shop offers \(6\) breads, \(8\) fillings, and \(4\) sauces. How many sandwiches can be made using one choice from each category?
Practice 3: Three-Stage Code
How many codes contain one letter followed by two decimal digits if repetition is allowed?
Practice 4: No Repetition
How many three-letter strings can be formed from \(10\) distinct letters if no letter may repeat?
Practice 5: Two Disjoint Formats
A code is either two letters or three digits. Repetition is allowed. How many codes are possible?
Practice 6: Restriction on the First Digit
How many four-digit positive integers are there?
Practice 7: Mixed Sum and Product
A traveler can reach a destination by either:
- choosing one of \(4\) buses and then one of \(3\) shuttle routes, or
- choosing one of \(5\) direct trains.
How many travel plans are possible?
Practice 8: Binary Strings
How many binary strings of length \(8\) are possible?
Practice 9: Counting Functions
How many functions are there from a four-element set to a three-element set?
Practice 10: Identify the Principle
A student chooses one mathematics elective from \(7\) options and one science elective from \(5\) options. Should the counts be added or multiplied? Explain.
Practice Answers
Practice 1
\[ \boxed{14+11=25}. \]Practice 2
\[ \boxed{6\cdot8\cdot4=192}. \]Practice 3
\[ \boxed{26\cdot10\cdot10=2600}. \]Practice 4
The available choices decrease after each position:
\[ \boxed{10\cdot9\cdot8=720}. \]Practice 5
Two-letter codes:
\[ 26^2=676. \]Three-digit codes:
\[ 10^3=1000. \]Add the disjoint formats:
\[ \boxed{676+1000=1676}. \]Practice 6
The first digit has \(9\) choices, and each remaining digit has \(10\):
\[ \boxed{9\cdot10^3=9000}. \]Practice 7
Bus-and-shuttle plans:
\[ 4\cdot3=12. \]Direct-train plans:
\[ 5. \]Add the two travel types:
\[ \boxed{12+5=17}. \]Practice 8
\[ \boxed{2^8=256}. \]Practice 9
Each of the \(4\) domain elements may be assigned any of \(3\) outputs:
\[ \boxed{3^4=81}. \]Practice 10
Multiply. A complete schedule requires both choices:
\[ \boxed{7\cdot5=35}. \]What to Remember
The sum principle counts disjoint alternatives:
\[ \boxed{m+n}. \]The product principle counts sequential choices:
\[ \boxed{mn}. \]- Add across mutually exclusive cases.
- Multiply across stages required to build one complete outcome.
- Adjust stage counts when restrictions remove choices.
- Split into cases when one uniform product does not describe the problem.
- Do not add overlapping cases without correcting the overlap.
The most important habit is to identify the structure of the outcomes before performing the arithmetic.
Where We Go Next
The sum and product principles provide the arithmetic foundation for more elaborate counting arguments.
The next lesson, Sequential Choices, develops the stage-by-stage viewpoint in greater detail, including changing option counts, restrictions, and structured choice processes.