1
Handle the constrained choice first
If the first digit cannot be 0, choose it first (9 ways) and then the rest freely. Choosing left to right regardless is what creates the difficulty.
Lesson · Combinatorics and Counting · Basic counting
Counting with Restrictions
Restrictions make counting harder in a specific way: they break the product rule's uniformity. Three techniques repair it — apply the constraint first, split into cases, or count the complement.
Place the CONSTRAINED positions first.
Split into cases where the counts are uniform, then add.
"at least one" → count the complement
Check: do the cases overlap? do they cover everything?
Three repairs
Core ideas
What this lesson establishes
A restriction is a place where the product rule stops applying directly. Each technique restores it.
2
Split into cases when the count varies
Cases must be disjoint and exhaustive — the same discipline as a proof by cases in “Cases, Counterexamples, and Writing a Proof” in Logic and Proof.
3
Complement when the restriction says "at least"
The complement of "at least one" is "none", which is a single unrestricted count.
The material
Working with restrictions
The three techniques, each on an example where it is clearly the right one.
Constrain first
Example · Leading digit
How many 4-digit numbers are there? The first digit cannot be 0, so choose it first: 9 ways, then 10 · 10 · 10 for the rest, giving 9000. Working left to right without noticing the restriction gives 10⁴ and counts 0123 as a four-digit number.
Example · Two constraints at once
Four-digit numbers, first digit nonzero and last digit even. Constrain both ends first: 9 choices for the first, 5 for the last, then 10 · 10 in the middle — 9 · 10 · 10 · 5 = 4500. Order of consideration is free; order of positions is not.
Split into cases
Example · A constraint that interacts
Four-digit numbers with first digit nonzero and all digits distinct. Constrain first: 9 choices for the leading digit. The second digit may be anything except the first, including 0, so 9 choices; then 8; then 7. Total 9 · 9 · 8 · 7 = 4536. Note the second count is 9 and not 8 — 0 becomes available exactly because it was excluded from the first position.
Where two restrictions genuinely interact, cases are unavoidable. To count the strings of length 4 over {a, b, c} with at least two as, split by the number of as — exactly two, exactly three, exactly four — count each, and add. The cases are disjoint because a string has one definite number of as. The worked example below does it, and then does it again by complement.
Complement
Example · At least one repeat
How many 5-digit PINs have at least one repeated digit? All PINs: 10⁵ = 100000. All-distinct PINs: 10 · 9 · 8 · 7 · 6 = 30240. Answer 69760. The direct count would need cases for one pair, two pairs, a triple, and so on — overlapping and easy to get wrong.
The general signal: if the condition is "at least" something, or "not all", or "some", the complement is usually a single clean count. If it is "exactly", cases are usually right.
Checking the answer
- Do the cases overlap? If an object satisfies two, it was counted twice.
- Do the cases cover everything? A missing case is an undercount that never announces itself.
- Does a small instance check out? Shrink n until you can enumerate by hand and compare with the formula. The lab does this to 400 objects.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Handling a restriction
Identify what the restriction breaks, then choose the repair.
1
Locate the constrained positions
Deal with them first so the remaining choices are uniform. This alone handles most restrictions.
2
If the counts still vary, split into cases
Choose the case variable so that within each case the product rule applies cleanly.
3
If the condition is "at least", complement
Total minus the objects failing the condition. One subtraction, no overlap.
4
Verify on a small instance
Shrink the parameters until enumeration is possible and compare. A formula that disagrees with a list is wrong.
Restrictions
Score 0 / 0Choose the answer you can justify.
At least two a's, two ways
How many strings of length 4 over {a, b, c} have at least two as?
All strings: 3⁴ = 81
BY CASES on the number of a's — disjoint, because a string has
one definite number of them.
exactly two: which two positions hold the a's?
12 13 14 23 24 34 — six choices
the other two positions: 2 · 2 = 4 (b or c each)
6 · 4 = 24
exactly three: which position is NOT an a? 4 choices,
and that position is b or c: 4 · 2 = 8
exactly four: aaaa 1
24 + 8 + 1 = 33
BY COMPLEMENT: the strings that FAIL have zero or one a.
no a: 2⁴ = 16
exactly one: 4 positions · 2³ = 32
81 − 16 − 32 = 33 agree
Two independent routes to 33. That agreement is the real check: a single method producing a plausible number is not evidence that the classification was right, and the case method is where a missing case would show up. The six position pairs were listed by hand; “Combinations” gives them a name and a formula, C(4, 2) = 6, and from then on they need not be listed.
Common mistakes
1
Ignoring the leading-digit restriction10⁴ counts 0123 as a four-digit number. Constrained positions get chosen first for exactly this reason.
2
Forgetting that excluding a value from one position frees it for anotherAfter choosing a nonzero first digit, the second digit has 9 options, not 8: 0 has become available.
3
Cases that overlap or leave a gapBoth errors are silent. Check the cases sum to the unrestricted total when the restriction is removed.
Check your understanding
✓
Finish when you check a restricted count two ways.
Count the 4-digit numbers (leading digit nonzero) that contain at least one 7, by complement and by cases on the position of the first 7 — a classification that is disjoint and exhaustive because every such number has exactly one first 7. Constrain the leading digit first in every case. If the two totals agree you have both the arithmetic and the classification right.
Note: The instinct to count what you want directly is usually the expensive one. Complementary counting, and inclusion and exclusion, both amount to counting something easier and correcting — which is the dominant strategy in this course.