Why Count the Outcomes That Do Not Work?
Some counting problems ask for outcomes satisfying a restriction, but the restriction can be awkward to build into a direct count. It may be easier to count every possible outcome and then remove the outcomes that fail the condition. This is called complementary counting.
The method is useful for conditions such as “at least one selected item has a property” or “a particular arrangement is not allowed.” Its success depends on being precise about the universe being counted and about exactly which outcomes violate the condition. The counting principles and factorials from the earlier material on arrangements and selections provide the basic tools.
The phrase “within \(U\)” matters. Before subtracting, specify what counts as one outcome and make sure the total and the forbidden count use the same rules. For example, if codes must have a nonzero first digit, that restriction must be used both in the total count and in the count of codes that fail some additional condition.
Why the Subtraction Formula Works
The formula is a direct consequence of how the outcomes divide into two groups: those that satisfy the condition and those that do not. Every outcome belongs to exactly one group, so the groups have no outcomes in common and together contain all of \(U\).
Let \(U\) contain every outcome allowed by the basic rules of the problem, before applying the condition being counted.
Every outcome either satisfies the condition or violates it. It cannot do both, and it cannot do neither.
The satisfying and violating groups partition \(U\), so \(|U|=|A|+|A^c|\). Rearranging gives \(|A|=|U|-|A^c|\).
This reasoning also explains a key limitation: the count being subtracted must include each violating outcome exactly once. If there are several different ways to violate a condition, and an outcome can fit more than one way, simply adding the separate counts can overcount. For a first complement-counting calculation, look for a single, unambiguous description of failure.
“At Least One” as the Complement of “None”
A common use of the method is to count selections or sequences containing at least one item of a specified type. Direct counting may require separate cases for exactly one, exactly two, and so on. The complement is often simpler: “at least one” fails precisely when there are none.
Worked Example: A Code Must Contain a Specified Digit
A four-character code uses distinct digits from 0 through 9. Its first digit must be nonzero, and the code must contain at least one 5. How many codes are possible? The method is to count all eligible codes and subtract those containing no 5. The complement avoids splitting into cases according to the position of the 5.
Total eligible codes. The first digit has 9 choices, namely 1 through 9. After choosing it, 9 digits remain for the second position, then 8 for the third, and 7 for the fourth. Thus the total is
Codes with no 5. The first digit must be nonzero and cannot be 5, giving 8 choices. The second digit can be any of the 8 remaining allowed digits, and the final two positions have 7 and 6 choices. The count is
Therefore the number containing at least one 5 is
Check. The answer is positive and less than the 4,536 eligible codes in total. The first-position rule and the distinct-digit rule were applied in both counts. A common mistake is to treat the first digit as having 10 choices in the total; that would incorrectly include codes beginning with 0.
In problems with repetition allowed, the count of “none” may have a different structure from the count above. The complement principle is unchanged, but the available choices at each position depend on the stated rules. Read conditions such as “distinct,” “without replacement,” and “first digit nonzero” before multiplying.
Excluding a Position Pattern in an Arrangement
For arrangements, a restriction may rule out a specific position pattern. If the unrestricted arrangements are easy to count, count the forbidden pattern and subtract it. Be careful to count the forbidden arrangements themselves, not just the objects involved in the restriction.
Worked Example: Two Cards Cannot Occupy Both Ends
Six distinct inspection cards are placed in a row. Two specified cards must not occupy the first and last positions together, in either order. How many arrangements satisfy the restriction? The method is to subtract the arrangements in which the specified pair occupies the two ends.
All arrangements. The six distinct cards can be arranged in
ways.
Forbidden arrangements. The two specified cards can be assigned to the two ends in \(2!=2\) orders. The remaining four cards can be arranged in the four middle positions in \(4!=24\) ways. Hence the number of forbidden arrangements is
Allowed arrangements. Subtract the forbidden cases from the total:
Check. The 48 forbidden arrangements are a subset of the 720 total, leaving 672 allowed arrangements. A common mistake is to use \(2\cdot5!\) for the forbidden count. Once the specified cards are fixed at the two ends, four cards—not five—remain to be arranged, so the correct count is \(2\cdot4!\).
Counting a Selection with at Least One Member of a Group
Complementary counting applies to unordered selections as well as to ordered codes and arrangements. When a selection must include at least one member of a group, count all selections and subtract the selections made entirely from outside that group. Use combinations because the order of selected members does not matter.
Worked Example: A Committee Must Include a Specialist
A hypothetical review panel is chosen as a committee of 7 from 12 eligible people. Three of the 12 are specialists in a particular area. How many committees contain at least one specialist? Assume every group of 7 people is an eligible committee. The method is to count all committees and subtract those containing none of the three specialists.
All committees. Choose 7 of the 12 eligible people:
Committees with no specialists. There are \(12-3=9\) nonspecialists. Choosing all 7 committee members from these 9 gives
Committees with at least one specialist. Subtract the no-specialist committees:
Check. There are 792 committees in total, and 36 have no specialist, leaving 756. A common mistake is to count only committees with exactly one specialist; that omits committees with two or three. The complement treats all positive numbers of specialists together.
Choosing the Easier Side to Count
Complementary counting is most helpful when the complement has a simpler description or a shorter calculation than the desired outcomes. For an arrangement in which a pair must not be adjacent, for instance, it can be convenient to subtract arrangements in which the pair is adjacent. Treating the adjacent pair as a block gives a direct count of those forbidden arrangements.
Worked Example: Two Books Must Not Be Adjacent
Seven distinct books are arranged on a shelf. Two specified books must not be next to each other. How many shelf arrangements meet this condition? The method is to subtract the arrangements in which the two books are adjacent.
All arrangements. The seven distinct books can be arranged in
ways.
Adjacent arrangements. Treat the two specified books as one block. The block and the five other books make six objects, which can be arranged in \(6!\) ways. Inside the block, the two specified books can appear in \(2!\) orders. Thus the number of adjacent arrangements is
Allowed arrangements. Subtract:
Check. The complement count is less than the total, as required. The factor of 2 accounts for the two possible orders within the adjacent pair; omitting it would count only one internal order.
Common Mistakes and a Reliable Checklist
A complement count can be short, but only after the outcome set is defined correctly. Before calculating, ask what distinguishes one outcome from another: position matters for a code or an arrangement, while order does not matter for a committee. Then apply each rule consistently to the total and the complement.
- Using different universes. Do not include outcomes in the total that violate a basic rule, such as a nonzero first digit, and then forget that rule when counting the complement.
- Misstating the failure condition. The complement of “at least one specialist” is “no specialists,” not “exactly one nonspecialist.” Translate the condition into a precise statement before counting.
- Forgetting order or internal arrangements. In an arrangement problem, count every allowed order of the restricted objects. In a selection problem, do not count different orders of the same selected group as different committees.
- Subtracting an incorrect forbidden count. Check how many positions or choices remain after the restriction has been imposed. Fixed end positions leave four middle positions in the six-card example.
- Adding overlapping violation counts without checking overlap. If one outcome can violate the condition in more than one way, adding separate forbidden counts may count it multiple times. A simple subtraction is valid only when the forbidden count is the number of distinct violating outcomes.
Check Your Understanding
For each problem, identify the total and the complement before calculating.
- A five-character sequence is formed from the letters A, B, C, D, E, and F, with no repeated letter. How many sequences contain A? (Answer: 600)
- Seven distinct objects are arranged in a row. Two specified objects must not occupy the two ends together, in either order. How many arrangements are allowed? (Answer: 4,800)
- A four-digit PIN has a nonzero first digit, and repetition is allowed. How many PINs contain at least one 0? (Answer: 2,439)
- A committee of 5 is selected from 11 people, including 4 members of a specialist group. How many committees include at least one specialist? (Answer: 441)
- Eight distinct books are arranged on a shelf. Two specified books must not be adjacent. How many arrangements satisfy the restriction? (Answer: 30,240)