The Central Idea
Suppose a finite set of all possible outcomes is \(U\), and the outcomes we want form a subset \(A\).
The outcomes we do not want form the complement
\[ A^c=U\setminus A. \]Because \(A\) and \(A^c\) divide the universe into two disjoint parts,
\[ |U|=|A|+|A^c|. \]Therefore,
\[ \boxed{|A|=|U|-|A^c|}. \]Count What Is Easier
Complementary counting is useful when the desired outcomes are complicated but the undesired outcomes are simple.
Instead of counting the desired set directly, use
\[ \boxed{\text{desired}=\text{total}-\text{undesired}}. \]The main strategic question is not whether direct counting is possible, but which direction produces the simpler calculation.
Example: At Least One Head
A fair coin is tossed \(4\) times. How many outcome sequences contain at least one head?
There are
\[ 2^4=16 \]total sequences.
The complement of “at least one head” is “no heads,” which means
\[ TTTT. \]There is exactly \(1\) such sequence.
Therefore,
\[ \boxed{16-1=15}. \]Why “At Least One” Is a Natural Complement Problem
Directly counting “at least one” often means separating outcomes into many cases:
- exactly one occurrence;
- exactly two occurrences;
- exactly three occurrences;
- and so on.
The complement usually collapses all of those cases into one simple condition: none.
A Useful Logical Pair
The statement
\[ \text{“at least one”} \]has complement
\[ \text{“none.”} \]Therefore,
\[ \boxed{\#(\text{at least one}) =\#(\text{all})-\#(\text{none})}. \]Example: At Least One Six
A six-sided die is rolled \(3\) times. How many sequences contain at least one \(6\)?
Total sequences:
\[ 6^3=216. \]The complement contains no \(6\). Each roll then has only
\[ 5 \]allowed outcomes.
So the complement has
\[ 5^3=125 \]sequences.
Therefore,
\[ \boxed{216-125=91}. \]Example: A Code with at Least One Digit
A three-character code is formed from \(26\) letters and \(10\) digits. Repetition is allowed. How many codes contain at least one digit?
Each position has
\[ 36 \]possible symbols, so the total number of codes is
\[ 36^3. \]The complement contains no digits, so every position must be a letter:
\[ 26^3. \]Therefore,
\[ \boxed{36^3-26^3}. \]Compute Only When Useful
A counting answer does not always need to be expanded numerically.
For example,
\[ 36^3-26^3 \]may communicate the counting structure more clearly than its decimal value.
An exact expression can be the best final form when the structure matters.
Complementary Counting with Binary Strings
How many binary strings of length \(8\) contain at least one \(1\)?
Total binary strings:
\[ 2^8=256. \]The complement contains no \(1\), so the only complement string is
\[ 00000000. \]Therefore,
\[ \boxed{256-1=255}. \]More Than One Forbidden Symbol
Suppose strings of length \(5\) are formed from the alphabet
\[ \{A,B,C,D,E\}. \]How many contain at least one \(A\) or \(B\)?
Rather than count the desired condition directly, count strings containing neither \(A\) nor \(B\).
Total strings:
\[ 5^5. \]Complement strings use only \(C,D,E\):
\[ 3^5. \]Therefore,
\[ \boxed{5^5-3^5}. \]“Not All” Is Another Natural Complement
The complement of
\[ \text{“not all outcomes have property }P\text{”} \]is
\[ \text{“all outcomes have property }P\text{.”} \]If the “all” case is easy to count, complementary counting can simplify the problem dramatically.
Example: Not All Digits Equal
A four-digit code uses digits \(0\) through \(9\), with repetition allowed. How many codes do not have all four digits equal?
Total codes:
\[ 10^4=10{,}000. \]Codes with all digits equal are
\[ 0000,\ 1111,\ \ldots,\ 9999, \]giving
\[ 10 \]complement outcomes.
Therefore,
\[ \boxed{10{,}000-10=9990}. \]Complementary Counting with Restrictions
The total set must itself obey the basic rules of the problem.
For example, if the objects being counted are three-digit positive integers, then the universe is not all length-three digit strings because leading zero is not allowed.
The complement must be taken inside the correct universe.
Example: Three-Digit Integers with at Least One Zero
Count three-digit positive integers containing at least one \(0\).
Total three-digit positive integers:
\[ 9\cdot10\cdot10=900. \]The complement contains no zeros.
The first digit has \(9\) nonzero choices, and each later digit also has \(9\) nonzero choices:
\[ 9^3=729. \]Therefore,
\[ \boxed{900-729=171}. \]Example: At Least One Repeated Symbol
A three-letter string is formed from \(8\) letters, with repetition allowed. How many strings contain at least one repeated letter?
Total strings:
\[ 8^3. \]The complement consists of strings with all letters distinct:
\[ 8\cdot7\cdot6. \]Therefore,
\[ \boxed{8^3-8\cdot7\cdot6}. \]The Complement of “At Least One Repeat”
This pattern is worth remembering:
\[ \text{at least one repetition} \]has complement
\[ \text{all choices distinct}. \]The distinct case is often much easier to count because the available choices decrease predictably.
Example: Repeated Birth Months
Suppose \(5\) labeled people are assigned birth months, and we ignore differences in month lengths.
There are
\[ 12^5 \]possible month assignments.
The complement of “at least two people share a birth month” is “all five birth months are distinct.”
The all-distinct count is
\[ 12\cdot11\cdot10\cdot9\cdot8. \]Therefore,
\[ \boxed{12^5-12\cdot11\cdot10\cdot9\cdot8}. \]Choosing a Good Universe
Complementary counting begins by defining the universe \(U\) carefully.
The universe should include every outcome under consideration but no outcomes that violate the problem's basic setup.
Then the desired set and its complement should partition that universe.
The Partition Requirement
The desired set \(A\) and complement \(A^c\) must satisfy
\[ A\cap A^c=\varnothing \]and
\[ A\cup A^c=U. \]These two conditions guarantee that every outcome is counted exactly once in either the desired set or the complement.
Example: At Least One Even Digit
How many four-digit codes contain at least one even digit?
Assume leading zero is allowed and repetition is allowed.
Total codes:
\[ 10^4. \]The complement contains only odd digits:
\[ \{1,3,5,7,9\}. \]Thus,
\[ 5^4 \]complement codes exist.
Therefore,
\[ \boxed{10^4-5^4}. \]Example: At Least One Vowel
Suppose a four-letter string is formed from the \(26\)-letter English alphabet, with repetition allowed.
Treat \(A,E,I,O,U\) as the \(5\) vowels.
Total strings:
\[ 26^4. \]Strings with no vowels use only the \(21\) consonants:
\[ 21^4. \]Therefore, the number containing at least one vowel is
\[ \boxed{26^4-21^4}. \]Direct Counting Can Require Many Cases
In the vowel example, direct counting would require separate cases for:
- exactly one vowel;
- exactly two vowels;
- exactly three vowels;
- exactly four vowels.
Complementary counting replaces all four cases with one calculation for zero vowels.
Complementary Counting and “At Most” Conditions
Complements can also convert an “at most” condition into a simpler “at least” condition, or vice versa.
For example, the complement of
\[ \text{“at most two failures”} \]is
\[ \text{“at least three failures.”} \]Whether this helps depends on which side is easier to count.
Use the Complement Only When It Helps
Complementary counting is a strategy, not a requirement.
If the desired set is easier to count directly than its complement, direct counting is better.
The goal is to choose the representation that minimizes unnecessary case work.
Example: A Case Where Direct Counting Is Simpler
How many three-digit codes contain exactly one \(7\)?
The desired set is already structurally simple:
- choose the position of the \(7\);
- fill the other two positions with any digit except \(7\).
This gives
\[ 3\cdot9^2. \]Counting the complement would involve several different cases, so direct counting is more efficient here.
Complementary Counting and Decision Trees
A decision tree can make a complement visible.
For example, if a tree contains all possible three-stage outcomes, the leaves that avoid a certain event form the complement.
We can count all leaves, count the unwanted leaves, and subtract.
Complementary Counting and Sets
In set notation,
\[ A^c=U\setminus A. \]For finite sets,
\[ \boxed{|A^c|=|U|-|A|} \]and equivalently
\[ \boxed{|A|=|U|-|A^c|}. \]Complementary counting is therefore a direct application of finite set cardinality.
Example: Avoiding One Particular Outcome
A binary string has length \(12\). How many such strings are not the all-zero string?
Total strings:
\[ 2^{12}. \]Exactly one string is excluded:
\[ 000000000000. \]Therefore,
\[ \boxed{2^{12}-1}. \]Example: Avoiding a Forbidden Initial Symbol
Suppose a four-character string is formed from \(6\) symbols, with repetition allowed. How many do not begin with a particular forbidden symbol?
Total strings:
\[ 6^4. \]Strings beginning with the forbidden symbol have
\[ 1\cdot6^3=6^3 \]possibilities.
Therefore,
\[ 6^4-6^3. \]This simplifies to
\[ \boxed{5\cdot6^3}. \]In this example, direct and complementary counting are equally natural.
Equivalent Counting Methods Can Verify Each Other
When both direct and complementary counting are easy, comparing the two results provides a useful check.
In the previous example, direct counting gives
\[ 5\cdot6^3, \]while complementary counting gives
\[ 6^4-6^3. \]Since
\[ 6^4-6^3=6^3(6-1)=5\cdot6^3, \]the methods agree.
Common Error: Subtracting from the Wrong Total
Suppose we count three-digit positive integers containing at least one zero.
The universe contains
\[ 900 \]three-digit positive integers, not
\[ 1000 \]arbitrary three-digit strings.
The total and the complement must refer to the same universe.
Common Error: Using the Wrong Complement
The complement of
\[ \text{“at least one }A\text{”} \]is not
\[ \text{“exactly one }A\text{.”} \]The correct complement is
\[ \boxed{\text{“no }A\text{.”}} \]Common Error: Forgetting Basic Restrictions in the Complement
If repetition is forbidden in the original problem, it remains forbidden in the complement.
The complement changes the target property, not the underlying rules of the universe.
Common Error: Subtracting Overlapping Bad Cases Separately
Complementary counting works most cleanly when the entire undesired set is counted once.
If the undesired set itself is divided into overlapping cases, simply subtracting each case may overcorrect.
Problems with overlapping bad cases often lead naturally to inclusion–exclusion.
Common Error: Assuming Complementary Counting Is Always Shorter
A complement can be more complicated than the original condition.
Before committing to the method, compare:
\[ \text{difficulty of counting }A \]with
\[ \text{difficulty of counting }A^c. \]Use the simpler side.
A Reliable Procedure
- Define the universe \(U\) of all allowed outcomes.
- Identify the desired set \(A\).
- State the complement \(A^c\) in plain language.
- Check that \(A\) and \(A^c\) partition the universe.
- Count \(|U|\).
- Count \(|A^c|\).
- Subtract using \(|A|=|U|-|A^c|\).
- Check that both counts obey the same underlying restrictions.
Example: Full Complement Workflow
Count five-character strings formed from \(8\) symbols that contain at least one occurrence of a designated symbol \(X\). Repetition is allowed.
Universe:
\[ |U|=8^5. \]Desired event:
\[ A=\{\text{strings containing at least one }X\}. \]Complement:
\[ A^c=\{\text{strings containing no }X\}. \]Each position in the complement has only \(7\) choices, so
\[ |A^c|=7^5. \]Therefore,
\[ \boxed{|A|=8^5-7^5}. \]Practice 1: At Least One Head
How many sequences of \(6\) coin tosses contain at least one head?
Practice 2: At Least One Six
How many sequences of \(4\) rolls of a six-sided die contain at least one \(6\)?
Practice 3: Binary Strings
How many binary strings of length \(9\) contain at least one \(1\)?
Practice 4: At Least One Vowel
How many three-letter strings over the English alphabet contain at least one vowel, assuming repetition is allowed and there are \(5\) vowels?
Practice 5: At Least One Repetition
How many three-character strings formed from \(7\) symbols contain at least one repeated symbol?
Practice 6: Not All Equal
How many five-digit codes are not composed of five identical digits?
Practice 7: Three-Digit Integers
How many three-digit positive integers contain at least one digit \(5\)?
Practice 8: Avoiding Two Symbols
Strings of length \(4\) are formed from \(10\) symbols. How many contain at least one of two designated symbols?
Practice 9: Distinct or Repeated
Four-letter strings are formed from \(9\) letters, with repetition allowed. How many contain at least one repeated letter?
Practice 10: Identify the Error
A student wants to count four-digit positive integers containing at least one zero. The student writes
\[ 10^4-9^4. \]Explain the error and give the correct count.
Practice Answers
Practice 1
There are \(2^6\) total sequences and \(1\) with no heads:
\[ \boxed{2^6-1=63}. \]Practice 2
Total sequences:
\[ 6^4. \]Sequences with no \(6\):
\[ 5^4. \]Therefore,
\[ \boxed{6^4-5^4=671}. \]Practice 3
\[ \boxed{2^9-1=511}. \]Practice 4
Total strings:
\[ 26^3. \]Strings with no vowels:
\[ 21^3. \]Therefore,
\[ \boxed{26^3-21^3}. \]Practice 5
Total strings:
\[ 7^3. \]Strings with all symbols distinct:
\[ 7\cdot6\cdot5. \]Therefore,
\[ \boxed{7^3-7\cdot6\cdot5=133}. \]Practice 6
Total five-digit codes:
\[ 10^5. \]There are \(10\) codes with all digits equal.
\[ \boxed{10^5-10=99{,}990}. \]Practice 7
Total three-digit positive integers:
\[ 9\cdot10\cdot10=900. \]Numbers containing no digit \(5\):
The first digit has \(8\) choices because it cannot be \(0\) or \(5\). Each later digit has \(9\) choices because only \(5\) is excluded.
\[ 8\cdot9\cdot9=648. \]Therefore,
\[ \boxed{900-648=252}. \]Practice 8
Total strings:
\[ 10^4. \]Strings avoiding both designated symbols:
\[ 8^4. \]Therefore,
\[ \boxed{10^4-8^4}. \]Practice 9
Total strings:
\[ 9^4. \]Strings with all letters distinct:
\[ 9\cdot8\cdot7\cdot6. \]Therefore,
\[ \boxed{9^4-9\cdot8\cdot7\cdot6}. \]Practice 10
The student used all four-digit strings as the universe, including strings that begin with \(0\). Those are not four-digit positive integers.
The correct universe has
\[ 9\cdot10^3=9000 \]elements.
The complement contains no zeros, so every position must be nonzero:
\[ 9^4=6561. \]Therefore,
\[ \boxed{9000-6561=2439}. \]What to Remember
Complementary counting uses
\[ \boxed{|A|=|U|-|A^c|}. \]- Define the correct universe first.
- State the complement precisely.
- Use complements when the unwanted outcomes are easier to count.
- “At least one” often pairs naturally with “none.”
- “At least one repetition” often pairs with “all distinct.”
- Keep all original restrictions in both the universe and complement.
- Use direct counting instead when it is simpler.
The main strategic habit is to ask whether counting what does not happen is easier than counting what does.
Where We Go Next
Complementary counting works especially well when the undesired outcomes form one clean set. When several conditions overlap, simple subtraction may count some outcomes too many or remove them too many times.
The next lesson, Inclusion–Exclusion, develops a systematic method for counting overlapping sets correctly.