- Solve counting problems using the Addition and Multiplication Principle
- Solve counting problems using permutations involving [latex]n[/latex] distinct objects
- Solve counting problems using combinations
- Find the number of subsets of a given set
- Solve counting problems using permutations involving n non-distinct objects
Using the Addition and Multiplication Principles
The Main Idea
- Addition Principle:
- Used when counting mutually exclusive events
- If event [latex]A[/latex] can occur in [latex]m[/latex] ways and event [latex]B[/latex] can occur in [latex]n[/latex] ways, and [latex]A[/latex] and [latex]B[/latex] cannot occur simultaneously, then [latex]A[/latex] OR [latex]B[/latex] can occur in [latex]m + n[/latex] ways
- Multiplication Principle:
- Used when counting sequential events or choices
- If event [latex]A[/latex] can occur in [latex]m[/latex] ways and event [latex]B[/latex] can occur in [latex]n[/latex] ways after [latex]A[/latex] has occurred, then [latex]A[/latex] AND [latex]B[/latex] can occur in [latex]m \times n[/latex] ways
- Also known as the Fundamental Counting Principle
- Applications:
- Customizable product options
- Menu combinations
- Outfit selections
- Password possibilities
- And many more real-world scenarios
A local library is organizing its annual summer reading program. They have different reading lists for different age groups and interests. The program is structured as follows:
- Children’s Section (ages 5-12):
- [latex]20[/latex] picture books
- [latex]15[/latex] early chapter books
- [latex]10[/latex] middle-grade novels
- Teen Section (ages 13-17):
- [latex]25[/latex] young adult novels
- [latex]12[/latex] graphic novels
- [latex]8[/latex] non-fiction books
- Adult Section (ages 18+):
- [latex]30[/latex] fiction novels
- [latex]22[/latex] non-fiction books
- [latex]18[/latex] biographies
- [latex]14[/latex] poetry collections
Each participant must choose one book from their age group’s list to read and review. Additionally, the library decides to allow teens to also choose from the Adult Section if they prefer.
- How many total book options are there across all age groups?
- If a family with a 7-year-old, a 15-year-old, and a 40-year-old all participate, how many different combinations of book choices could they make as a family?
A new phone app allows users to create a custom avatar. They can choose:
- [latex]1[/latex] of [latex]8[/latex] face shapes
- [latex]1[/latex] of [latex]6[/latex] hairstyles
- Any number of accessories from a set of [latex]5[/latex] (including choosing no accessories)
- [latex]1[/latex] of [latex]10[/latex] shirt colors
How many unique avatars can be created?
Finding the Number of Permutations of [latex]n[/latex] Distinct Objects
The Main Idea
- Definition of Permutation:
- An ordered arrangement of objects
- Deals with the question “How many ways can we arrange n distinct objects?”
- Permutation Formula:
- [latex]P(n,r) = \frac{n!}{(n-r)!}[/latex]
- [latex]n[/latex]: total number of objects
- [latex]r[/latex]: number of objects being arranged
- Also written as [latex]_nP_r[/latex]
- Special Case:
- When arranging all [latex]n[/latex] objects: [latex]P(n,n) = n![/latex]
- Multiplication Principle Connection:
- Permutations are an application of the Multiplication Principle
- [latex]n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1)[/latex] factors
How many ways can the photographer line up [latex]3[/latex] family members?
How many ways can the family line up for the portrait if the parents are required to stand on each end?
How many ways can [latex]5[/latex] of the [latex]7[/latex] actors be chosen to line up?
You can view the transcript for “Ex: Determine the Possible Number of 4 Color Striped Flags (Permutation)” here (opens in new window).
Finding the Number of Permutations of [latex]n[/latex] Non-Distinct Objects
The Main Idea
- Definition:
- Permutations where some objects are identical or indistinguishable
- Formula: For [latex]n[/latex] objects, where [latex]r_1[/latex] are alike, [latex]r_2[/latex] are alike, etc., up to [latex]r_k[/latex]: [latex]\frac{n!}{r_1! \cdot r_2! \cdot ... \cdot r_k!}[/latex]
- Reasoning:
- Start with total permutations ([latex]n![/latex])
- Divide by permutations of each set of identical objects
- This removes duplicate counts
A florist is creating a large display using:
- [latex]8[/latex] red roses
- [latex]6[/latex] white lilies
- [latex]5[/latex] yellow daisies
- [latex]4[/latex] purple orchids
How many different linear arrangements of these flowers are possible?
You can view the transcript for “Ex 1: Determine the Number of Permutations With Repeated Items” here (opens in new window).
Combinations
The Main Idea
- Definition of Combination:
- A selection of objects where order doesn’t matter
- Notation: [latex]C(n,r)[/latex] or [latex]_nC_r[/latex]
- Combination Formula: [latex]C(n,r) = \frac{n!}{r!(n-r)!}[/latex]
- [latex]n[/latex]: total number of objects
- [latex]r[/latex]: number of objects being selected
- Relation to Permutations: [latex]C(n,r) = \frac{P(n,r)}{r!}[/latex]
- Key Property: [latex]C(n,r) = C(n,n-r)[/latex]
You can view the transcript for “Ex: Determine the Number of Ways 3 Varieties can be Selected from 12. (Combination)” here (opens in new window).
You can view the transcript for “Ex: Evaluate a Combination and a Permutation – (n,1)” here (opens in new window).
Finding the Number of Subsets of a Set
The Main Idea
- Definition of Subset:
- A collection of elements from a set, including the empty set and the set itself
- Power Set:
- The set of all possible subsets of a given set
- Key Formula:
- For a set with [latex]n[/latex] elements, the number of subsets is [latex]2^n[/latex]
- Connection to Combinations:
- Number of subsets = [latex]\sum_{k=0}^n C(n,k) = 2^n[/latex]