View source for Complementary counting

In [[combinatorics]], '''complementary counting''' is a [[counting]] method where one counts what they don't want, then subtracts that from the total number of possibilities. In problems that involve complex or tedious [[casework]], complementary counting is often a far simpler approach. A large hint that complementary counting may lead to a quick solution is the phrase "not" or "at least" within a problem statement.

More formally, if <math>B</math> is a [[subset]] of <math>A</math>, complementary counting exploits the property that <math>|B| = |A| - |B^c|</math>, where <math>B^c</math> is the [[complement]] of <math>B</math>. In most instances, though, <math>A</math> is obvious from context and is committed from mention.

== Complementary Probability ==
There is a [[probability]] equivalent of complementary counting. For any event, the probability it happens plus the probability it does not happen is one. Thus, we have the identity <cmath>P(A) = 1 - P(A^c).</cmath> Like its counting analog, complementary probability often vastly simplifies tedious casework. Unlike complementary counting, though, it sees frequent use as an intermediate step, primarily because computing complements is much easier in probability than in counting.

== Examples ==
Here are some examples that demonstrate complementary counting and probability in action. It is worth noting that complementary probability is not typically an intermediate step, but a framework upon which a solution is built.

=== Example 1 ===
''How many positive integers less than <math>100</math> are not a multiple of five?''

'''Solution''': We use a complementary approach. The total number of positive integers, with no restrictions, is <math>99</math> integers. What we don't want are the multiples of five. These are <math>5, 10,..., 95</math> or <math>1 \cdot 5, 2 \cdot 5,..., 19 \cdot 5</math>; it's easy to see that there are <math>19</math> of them. Thus, our answer is is <math>99-19 = 80</math>. <math>\square</math>

=== Example 2 ===
''[[2006 AMC 10A Problems/Problem 21 | 2006 AMC 10A Problem 21]]: How many four-digit positive integers have at least one digit that is a 2 or a 3?''

'''Solution''': We use a complementary approach. With no restrictions, there are <math>9000</math> four-digit positive integers. What we don't want are the four-digit integers with no digit that is a two or three, Using a [[Constructive counting | constructive]] approach, the first digit can be one of seven integers; <math>1, 4, 5, 6, 7, 8,</math> and <math>9</math>. Note that the first digit cannot be zero, or else it ceases to have four digits. However, the second, third, and fourth digits can be zero; as a result, they have eight options. So, our total number of two-and-three-free numbers is <math>7 \cdot 8^3 = 3,584</math>. Hence, our final answer is <math>9000 - 3584 = 5416</math>, as desired. <math>\square</math>

=== Example 3 ===
''Sally is drawing seven houses. She has four crayons, but she can only color any house a single color. In how many ways can she color the seven houses if at least one pair of consecutive houses must have the same color?

'''Solution''': Use complementary counting. First, we find the total colorings without restriction, which we do by constructing them. She has four options for what color the first house can be, four options for the second, and so on. Hence, there are <math>4^7 = 16384</math> ways she can color the four houses.

Next, we find the possibilities where every house's next-door neighbor is a different color. Using a constructive approach, she has four options for the color of the first house. We have to make sure the next house is a different color; as a result, there are only three options for the color of the second house, with the color of the first house unavailable. By similar logic, there are 3 options for the third house, and so on for every other house. Combining these yields <math>4 \cdot 3^6 = 2916</math> possibilities if every house must be a different color. 

Putting these two together, there are <math>16384 - 2916 = 13468</math> ways she can color the seven houses four colors if at least one pair of consecutive houses must be the same color. <math>\square</math>

=== Example 4 ===
''[[2002 AIME I Problems/Problem 1 | 2002 AIME I Problem 1]] Many states use a sequence of three letters followed by a sequence of three digits as their standard license-plate pattern. Given that each three-letter three-digit arrangement is equally likely, the probability that such a license plate will contain at least one palindrome (a three-letter arrangement or a three-digit arrangement that reads the same left-to-right as it does right-to-left) is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n.</math>''

'''Solution''': We use complementary probability. So first, we find the probability that a license plate has no palindromes; in other words, the probability that the first and third numbers and letters are distinct. The probability the numbers are distinct is <math>\frac{9}{10}</math>, as for every digit of the first number, one out of ten is the same digit; similarly, for the letters, it is <math>\frac{25}{26}</math>. Multiplying these together gives that the probability that a license plate has no palindromes is <cmath>\frac{9}{10} \cdot \frac{25}{26} = \frac{225}{260} = \frac{45}{52}.</cmath> Taking the complement of this, the probability a license plate has a palindrome is thus <math>1 - \frac{45}{52} = \frac{7}{52}</math>. Hence, our answer is <math>7 + 52 = 59</math>. <math>\square</math>

=== Example 5 ===
''[[2008 AMC 12B Problems/Problem 22 | 2008 AMC 12B Problem 22]]: A parking lot has 16 spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires 2 adjacent spaces. What is the probability that she is able to park?''

'''Solution''': Use complementary probability, where we find the probability that no two open spots are consecutive. With no restrictions, the total number of ways the 12 cars could park is <math>_{16} C_{12} = 1820</math>, where <math>_n C_k</math> is a [[combination]]. Finding how many permutations of the cars and spaces leave no two spaces next to each other is a more challenging task, though.

One might eventually think to treat this problem like a distribution, a [[stars-and-bars]] approach. Let the 12 cars be stars and the 4 spaces be bars. Here is one arrangement of our stars and bars; <cmath>| \star \star | \star | \star \star \star \star \star \star \star \star | \star</cmath> The question mandates that no two bars sit next to each other. Thus, we have 13 "slots" where the bars could go (eleven between the stars, two at the endpoints), where only one bar can fit in each slot. It follows that the number of ways to insert these bars is <math>_{13} C_4 = 715</math>.

Then the probability that Auntie Em cannot park is <math>\frac{715}{1820} = \frac{11}{28}</math>. Finally, our answer is <math>1-\frac{11}{28} = \frac{17}{28}</math>. <math>\square</math>

== Resources ==
* [https://artofproblemsolving.com/videos/counting/chapter2/186 AoPS Complementary Counting Part 1]
* [https://artofproblemsolving.com/videos/counting/chapter2/186 AoPS Complementary Counting Part 2]
* [https://artofproblemsolving.com/videos/counting/chapter8/186 AoPS Complementary Probability Part 1]
* [https://artofproblemsolving.com/videos/counting/chapter8/186 AoPS Complementary Probability Part 2]
* [https://artofproblemsolving.com/videos/counting/chapter8/186 AoPS Complementary Probability Part 3]
* [https://artofproblemsolving.com/videos/counting/chapter8/186 AoPS Complementary Probability Part 4]

== See also ==
* [[Casework]]
* [[Constructive counting]]
* [[Overcounting]]

[[Category:Combinatorics]]
[[Category:Definition]]