Repairing an overcount

Idea: Add, then repair

Count each group alone, then subtract what you counted twice.

• Multiples of $6$ up to $300$: $50$
• Of $9$: $33$; of both, that is of $18$: $16$
• Total: $50+33-16=67$

Formula: Inclusion and exclusion

$|A\cup B\mid =\mid A\mid +\mid B\mid -\mid A\cap B|$

Add the sets, then subtract the overlap once.

Common mistake: Both means the least common multiple

Divisible by $6$ and $9$ is not divisible by $6\times 9=54$.

Instead Use the least common multiple, $18$. The product works only when the numbers share no factor.

Idea: Why the signs alternate

With more sets: add the singles, subtract the pairs, add the triples, and so on.

• An element in $3$ sets: $\left(\genfrac{}{}{0ex}{}{3}{1}\right)-\left(\genfrac{}{}{0ex}{}{3}{2}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$
• Every element ends up counted exactly once

Idea: Count what you do not want

"Not adjacent", "at least one" and "none" signal the complement.

• A pair not adjacent in a row of $7$: $7!-2\times 6!=3600$

Example: No letter in its own envelope

$4$ letters go into $4$ addressed envelopes. In how many ways does no letter reach its own?

1. At least one right: $24-12+4-1=15$
2. None right: $4!-15=9$

Formula: Derangements

$D(n)=(n-1)\times (D(n-1)+D(n-2))$

Start from D(1) = 0 and D(2) = 1. The share of derangements settles near 1/e.

Quick check: 5 letters, 5 envelopes

In how many ways can $5$ letters go into $5$ addressed envelopes with no letter in its own?

Idea: Narrate the correction

State the sets, then what got counted twice and how you repair it.

• Say so before you switch to the complement
• Close with a case you can list, such as $D(3)=2$