Constructive vs complementary counting: which one to reach for

Constructive counting and complementary counting are not rival techniques, and treating them as a choice between two skills is why the choice feels hard. They are two descriptions of the same finite set. Constructive counting describes the things you want by saying how to build one. Complementary counting describes them by saying what they are not.

Both are always available. Every counting problem has a complement, and every finite set can in principle be built step by step. So the question is never "which technique does this problem use". It is a cost question, and it has a one-line answer.

The question that decides it

That is the whole decision. Not which set is smaller, and not which set the problem mentions first. Easier to describe means: fewer cases, fewer conditions interacting, a construction with independent steps rather than steps that depend on each other.

If the thing you want has a clean build order, construct it. If the thing you want is a mess but the things you are excluding are a short, tidy list, count the universe and subtract. When the answer to the question is genuinely unclear, that is information too: it usually means neither description is clean yet and the real work is finding a better way to describe the set.

The signals for complementary counting

• "At least one." The single loudest tell in counting. "At least one" is the negation of "none", and "none" is usually a single uniform restriction applied everywhere, which is exactly the shape a product counts easily.
• "Not", "no two", "avoid", "at most one". Any phrasing where the forbidden thing is rare and the permitted thing is common. The rare side is the cheap side to count.
• An obvious universe. Complementary counting only pays if the total is easy. Five-digit strings, all $4$-digit numbers, all subsets of a set: if you can write the total down without thinking, subtraction is cheap.
• A count that would otherwise split into many cases. If constructing forces you to say "either exactly one, or exactly two, or exactly three …", you are about to do inclusion-exclusion by hand. Check the complement first.

The signals for constructive counting

• A build order exists. You can name a first decision, then a second, and the number of options at step two does not depend on which option you took at step one. Multiply.
• "In how many ways can you arrange / seat / choose / assign." These verbs describe a procedure. The procedure is the count.
• The object has independent coordinates. Every element is in the subset or out of it; every seat gets a person; every letter gets a position. Independence is what makes the product legal.
• The complement is worse. Sometimes you reach for the complement, look at it, and find it is the thing with all the cases. Then you construct.

The worked pair

How many five-digit strings of digits, leading zeros allowed, contain at least one $7$?

Construct it and you are immediately in cases: exactly one $7$, exactly two, and so on, or an inclusion-exclusion over which positions hold a $7$. That inclusion-exclusion is $5 \cdot 10^4 - \binom{5}{2}10^3 + \binom{5}{3}10^2 - \binom{5}{4}10 + 1$, five terms and four sign flips, and it does give the right answer.

Complement it instead. Strings with no $7$: each of the five positions has nine choices, so $9^5 = 59049$. Total is $10^5$. The answer is $100000 - 59049 = 40951$. One multiplication and one subtraction.

Both routes land on $40951$. The difference is that one of them has five places to make a sign error and the other has none. On a timed paper that is the entire argument.

The same shape settles a classic AMC-style question: how many four-digit numbers have a repeated digit? All-distinct is a clean construction, $9 \cdot 9 \cdot 8 \cdot 7 = 4536$, because the leading digit cannot be zero and each later digit avoids what came before. There are $9000$ four-digit numbers, so $9000 - 4536 = 4464$ have a repeat. Trying to build a number with a repeat directly means choosing which digit repeats, how many times, and where, which is three nested case splits for a problem that has none.

The trap: the words point, they do not decide

Here is the failure that costs people marks. "At least one" suggests the complement, so they take the complement without checking it is any easier.

Count the subsets of $\{1, 2, \dots, 10\}$ containing no two consecutive integers. The complement is "contains at least one consecutive pair", and by the rule of thumb above you should reach for it. Do not. That complement is a tangle of overlapping pairs and needs inclusion-exclusion over which adjacencies occur.

The set you actually want is the tidy one. Build a subset left to right, deciding for each integer whether to include it, with the single rule that including $k$ forbids $k+1$. That gives $a_n = a_{n-1} + a_{n-2}$, the Fibonacci recursion, and the count for $n = 10$ is $144$.

Constructive counting's tax is the division

The reason constructive counting goes wrong is almost never the multiplication. It is that the construction built some objects more than once.

Arrange the letters of MISSISSIPPI. Eleven letters means $11!$ orderings, but the four $\text{S}$s are interchangeable, and so are the four $\text{I}$s and the two $\text{P}$s, so each distinct arrangement was produced $4! \cdot 4! \cdot 2!$ times. Dividing gives $34650$, and generating the distinct strings directly confirms it.

Seat eight people at a round table where only who-sits-next-to-whom matters. There are $8! = 40320$ orderings and each seating appears once per rotation, so the count is $40320 / 8 = 5040 = 7!$.

Both corrections follow the same instruction: when a count is off by a small integer factor, you built each object that many times. That factor is the size of the group acting on your construction, and finding it is the skill the multiplication never teaches you. This is the half of constructive counting that decides whether you get the mark.

Where the two meet

The cleanest constructive count on the syllabus is a set with $n$ elements has exactly $2^n$ subsets: walk the elements, take each or leave it, two independent choices $n$ times. No division, because no subset gets built twice.

The cleanest complementary argument is $\binom{n}{k} = \binom{n}{n-k}$, which is complementary counting in its purest form. Choosing $k$ elements to keep is choosing $n-k$ elements to discard. It is not a subtraction; it is a bijection between a set and its complement, and it is where the subtraction trick comes from.

Put those together and you get $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$: classify the $2^n$ subsets by size. That is double counting, the third member of this family and the one most often confused with the other two. The distinction worth holding: constructive and complementary counting each count one set once, by a build or by a subtraction. Double counting counts one set twice, two different ways, and equates the answers. Constructive and complementary give you a number. Double counting gives you an identity.

What to practise

Do not solve. Take fifteen counting problems and write two lines on each: the construction, and the complement. Then write which one you would do and why. You will finish fifteen in the time two full solutions take, and the decision is the part you are short of, not the arithmetic.

The technique library has the counting family with the overcount corrections listed, and the problem archive carries the combinatorics problems above in full with expected times. The daily problem posts a fresh one in three tiers every day with no account needed, which is the cheapest way to keep the decision reflex warm.