UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 5.2 Free with a free account
The Addition and Multiplication Rules
Discrete Mathematics · Chapter 5: Counting Methods and Basic ProbabilitySection 5.2 · lesson 28 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Discrete Mathematics.
Lesson complete
Earn the 4 college credits for Discrete Mathematics
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: The Pigeonhole Principle →← Counting Outcomes and Sample SpacesNext lesson: The Pigeonhole Principle →
In this lesson
2 "how many" questions - one multiplies, the other adds.
- State and justify the Multiplication Rule
- State the Addition Rule and its no-overlap condition
- Choose the right rule with the AND / OR test
- Combine both rules in a single count
Transcript
Everything said in the video, section by section (1,634 words). Read along, or search it.
Counting Methods and Basic Probability
The Addition and Multiplication Rules
Section five point one counted outcomes by listing them one at a time. This section introduces the two basic shortcuts, the multiplication rule and the addition rule. Each is simple on its own. The real skill is telling reliably which one a problem calls for, and this section gives a logical test for that. Then we'll see how the two rules combine, in problems that need both.
The Opening Problem
A Smart Lock, 2 Counting Questions
A smart-lock manufacturer is designing the access system for a shared coworking space. Two very different counting questions come up in the design review. First, how many distinct four-digit entry codes can the keypad support, if repeated digits are allowed? Second, how many successful entries happened this month? Every entry was logged as using exactly one of three methods, a keypad code, a mobile app tap, or a physical fob. And the count for each method is reported separately. Both are how many questions. But they call for entirely different arithmetic. One multiplies, and the other adds. Mixing the two up is one of the most common errors in early combinatorics. And telling them apart reliably, not just applying each one once memorized, is what this section is about.
Theorem 5.2.1
The Multiplication Rule
The keypad question is a sequential choice problem. A code is built by choosing a first digit, then a second, then a third, then a fourth. Every stage has to happen, in order, to produce one code. The multiplication rule says this. Suppose a task is completed through a sequence of k stages. And for every possible way the earlier stages could go, stage i can be completed in exactly n i ways. Then the whole sequence can be completed in n one, times n two, and so on, times n k ways. Notice exactly what the condition asks for. The count of options at each stage can't depend on earlier choices. But the specific options available can.
Justifying the Rule
A Grid, Then Induction
The rule itself is justified by the induction method of chapter four, starting from a two-stage building block. For two stages, arrange every combined outcome in a grid. One row for each stage-one outcome, one column for each stage-two outcome. The grid has n one rows and n two columns, so it has n one times n two cells. That's one cell, and so one total outcome, for every way of pairing the two choices. Now induction on k. The base case, k equals two, is the grid argument itself. For the inductive step, take a task with k plus one stages. Group the first k stages into one combined stage. By the inductive hypothesis, it can be completed in n one times, up to n k, ways. Then apply the two-stage case once more, combining that grouped stage with stage k plus one. That multiplies in one more factor. So by induction, the rule holds for every k, at least two. And it holds trivially for a single stage.
Worked Examples 5.2.1 and 5.2.2
Codes and Asset Tags
Back to the keypad. It accepts a four-digit code, using digits zero through nine, with repetition allowed. Each of the four positions is one stage. Because repetition is allowed, every position has exactly ten possible digits, whatever was chosen elsewhere. So by the multiplication rule, there are ten times ten times ten times ten, which is ten thousand distinct codes. Next, the coworking space labels its shared equipment with an asset tag. Two uppercase letters, followed by three digits, with repetition allowed at every position. That's five stages. Each letter position has twenty-six options, and each digit position has ten. So there are twenty-six times twenty-six, which is six hundred seventy-six, times one thousand. That's six hundred seventy-six thousand distinct tags.
Theorem 5.2.2
The Addition Rule
The entry log question has a different shape entirely. An entry is completed by exactly one of three separate methods, never more than one at a time. The addition rule says this. Suppose a task can be done through one of k separate categories of ways. Category one offers n one ways, category two offers n two ways, and so on. And suppose no single way of doing the task belongs to more than one category. The categories are mutually exclusive. They share no outcomes. Then the total number of ways is n one plus n two, and so on, plus n k. That mutual exclusivity condition isn't a technicality. If two categories share even one outcome, adding directly counts it twice. Correcting for overlap takes a method called inclusion exclusion, which comes in section eight point thirteen. The rule stated here applies only when the categories are confirmed not to overlap.
Worked Examples 5.2.3 and 5.2.4
Entries and Electives
Back to the entry log. This month shows four hundred twenty-eight entries by keypad, six hundred fifteen by app, and one hundred ninety-three by fob. The logging system records exactly one method per entry, so the three categories share no entries. The total is their sum, one thousand two hundred thirty-six entries. Another example. A student must enroll in exactly one elective, chosen from three department lists. Eight in computer science, five in business, and four in design. None is cross-listed, so the addition rule applies directly. Eight plus five plus four is seventeen possible electives. But suppose two of the business electives were cross-listed as design electives. Simply adding eight plus five plus four would count those two courses twice. That overstates the true total by two. Once categories can overlap, the addition rule as stated simply doesn't apply.
5.2.3 Choosing the Right Rule
AND Multiplies, OR Adds
So how do you choose? The reliable test is logical, not a feeling for whether a problem looks like multiplication or addition. It comes down to AND versus OR. If the task needs stage one, AND stage two, AND every stage through k, all happening in sequence to produce one outcome, multiply. If the task uses category one, OR category two, OR another, exactly one category, with no shared outcomes, add. The picture shows why. With multiplication, on the left, every stage-one branch leads into every stage-two branch. So the branches multiply. Two times three is six. With addition, on the right, the categories sit side by side, with no shared members. So their sizes simply add. Two plus three plus one is also six.
Worked Example 5.2.5
Diagnose, Then Solve
Here's the test in action. A meal-kit service lets a customer build an order. They choose exactly one protein from four options, AND one starch from three, AND one vegetable from five. All three are required for every order. Since all three choices are required together, that's AND logic, and the multiplication rule. Four times three times five is sixty distinct bowls. Separately, the customer pays using exactly one of three methods. Credit card, digital wallet, or store credit. Only one method is used per order, and they share no outcomes. That's OR logic, and the addition rule. Three ways to pay, whichever bowl was built.
Table 5.2.1
Diagnostic Checklist
This table pulls the diagnostic signals together. The connector for multiplication is AND. Every stage is completed together. For addition, it's OR. Exactly one category out of several is used. The structure for multiplication is a sequence of stages, and every stage is needed to finish the task. For addition, it's a set of separate categories, and completing any single one finishes the task. The formulas are a product for multiplication, and a sum for addition. And the key requirements. For multiplication, the count of options at each stage stays fixed, even if the options themselves change. For addition, the categories share no outcomes. If they might overlap, use inclusion exclusion instead.
Worked Example 5.2.6
Multiply Within, Add Across
Many real problems use both rules in the same calculation. Multiply within a branch to count its outcomes, then add across branches that can't both happen. Here's an example. The coworking app lets a member book either a hot-desk, or a private room. Exactly one of the two, never both in the same reservation. For a hot-desk, choose one of four floors, AND one of three time blocks. That's four times three, which is twelve ways. For a private room, choose one of two room sizes, AND one of five rooms of that size. That's two times five, which is ten ways. A booking is exactly one branch or the other, so the branches are mutually exclusive. Add across them. Twelve plus ten is twenty-two booking configurations.
Worked Example 5.2.7
Promo Codes in 2 Formats
One more. A streaming service generates promo codes in exactly one of two formats. The formats differ in structure, so no code can satisfy both. Format A is two uppercase letters, then four digits. That's twenty-six squared, times ten to the fourth, which is six million, seven hundred sixty thousand codes. Format B is three digits, then three letters. That's one thousand, times twenty-six cubed, which is seventeen thousand, five hundred seventy-six. So format B gives seventeen million, five hundred seventy-six thousand codes. Every code uses exactly one format, so add across them. The total is twenty-four million, three hundred thirty-six thousand distinct possible promo codes.
Takeaways
AND or OR - Then Count
To summarize. The multiplication rule counts a task built from required stages, by multiplying the option counts. The count at each stage can't depend on earlier choices, even when the specific options do. The addition rule counts a task done by exactly one of several categories, by adding their counts. But only when the categories share no outcomes. The reliable test is AND versus OR. Overlapping categories get double-counted, and correcting that needs inclusion exclusion, later in the course. And many real problems multiply within each branch, then add across the branches. Here's something to think about. A license plate is three letters, then three digits. But the three letters must all be different, while the digits may repeat. Does the multiplication rule still apply? If so, how many plates are possible? And explain, using the rule's actual condition, why this doesn't break it. Even though the letters available at the second and third positions clearly depend on what came before.
About Discrete Mathematics at UPI Study
Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take Discrete Mathematics with UPI Study
Where the credit goes
Universities that work with NCCRS
Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About The Addition and Multiplication Rules
How do I know whether to multiply or add in a counting problem?
What is the Multiplication Rule in counting, and why does it work?
What condition must be true to use the Addition Rule?
How do I solve a problem that needs both the Addition and Multiplication Rules?
About the Discrete Mathematics course
How many college credits is Discrete Mathematics?
How much does Discrete Mathematics cost and what is included?
Which universities accept UPI Study credits?
How long does Discrete Mathematics take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 4 credits in Discrete Mathematics.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
4 credits · NCCRSEnroll →