Session 6A
Counting basics
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- Counting proofs start with two basic rules. The sum rule applies when choices are in disjoint categories: if there are a ways to do task A or b ways to do task B, and you cannot do both at once, then there are a + b total ways. The product rule applies when a procedure is sequential: if there are a choices for step 1 and for each of those there are b choices for step 2, then there are ab total outcomes. These rules are simple, but they are the foundation of most combinatorics.
- A subtle but important skill is defining what counts as one outcome. You must specify whether order matters, whether repetition is allowed, and what the "alphabet" or set of objects is. Many counting mistakes come from silently switching these assumptions. Once your assumptions are clear, counting becomes a chain of product and sum rule applications. Counting is also proof-based because many identities are proven by counting the same set in two different ways, which leads directly into combinations and binomial identities.
Practice
- 1How many 5-letter strings from {A,B,C} (repetition allowed)?
- 2How many 5-letter strings with no repetition from {A,B,C,D,E,F}?
- 3Prove: number of subsets of an n-element set is 2^n.
MCQ
How many 5-letter strings from {A,B,C} with repetition allowed?