Inclusion and exclusion

When the sets being counted overlap, adding their sizes counts some elements more than once, and the question is how to correct the total exactly.

The sum rule adds the sizes of sets that do not overlap, and the previous lesson ended where it fails: of the integers from $1$ to $100$ , fifty are divisible by $2$ and thirty-three by $3$ , but $50 + 33 = 83$ is too many, because the multiples of $6$ are in both lists. This lesson builds the exact correction for any number of sets and spends it on three problems that are hard to attack any other way. It assumes the language of sets and the binomial coefficient $(\binom{n}{k})$ , the number of $k$ element subsets of an $n$ element set.

Two overlapping sets

Write $| A |$ for the number of elements of a finite set $A$ . The sum $| A | + | B |$ counts every element of $A \cup B$ , but it counts the elements of $A \cap B$ twice, once in $A$ and once in $B$ . Subtracting $| A \cap B |$ removes the second copy and nothing else:

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

Check this element by element, because that check is the proof that generalises. An element in $A$ only contributes $1$ to the right side, through $| A |$ ; one in $B$ only contributes $1$ through $| B |$ ; one in both contributes $1 + 1 - 1 = 1$ ; one in neither contributes nothing. Each element of the union is counted once.

For the question left open, let $A$ be the multiples of $2$ up to $100$ and $B$ the multiples of $3$ . An integer is in both exactly when it is divisible by $6$ , and there are $⌊ 100 / 6 ⌋ = 16$ of those, where $⌊ x ⌋$ means $x$ rounded down. So $| A \cup B | = 50 + 33 - 16 = 67$ , and $33$ integers are divisible by neither, which is often the count actually wanted.

The integers from 1 to 100, with A the 50 multiples of 2 and B the 33 multiples of 3. The overlap holds the 16 multiples of 6, leaving 34 in A only and 17 in B only, so the union has 34 + 16 + 17 = 67 elements and 33 integers lie outside both.

The one step needing thought was the intersection. For divisors sharing a factor it is the multiples of the least common multiple: divisible by both $4$ and $6$ means divisible by $12$ , not $24$ .

Three sets

With three sets, start from $| A | + | B | + | C |$ and subtract the three pairwise intersections, since elements in two sets were counted twice. An element in all three sets, though, was counted three times and then subtracted three times, once for each pair, so it is now counted $3 - 3 = 0$ times and has to be put back:

| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |

Element by element: one in exactly one set is counted once; one in exactly two, say $A$ and $B$ , is counted by $| A |$ and $| B |$ and subtracted by $| A \cap B |$ alone, a net $2 - 1 = 1$ ; one in all three is counted $3 - 3 + 1 = 1$ time. The numbers being added and subtracted, $1$ ; $2, 1$ ; $3, 3, 1$ , are rows of Pascal's triangle, which is the clue to the general case.

Example. How many integers from $1$ to $1000$ are divisible by at least one of $2$ , $3$ and $5$ ?

Let $A$ , $B$ and $C$ be the multiples of $2$ , $3$ and $5$ . The singles are $500$ , $⌊ 1000 / 3 ⌋ = 333$ and $200$ , totalling $1033$ . The pairs are the multiples of $6$ , $10$ and $15$ , numbering $166$ , $100$ and $66$ , totalling $332$ . The triple is the $33$ multiples of $30$ . So the union has $1033 - 332 + 33 = 734$ elements, and $266$ integers up to $1000$ are divisible by none of the three. Testing each integer by computer gives the same $734$ .

Now you. How many integers from $1$ to $600$ are divisible by at least one of $4$ , $6$ and $10$ ?

Answer

The singles are $150$ , $100$ and $60$ . The pairwise intersections are the multiples of the least common multiples $12$ , $20$ and $30$ , numbering $50$ , $30$ and $20$ , and the triple is the $10$ multiples of $60$ . The count is $310 - 100 + 10 = 220$ . Using products ( $24$ , $40$ , $60$ and $240$ ) instead would give a wrong answer.

The general formula

Take finite sets $A_{1}, A_{2}, \dots, A_{n}$ . For each $k$ from $1$ to $n$ , let $S_{k}$ be the result of choosing $k$ of the sets in every possible way, intersecting each choice, and adding up the sizes of those $(\binom{n}{k})$ intersections. So $S_{1}$ is $| A_{1} | + \dots + | A_{n} |$ , $S_{2}$ adds the sizes of all pairwise intersections, and $S_{n}$ is the size of the intersection of all $n$ sets. The principle of inclusion and exclusion says

