1
Classify before computing
Order and repetition determine which of four formulas applies. Answering those two questions out loud prevents most errors.
Lesson · Combinatorics and Counting · Technique
Choosing a Counting Method
A summary of the course as a procedure: classify the problem, apply the rule, and verify. Most errors are classification errors, and most of them are caught by a small-case check.
1. Does ORDER matter? 2. Is REPETITION allowed?
3. Are there RESTRICTIONS? cases, complement, or inclusion–exclusion
4. CHECK on a small case where enumeration is possible.
A right calculation of the wrong quantity is the standard failure.
The procedure
Core ideas
What this lesson establishes
The arithmetic in this course is easy. Deciding what to compute is not, and checking is what catches the difference.
2
Restrictions are handled by three techniques
Constrain first, split into cases, or count the complement. Inclusion and exclusion is the general version of the third.
3
Always check a small case
Shrink the parameters until enumeration is possible. A formula disagreeing with a list is wrong, whatever the reasoning looked like.
The material
The decision procedure
The four questions, the whole toolkit in one table, and how to verify.
Step 1: order and repetition
order matters order does not
repetition forbidden P(n, r) C(n, r)
repetition allowed nʳ C(n + r − 1, r)
Ask what makes two outcomes different. If rearranging the same objects gives a new outcome, order matters. If an object can be used twice, repetition is allowed. At n = 5, r = 3 these give 60, 10, 125 and 35 — four different answers to four different questions.
Step 2: restrictions
- A constrained position: choose it first, then the rest freely.
- Varying counts: split into cases where the count is constant, then add.
- "At least one": count the complement.
- Overlapping conditions: inclusion and exclusion.
- Adjacency required: glue into a block, count, multiply by internal arrangements.
- Adjacency forbidden: arrange the others, then choose gaps.
Step 3: the whole toolkit
identical objects, distinct boxes C(n + r − 1, r) stars and bars
distinct objects, distinct boxes multinomial coefficient
arrangements of a multiset n!/(n₁!⋯n_k!)
circular arrangements (n−1)!
no fixed points Dₙ
at least one of several properties inclusion–exclusion
answer needed for every n generating function
an identity to prove double count or biject
existence rather than a count pigeonhole
Step 4: verification
- Shrink and enumerate. Set n = 3, r = 2 and list. The lab does this up to 400 objects.
- Count a second way. Cases and complement should agree. Two routes to one number is the strongest cheap check available.
- Check the magnitude. The answer cannot exceed the unrestricted count or fall below zero.
- Check the extremes. Does the formula give the right answer at r = 0 and r = n? Those are where off-by-one errors surface.
The habit worth taking from this course is the last one. A formula checked at its boundaries and against one small enumeration is very unlikely to be the right calculation of the wrong quantity, which is the failure this whole procedure exists to prevent.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
The procedure
Four questions, in order, before any arithmetic.
1
Does order matter?
Ask what makes two outcomes different. Committees and hands: no. Podiums and passwords: yes.
2
Is repetition allowed?
Can an object be used twice? Drawing with replacement, yes; without, no.
3
What are the restrictions, and which technique fits?
Constrain first, split into cases, complement, or inclusion and exclusion.
4
Verify
A small enumeration, a second method, and the boundary values. Three cheap checks that between them catch nearly everything.
Choosing a method
Score 0 / 0Choose the answer you can justify.
One problem, fully classified
How many 5-letter strings over {a,…,z} have no repeated letter and at least one vowel?
1. ORDER? yes — strings
2. REPETITION? no — "no repeated letter"
⟹ base rule is P(26, 5)
3. RESTRICTION? "at least one vowel" ⟹ complement
all: P(26,5) = 26·25·24·23·22 = 7 893 600
no vowel: P(21,5) = 21·20·19·18·17 = 2 441 880
answer: 7 893 600 − 2 441 880 = 5 451 720
4. CHECK
magnitude: 5 451 720 < 7 893 600 ✓
proportion: 1 − 2441880/7893600 ≈ 0.691 — plausible,
since 5 of 26 letters are vowels and there are
5 chances to hit one ✓
small case: length 2 from {a,b,c,d} with vowel a:
P(4,2) − P(3,2) = 12 − 6 = 6,
and listing gives ab,ba,ac,ca,ad,da ✓
The small-case check is the one that would catch a misclassification. Enumerating six strings takes ten seconds and confirms that the formula counts what was intended, which no amount of re-reading the arithmetic can.
Common mistakes
1
Computing before classifyingThe formula is the last step, not the first. Two sentences of classification prevent most wrong answers.
2
Skipping the check because the reasoning felt soundWrong classifications feel exactly as sound as right ones. That is what makes them dangerous and what makes the check worth doing.
3
Ignoring the boundariesr = 0 and r = n are where off-by-one errors show. Both take a second to evaluate.
Check your understanding
✓
Finish when classification precedes computation automatically.
Five problems from this course, without looking back: the 4-digit PINs, the podium from ten runners, the 5-card hands, five doughnuts from three kinds, and the arrangements of BANANA. For each, write the two answers — order? repetition? — and the rule they select before computing anything; they should land on four different rules and one multiset. Then verify the doughnuts by listing. That sequence — classify, compute, check — is the whole course.
Note: Discrete Probability turns these counts into probabilities by dividing by the size of the sample space, so every classification error here becomes a wrong probability there. The counting is the hard part; the division is not.