Complementary counting computes the desired count as Total - Unwanted. It is especially powerful for "at least one" problems. Example: at least one woman in a committee = total committees - all-men committees. For "at least 2," subtract "0 or 1" cases. This avoids enumerating many valid cases. The approach works whenever the complement is simpler to count. Similarly, for "at most k" problems, complement = "more than k" cases. JEE problems frequently disguise complementary counting: "no two vowels together" = total arrangements - arrangements with some vowels together (using inclusion-exclusion). Always verify: desired + complement = total, as a self-check mechanism.
Part of ALG-07 — Permutations & Combinations
Complementary Counting
Want to generate AI summaries of your own documents? NoteTube turns PDFs, videos, and articles into study-ready summaries.
Sign up free to create your own