| A_{1} \cup A_{2} \cup \dots \cup A_{n} | = S_{1} - S_{2} + S_{3} - \dots + (- 1)^{n - 1} S_{n}

In words: add the sizes of the sets, subtract the pairwise overlaps, add the triple overlaps, and keep alternating.

The proof counts how many times each element is included. Take an element $x$ in exactly $m$ of the sets, with $m \geq 1$ . An intersection of $k$ sets contains $x$ precisely when all $k$ chosen sets are among the $m$ that contain it, and there are $(\binom{m}{k})$ such choices. So $x$ is counted $(\binom{m}{k})$ times in $S_{k}$ (zero times once $k > m$ ), and its net count is

(\binom{m}{1}) - (\binom{m}{2}) + (\binom{m}{3}) - \dots + (- 1)^{m - 1} (\binom{m}{m})

The previous lesson proved that the alternating sum of a row of Pascal's triangle vanishes, $(\binom{m}{0}) - (\binom{m}{1}) + (\binom{m}{2}) - \dots + (- 1)^{m} (\binom{m}{m}) = 0$ for $m \geq 1$ , because a nonempty set has as many subsets of even size as of odd size. The displayed sum is that row with its first term, $(\binom{m}{0}) = 1$ , removed and every sign flipped, so it equals $1$ . Every element of the union is counted exactly once, and one in none of the sets appears in no term.

Usually the sets live inside a universe $U$ of $N$ elements, each $A_{i}$ collecting the elements with some unwanted property, and the question is how many have none of the properties. Subtracting the union from $N$ flips every sign, giving the sieve form used in the rest of the lesson:

| U | - | A_{1} \cup \dots \cup A_{n} | = N - S_{1} + S_{2} - S_{3} + \dots + (- 1)^{n} S_{n}

Abraham de Moivre used the idea in his Doctrine of Chances of 1718. Its cost is that $n$ sets have $2^{n} - 1$ intersections, over a billion for thirty sets, so it is a practical method only when every intersection of $k$ sets has the same size, say $s_{k}$ . Then $S_{k} = (\binom{n}{k}) s_{k}$ and the formula collapses to one sum of $n + 1$ terms, as in each application below.

Onto functions

A function from a set $K$ to a set $T$ is onto if every element of $T$ is assigned to something. If $| K | = k$ and $| T | = n$ , the product rule gives $n^{k}$ functions in all. "Everything is hit" constrains the whole function at once, but its failure splits into simple pieces: the function misses some particular element.

So let $A_{i}$ be the functions that miss the $i$ th element of $T$ . A function missing $j$ given elements sends all of $K$ into the other $n - j$ , which can be done in $(n - j)^{k}$ ways whichever $j$ were chosen. The intersections are uniform, and the number of onto functions is

\sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) (n - j)^{k} = n^{k} - (\binom{n}{1}) (n - 1)^{k} + (\binom{n}{2}) (n - 2)^{k} - \dots

Two quick checks: with $k = 2$ and $n = 3$ nothing is onto, and the formula gives $9 - 12 + 3 - 0 = 0$ ; with $k = n = 3$ onto means bijection, and it gives $27 - 24 + 3 = 6 = 3!$ .

Example. Five different tasks are shared among three people so that everyone gets at least one. In how many ways?

An allocation is a function from tasks to people, and "everyone gets at least one" means onto. The count is $3^{5} - 3 \times 2^{5} + 3 \times 1^{5} - 0 = 243 - 96 + 3 = 150$ .

Now you. Six students are assigned to four different projects, each project needing at least one student. How many assignments are there?

Answer

Count onto functions from students to projects: $4^{6} - 4 \times 3^{6} + 6 \times 2^{6} - 4 \times 1^{6} + 0 = 4096 - 2916 + 384 - 4 = 1560$ .

Derangements and the hat check problem

At a party, $n$ guests leave their hats at the door, and the attendant, having lost the tickets, hands them back at random. What is the chance that nobody gets their own hat? Pierre Rémond de Montmort posed the question in 1708 as a card game called treize.

Handing back the hats is a permutation of the guests, one of $n!$ . A permutation that sends nothing to itself is a derangement, and $D_{n}$ is the number of derangements of $n$ elements. Let $A_{i}$ be the permutations that give guest $i$ their own hat. Fixing $j$ given guests leaves the other $n - j$ hats to be arranged freely, in $(n - j)!$ ways, so $S_{j} = (\binom{n}{j}) (n - j)! = \frac{n!}{j!}$ and the sieve gives

