Complement rule

The complement rule states that the number of things you want is the number of things you don't want subtracted from the total number of things. This provides a method for indirectly counting the cardinality of a set:

How many \(4\)-bit binary strings have at least one \(0\)? Well, there are \(2^4 = 16\) \(4\)-bit binary strings in total. Counting by complement, the number of \(4\)-bit binary strings that do not have at least one \(0\) (in other words, no \(0\)'s) is exactly \(1\), being \(1111.\) Therefore, by the complement rule, \(16 - 1 = 15\) \(4\)-bit binary strings have at least one \(0.\)

How many months in a year do not start with the letter J? It's already known there's \(12\) months in a year. Manually counting, we can see there are \(3\) months that start with the letter J: January, June, and July. By the complement rule, \(12 - 3 = 9\) months do not start with the letter J.

In a standard \(52\)-card deck of playing cards, how many \(6\)-card hands have at least one card of the hearts suit? Since a \(6\)-card hand is simply a \(6\)-combination of the set of playing cards (the deck), there are \(\binom{52}{6}\) \(6\)-card hands in total. To count by complement, we need to first figure out the number of \(6\)-card hands that have no cards of the hearts suit. With \(4\) suits (hearts ♥, clubs ♣, diamonds ♦, spades ♠) and \(13\) cards per suit, we can conclude there are \(52 - 13 = 39\) cards that are not of the hearts suit. Therefore, the number of \(6\)-card hands without hearts is \(\binom{39}{6}.\) By the complement rule, \((\binom{52}{6} - \binom{39}{6})\) \(6\)-card hands have at least one card of the hearts suit.

How many \(8\)-character passwords that can only use numbers and lowercase letters have at least one number and at least one letter? By the rule of product, there are \(36^8\) total \(8\)-character passwords that can only use numbers and lowercase letters. Counting by complement is a little trickier here as we need to count the number of passwords that have no numbers or no letters. In other words, we need to count the number of all-letter and all-number passwords. Using the rule of product again, we see \(26^8\) all-letter passwords exist and \(10^8\) all-number passwords exist. Therefore, \(26^8 + 10^8\) passwords have no numbers or no letters. By the complement rule, \((36^8 - (26^8 + 10^8))\) \(8\)-character passwords have at least one number and at least one letter.

The following question pertains to multisets, but is still an application of the complement rule. Say you want to make a workout schedule. How many ways are there of distributing \(200\) push-ups among the \(7\) days of the week, with at most \(10\) push-ups on Monday? The restriction "at most" is what makes this tricky. Let's negate the statement to count by complement. Now, we want to know how many ways there are of distributing \(200\) push-ups among the \(7\) days of the week, with at least \(11\) push-ups on Monday. Not bad. Let's take care of Monday first by scheduling \(11\) push-ups on that day. There are \(189\) push-ups remaining to distribute among the \(7\) days of the week. Counting the multisets, that totals to \(\binom{189 + 7 - 1}{7 - 1} = \binom{195}{6}\) ways of distributing the push-ups such that at least \(11\) are on Monday. Of course, the total number of ways of distributing the push-ups without any restrictions is \(\binom{200 + 7 - 1}{7 - 1} = \binom{206}{6}.\) Since we counted the negation and the total, now all we have to do is compute \(\binom{206}{6} - \binom{195}{6}\) to get the number of ways of distributing \(200\) push-ups among the \(7\) days of the week such that at most \(10\) are on Monday.

Here's a question related to the inclusion-exclusion principle. Imagine you're trying to unlock your phone, but you forgot your \(4\)-digit passcode. You remember that the passcode has \(7\) in it. How many passcodes fit that description? Let \(P_1\) be the set of all passcodes with a \(7\) as the first digit. By the rule of product, there are \(10^3\) such passcodes. Furthermore, let \(P_2\) denote the set of all passcodes with a \(7\) as the second digit, let \(P_3\) denote the set of all passcodes with a \(7\) as the third digit, and let \(P_4\) denote the set of all passcodes with a \(7\) as the fourth digit. The cardinalities of all these sets are \(10^3.\) The set we are trying to count, the set of all passcodes with at least one occurrence of \(7\), can be represented as \(P_1 \cup P_2 \cup P_3 \cup P_4.\) If we used the inclusion-exclusion principle, that would involve counting the number of elements in a ton of intersections, which would take a pretty long time. Let's try the complement rule instead, which tells us that \(|P_1 \cup P_2 \cup P_3 \cup P_4| = |U| - |\overline{P_1 \cup P_2 \cup P_3 \cup P_4}|\), where \(U\) is the universal set in this context, the set of all \(4\)-digit passcodes, with a cardinality of \(10^4.\) Since \(P_1 \cup P_2 \cup P_3 \cup P_4\) was the set of all passcodes with at least one occurrence of \(7\), its complement, \(\overline{P_1 \cup P_2 \cup P_3 \cup P_4}\), must be the set of all passcodes with no occurrences of \(7\), which has a cardinality of \(9^4.\) Thus, the number of passcodes with at least one occurrence of \(7\) is \(10^4 - 9^4.\)

Lastly, I'd like to share one more problem that requires a well-rounded understanding of combinatorics. How many ways are there to buy a dozen \((12)\) donuts from a bakery if there are \(3\) varieties: glazed, pink-frosted, and Boston cream, but only \(5\) pink-frosted and \(4\) Boston cream donuts are left? The glazed variety is well-stocked. Let's try to write out what we're counting a bit more logically. It's the number of ways of buying \(12\) donuts from \(3\) varieties with the restriction that \(\leq 5\) of them are pink-frosted and \(\leq 4\) of them are Boston cream donuts. Counting by complement, this is equal to the total number of ways of buying \(12\) donuts from \(3\) varieties with no restrictions (which we know from multisets is exactly \(\binom{12 + 3 - 1}{3 - 1} = \binom{14}{2}\)) minus the number of ways of buying \(12\) donuts from \(3\) varieties with the restriction that \(>5\) of them are pink-frosted or \(>4\) of them are Boston cream donuts. Note the use of De Morgan's Laws here to negate the statement. Since we're dealing with integers, we're really counting the number of ways of buying \(12\) donuts from \(3\) varieties with the restriction that \(\geq 6\) of them are pink-frosted or \(\geq 5\) of them are Boston cream donuts. The logical connective "or" suggests that the inclusion-exclusion principle may be used here. Therefore, the number of ways of buying \(12\) donuts from \(3\) varieties with the restriction that \(\geq 6\) of them are pink-frosted or \(\geq 5\) of them are Boston cream donuts is equal to the number of ways that \(\geq 6\) of them are pink-frosted donuts plus the number of ways that \(\geq 5\) of them are Boston cream donuts minus the number of ways that \(\geq 6\) of them are pink-frosted and \(\geq 5\) of them are Boston cream donuts. That results in \(\binom{(12 - 6) + 3 - 1}{3 - 1} + \binom{(12 - 5) + 3 - 1}{3 - 1} - \binom{(12 - 6 - 5) + 3 - 1}{3 - 1} = \binom{8}{2} + \binom{9}{2} - \binom{3}{2}\), which we subtract from the total number of ways to get a final answer of: \(\binom{14}{2} - (\binom{8}{2} + \binom{9}{2} - \binom{3}{2}).\)