Complementary counting

When it is difficult to count the outcomes that meet our criteria, we can try the complementary counting approach. Complementary counting counts the outcomes that do not meet our criteria and subtracts that from the total number of all outcomes. Let’s use some examples to explain the approach.

A row in a movie theater has 8 seats. In how many ways can we place 8 people in the row if two of the people, Alex and Jack, refuse to sit together?

Solution: Does the problem look familiar? We just solved the same problem using casework in the last section. Now let’s solve it using complementary counting. We can count the number of permutations if there is no restriction and then subtract the number of cases that Alex and Jack sit together. The number of permutations without restriction is To calculate the cases that Alex and Jack sit together, we can use the general rule that we derived when a subgroup of elements needs to stay together. First, they are treated as one person in the permutation with the other 6 people, and we have permutations. Since Alex and Jack are distinguishable, we multiply that number by the permutations within the group, which is Therefore, the number of cases that Alex and Jack sit together is and the number of cases that Alex and Jack do not sit together is .

How many 3-digit integers contain the digit 8 at least once?

Solution: Since a 3-digit number may contain one 8, two 8s, or three 8s, it is much easier to count the 3-digit numbers that do not contain the digit 8. Without restriction, there are choices (as a number cannot start with ) for the hundreds digit; 10 choices () for the tens digit; 10 choices for the ones digit. Hence, there are 3-digit numbers . If we remove digit 8 from each step, the number of outcomes becomes Therefore, the number of 3-digit numbers that contain the digit 8 at least once is.

How many 4-digit integers contain the digits 1, 2, or 3 at least once?

Solution: It is easier to count the 4-digit numbers that do not contain digits 1, 2, or 3. For the thousands digit, there are 6 choices (4, 5, 6, 7, 8, 9); for hundreds digit, tens digits, and unit digits, there are 7 choices each (0, 4, 5, 6, 7, 8, 9). Therefore, the number of 4-digit integers that do not contain 1, 2, or 3 is Since there are 9000 4-digit numbers (1000-9999), the number of 4-digit integers that contain 1, 2, or 3 at least once is

Part A. A row of chairs has 7 chairs. How many ways can 4 girls and 3 boys be seated in the row so that at least 2 girls sit together?

Part B. A row of chairs has 8 chairs. How many ways can 4 girls and 4 boys be seated in the row so that at least 2 girls sit together?

Solution. This is another problem where we can apply complementary counting. For part A. if there is no restriction, the total number of permutations is . Let’s consider the cases that no two girls sit together; the arrangement must be . The number of permutations that no two girls sit together is . Therefore, the number of ways that at least 2 girls sit together is .

Part B is more complex. If there is no restriction, the number of permutations is Let’s consider the cases that no two girls sit together. Unlike part A, there are more choices as there are 4 boys. Let’s arrange the 4 boys first. There are permutations. As the following arrangement shows, 4 boys separate the linear space to 5 subspaces:

If no two girls sit together, each subspace has at most one girl. The first girl can choose from any of the 5 subspaces; the second girl can choose only from the remaining 4 subspaces; the third girl can choose from the remaining 3 subspaces; the last girl can choose from the remaining 2 subspaces. The number of choices for girls is The total number of arrangements where no two girls sit together is Therefore, the number of ways that at least 2 girls sit together is .