D_{n} = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(- 1)^{n}}{n!})

Example. Five guests. How many ways are there to return the hats so that nobody gets their own, and what is the probability?

The terms are $120 / j!$ for $j = 0$ to $5$ with alternating signs, so $D_{5} = 120 - 120 + 60 - 20 + 5 - 1 = 44$ , and the probability is $44 / 120 \approx 0.3667$ . Listing all $120$ permutations by computer finds the same $44$ .

Now you. Six guests. What is the probability that exactly two of them get their own hats back?

Answer

Choose the two lucky guests in $(\binom{6}{2}) = 15$ ways; the other four must form a derangement, and $D_{4} = 24 - 24 + 12 - 4 + 1 = 9$ . So $135$ of the $720$ permutations qualify, a probability of $135 / 720 = 0.1875$ .

The probability that nobody gets their own hat is $D_{n} / n!$ , the bracket in the formula, and its values are strange.

$n$	$D_{n}$	$D_{n} / n!$
2	1	0.500000
3	2	0.333333
4	9	0.375000
5	44	0.366667
6	265	0.368056
7	1854	0.367857
8	14833	0.367882
10	1334961	0.367879

The answer barely depends on $n$ : eight guests or a thousand agree to four decimal places. The bracket is the start of the series $e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \dots$ at $x = - 1$ , so it converges to $1 / e \approx 0.367879$ . It converges fast, because in an alternating series with shrinking terms, stopping early is wrong by less than the first term left out, here $1 / (n + 1)!$ . Multiplying by $n!$ , $D_{n}$ is within $1 / (n + 1)$ of $n! / e$ , so $D_{n}$ is $n! / e$ rounded to the nearest integer: $40320 / e \approx 14832.9$ , and $D_{8} = 14833$ .

Euler's totient

For a positive integer $n$ , Euler's totient $φ (n)$ counts the integers from $1$ to $n$ that share no factor with $n$ except $1$ . So $φ (12) = 4$ , counting $1$ , $5$ , $7$ and $11$ , and $φ (p) = p - 1$ for a prime $p$ . Euler introduced it in 1763, and it drives a later lesson's generalisation of Fermat's little theorem and with it the RSA cryptosystem.

An integer shares a factor greater than $1$ with $n$ exactly when some prime divisor of $n$ divides it. So let $p_{1}, \dots, p_{r}$ be the distinct primes dividing $n$ , and $A_{i}$ the multiples of $p_{i}$ from $1$ to $n$ . A number lies in several of these sets exactly when it is divisible by the product of those primes, and since that product divides $n$ , its multiples up to $n$ number exactly $n$ divided by it. Subtract $n / p$ for each prime, add back $n / (p q)$ for each pair of primes, subtract $n / (p q r)$ for each triple, and so on. The alternating sum factorises:

φ (n) = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{r}})

To see why, expand the product as the previous lesson expanded $(x + y)^{n}$ , choosing $1$ or $- 1 / p_{i}$ from each bracket. Each set of primes arises once, as the brackets that supplied $- 1 / p_{i}$ , with sign $+$ for an even number of primes and $-$ for an odd number. That is the sieve, term for term.

Take $360 = 2^{3} \times 3^{2} \times 5$ . The sieve reads $360 - (180 + 120 + 72) + (60 + 36 + 24) - 12 = 96$ , and the product reads $360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 96$ . For $1000 = 2^{3} \times 5^{3}$ , $φ (1000) = 1000 \times \frac{1}{2} \times \frac{4}{5} = 400$ . Only which primes divide $n$ matters, not how often, and a computer check of every number confirms both.

Counts built from smaller counts

The three applications share a shape. Each negated a condition on the whole object (every person busy, nobody with their own hat, no prime shared) into simple failures, one per person, guest or prime, whose intersections depended only on how many failures were demanded. That uniformity is what to look for.

The derangement numbers $1, 2, 9, 44, 265, 1854$ hide something else: $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ , so that $265 = 5 \times (44 + 9)$ . Guest $1$ gets some guest $i$ 's hat, in $n - 1$ ways. If guest $i$ gets hat $1$ back, the other $n - 2$ guests form a derangement, in $D_{n - 2}$ ways. If not, treat hat $1$ as guest $i$ 's forbidden hat, and the $n - 1$ guests other than guest $1$ form a derangement, in $D_{n - 1}$ ways.

That description needs no alternating sum: it defines each count through smaller versions of itself. Such descriptions are recurrences, and the next lesson is about setting them up and solving them.