
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Additive and Multiplicative Principles in Discrete Mathematics
In discrete mathematics and combinatorics, we work with counting problems a lot and we aim to calculate the number of ways certain outcomes can be produced.
Additive and multiplicative principles are useful in calculating the total number of possible outcomes in a variety of problems, from simple situations like choosing meals at a restaurant to more complex ones involving sets and functions.
Read this chapter to get a clear understanding of additive and multiplicative principles and how they are applied in discrete mathematics.
The Additive Principle
The concept of additive principle is quite straightforward. It is applied when there are two or more mutually exclusive events. So that the events cannot happen simultaneously.
The principle states that if event A can occur in m ways and event B can happen in n ways, and these events are disjoint (so that they cannot occur at the same time), then the total number of ways either event A or event B can happen is the sum of the individual possibilities.
Mathematically, it is expressed as −
$$\mathrm{\text{Total number of outcomes } = \:m \:+\: n}$$
Example 1: Selecting Food Items from a Menu
Consider a restaurant that offers 8 appetizers and 14 entres. If we are only going to choose one dish, either an appetizer or an entre, how many options do we have? Since selecting an appetizer and choosing an entre are disjoint events (we cannot choose both at the same time), we can simply add the number of choices −
$$\mathrm{\text{Total choices } =\: 8 \:+\: 14 \:=\: 22}$$
So that, we have 22 different options for the meal.
Example 2: Selecting Playing Cards
Consider we have a deck of 52 cards, of which 26 are red, and 12 are face cards. Then how many ways can we select a card that is either red or a face card?
At first glance, it might seem like we should add the two numbers together, but there's a problem. six of the face cards are also red. If we simply added the 26 red cards to the 12 face cards, we would double-count those six cards. The correct way to handle this is by subtracting the overlap:
$$\mathrm{\text{Total choices } = \:26 \:+\: 12 \:\: 6 \:=\: 32}$$
So, there are 32 different cards that are either red or face cards.
Example 3: Selecting Letters for Words
The third example is on words and letters. If we want to create a two-letter word that starts with either the letter 'A' or 'B', the additive principle can be used once again. There are 26 letters in the alphabet, so we the word starts with 'A', the second letter can be any of the 26 letters. The same is true for words starting with 'B'. This gives us −
$$\mathrm{\text{Total words } =\: 26\: (A-start) \:+\: 26\: (B-start) \:= \:52}$$
Thus, we have 52 different words that start with either 'A' or 'B'.
The Multiplicative Principle
After the additive property, let us see the multiplicative principle. This is also used when we have two or more events. and each event can happen independently of the others. It states that if event A can occur in m ways, and after event A occurs, event B can occur in n ways, then the total number of ways both events can occur is the product of the individual possibilities −
$$\mathrm{\text{Total number of outcomes } \:=\: m \:\times\: n}$$
Example 1: License Plates
Let us understand with example. Consider the problem of creating a license plate with three letters followed by three numbers. The multiplicative principle applies here because choosing each letter and each number is an independent event. There are 26 choices for each of the three letters, and 10 choices for each of the three numbers. Therefore, the total number of possible license plates is −
$$\mathrm{\text{Total plates } =\: 26 \:\times\: 26 \:\times\: 26 \:\times\: 10 \:\times\: 10 \:\times\: 10 \:=\: 17,576,000}$$
Thus, there are 17,576,000 possible license plate combinations.
Example 2: Combining Food and Toppings
Next example is quite interesting. Consider we are at a yogurt shop and we can choose from 6 yogurt flavors and 4 toppings, the multiplicative principle tells us how many total combinations are there. Since we know that the yogurt choice is independent of the topping choice, we multiply the number of options −
$$\mathrm{\text{Total combinations } \:=\: 6 \:\times\: 4 \:=\: 24}$$
So, we have 24 different combinations of yogurt and toppings.
Example 3: Counting Functions
Another interesting problem is the counting function. Here, we need to count how many functions can be created from the set {1, 2, 3, 4, 5} to the set {a, b, c, d}. A function assigns each element in the domain (the set of numbers) to an element in the codomain (the set of letters). For each of the five numbers, we can choose one of the four letters. Using the multiplicative principle, the total number of functions is −
$$\mathrm{\text{Total functions } =\: 4 \:\times\: 4 \:\times\: 4 \:\times\: 4 \:\times\: 4 \:=\: 45 \:=\: 1024}$$
Thus, there are 1024 possible functions from the set of five numbers to the set of four letters.
Combining Additive and Multiplicative Principles
Sometimes, both the additive and multiplicative properties are used together in the same problem. This happens when there are different stages of decision-making. At some stages it involve exclusive choices (additive principle), while others involve independent choices (multiplicative principle).
Example of Choosing an Outfit
Let us say we have 9 shirts and 5 pairs of pants. Now in our example, on a regular day, we would wear both a shirt and a pair of pants. But on a special day we might choose to wear just a shirt or just a pair of pants. We can break this problem into two parts −
Regular day (Multiplicative Principle) − We choose both a shirt and pants, so −
$$\mathrm{\text{Total outfits } =\: 9 \:\times\: 5 \:=\: 45}$$
Special day (Additive Principle) − We wear either a shirt or pants, but not both −
$$\mathrm{\text{Total choices } =\: 9 \:+\: 5 \:=\: 14}$$
In this case, we used both principles to solve different parts of the problem.
Conclusion
In this chapter, we explained how the additive principle helps us calculate the total number of ways when choosing between mutually exclusive options. We also presented the multiplicative principle and explained how it helps us find the total outcomes when we make independent choices.
We explained both the principles through various everyday examples such as selecting a food item from a menu in a restaurant, creating license plates, and dressing up.