Counting the Complement

"At least one" problems are everywhere: committees with at least one woman, passwords with at least one digit. Counting them head-on means many cases. Counting the opposite is usually one short step, built from the sum rule and combinations.

Idea clave

To count the outcomes with a property, count all outcomes and subtract those without it: $$\#(\text{at least one}) = \#(\text{all}) - \#(\text{none}).$$

Listen for the words "at least one," "some," "not all" and "contains a." Each is the opposite of a simple condition (none, all, never), and that opposite is usually a single product. A password with no digit is just a string of letters; a committee with no women is just a committee of men; a sequence of dice rolls with no 6 has $5$ choices per roll.

Por qué funciona

Every outcome either has at least one of the thing or has none, never both. So by the sum rule, all $=$ (none) $+$ (at least one). Rearranging gives the formula. The "none" case is usually simple: a committee with no women is just a committee chosen from the men.

A tempting shortcut that overcounts: "choose one woman first, then anyone." A committee with two women is produced twice, once for each woman picked first.

Worked examples

Ejemplo resuelto: Committees with at least one woman

A committee of $3$ is chosen from $4$ women and $3$ men. How many committees include at least one woman?

All committees: $\binom{7}{3} = 35$.
No women: all three from the $3$ men, $\binom{3}{3} = 1$.
At least one woman: $35 - 1 = 34$.

Respuesta: $34$

Ejemplo resuelto: Bit strings

How many bit strings of length $8$ contain at least one 1? At least two 1s?

All strings: $2^{8} = 256$. The only string with no 1 is 00000000, so at least one 1: $255$.
"At least two 1s" is the opposite of "zero or one 1." There is $1$ string with no 1 and $8$ with exactly one (choose its position).
At least two: $256 - 1 - 8 = 247$.

Respuesta: $255$ and $247$

Ejemplo resuelto: Repeated digits

How many $4$-digit PINs (digits 0–9) have at least one repeated digit?

All PINs: $10^{4} = 10{,}000$.
No repeated digit: $10 \cdot 9 \cdot 8 \cdot 7 = 5{,}040$.
At least one repeat: $10{,}000 - 5{,}040 = 4{,}960$.

Respuesta: $4{,}960$

Error común

Choosing "one first, then anyone." For the committees above it is tempting to pick a woman ($4$ ways) and then any $2$ of the other $6$ people ($\binom{6}{2} = 15$), giving $60$. But the committee $\{W_{1}, W_{2}, M_{1}\}$ is produced twice: once with $W_{1}$ picked first and once with $W_{2}$. Committees with more women are counted more times, so $60$ is far too big. Check: a correct method produces each outcome exactly once; ask how many ways your method can produce one particular outcome.

Worked examples

Práctica

Se apoya en

Lleva a

Fuentes y lecturas