Complementary Counting for Restricted Selections

Why Count What You Do Not Want?

Some selection questions sound as though they require listing many different cases. For example, a committee might need to include at least one person from a particular group. One approach is to count committees with exactly one person from that group, then exactly two, and so on, and add the results. But if the condition is simply “at least one,” there is often a shorter route: count all possible committees, then subtract committees with no one from the group.

This strategy is called complementary counting. It is especially useful when the disallowed selections are easier to describe and count than all the separate ways to satisfy the condition. The selections in these examples are unordered: a committee containing A, B, and C is the same committee regardless of the order in which its members are named.

Counting a Selection and Its Complement

When choosing \(k\) objects from \(n\) distinct objects without regard to order, the number of selections is \(\binom{n}{k}\). In particular, choosing \(k\) people for a committee does not create different outcomes for different orderings of the same people.

Suppose \(r\) of the \(n\) objects belong to a group of interest, and the other \(n-r\) objects do not. For a selection of \(k\) objects, the condition “at least one object from the group” fails exactly when every selected object is outside the group. There are \(\binom{n}{k}\) selections altogether and \(\binom{n-r}{k}\) selections made entirely from outside the group. Therefore:

This expression assumes the full pool is divided into the group and its complement, the objects are distinct, and each selection contains exactly \(k\) objects. If there are fewer than \(k\) objects outside the group, then no selection can avoid the group. In that case the disallowed count is zero; equivalently, we use \(\binom{n-r}{k}=0\) when \(k>n-r\).

Why the Subtraction Works

The key is not a special property of committees; it is that every possible selection falls into exactly one of two categories: it satisfies the target condition, or it does not. Those categories do not overlap, and together they account for every selection. This gives a direct counting justification.

In symbols, let \(S\) be the set of all possible selections and \(A\) the subset satisfying the target condition. The selections in \(S\) that are not in \(A\) form its complement, written \(A^c\). Since \(A\) and \(A^c\) are disjoint and together equal \(S\), their counts add:

The proof depends on identifying the complement correctly. Subtraction is valid even when there are many ways to satisfy the condition, but only if every disallowed selection is counted once and only once.

When the Complement Fixes Some Objects

Not every restriction is an “at least one” condition. Complementary counting also works when a rule forbids a particular combination. For instance, if two specified people may not serve together, the disallowed selections are precisely those containing both people. To count those, treat the two specified people as already included and choose the remaining positions from everyone else.

Choosing the Easiest Side to Count

A complement is useful when the opposite condition has a simple description. “At least one” often has an especially simple opposite: “none.” Likewise, a rule forbidding a particular pair has a clearly defined forbidden group: selections containing that pair. In other problems, directly counting the target may be just as easy, or easier. The goal is not to use subtraction automatically, but to compare the work involved in counting each side.

For example, suppose a fictional reading group chooses 5 books from a shelf of 12, of which 4 are reference books and 8 are novels. To find the number of selections with at least one reference book, counting “no reference books” is straightforward: choose all 5 books from the 8 novels. The set of all books and the disallowed set satisfy the assumptions for combinations: the books are distinct, exactly 5 are chosen, and order on the shelf does not affect which books were selected.

Common Mistakes

• Subtracting the wrong complement. For “at least one nurse,” subtract committees with no nurses, not committees with exactly one nurse. The exact opposite of “at least one” is “none.”
• Counting the forbidden selections incorrectly. If a forbidden committee must contain two specified people, those two people are already chosen. Count only the remaining positions from the remaining people.
• Using permutations for an unordered selection. If a committee is defined by its members, rearranging the same members does not create a new committee. Use combinations, not arrangements.
• Subtracting a count that overlaps itself. If the forbidden condition can happen in different ways, check whether a selection could be counted under more than one forbidden case. The complement count must count each disallowed selection exactly once.
• Forgetting the basic selection setup. The combination count assumes distinct objects and a fixed selection size. If order matters, or objects can be selected more than once, the counting model must change.

A useful final check is to describe in words what one item in each count represents. For example, \(\binom{7}{4}\) in the committee example counts one particular group of four people chosen from the seven non-nurses. This makes it easier to catch a mismatch between the scenario and the formula.