Answers · The mathematics underneath

Why do I have to subtract the overlap when I add two groups together?

In shortBecause anything in both groups gets counted twice, so you take one copy back out to leave it counted once.

You subtract the overlap because everything in both groups has been counted twice: once when the first group was counted and once when the second was. Subtracting the overlap once leaves every member of the combined group counted exactly once.

Take the whole numbers from 1 to 100 and ask how many are divisible by 3 or by 5. The multiples of 3 up to 100 number 33, since 99 divided by 3 is 33. The multiples of 5 number 20, since 100 divided by 5 is 20. Adding the two sizes gives 53. That number is larger than the correct answer because some numbers have been entered into the sum twice.

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

The overlap is the set of numbers divisible by both 3 and 5. A number divisible by both is divisible by 15, their least common multiple. The multiples of 15 up to 100 are 15, 30, 45, 60, 75 and 90: six numbers, since 15 times 6 is 90 and 15 times 7 is 105, which is above 100. Each of those six was counted in the 33 and counted again in the 20. Subtracting the overlap once gives 33 + 20 - 6 = 47.

FIG 1Multiples of three or five up to one hundred, done properly

step	step	reasoning	count
1	multiples of three	99 divided by 3	33
2	multiples of five	100 divided by 5	20
3	naive sum	add the two counts	53
4	the overlap	multiples of 15 up to 100	6
5	subtract it once	33 + 20 - 6	47
6	check by listing	count n from 1 to 100 with n mod 3 = 0 or n mod 5 = 0	47

6 steps

The overlap of the multiples of three and the multiples of five is the multiples of fifteen, not some smaller set guessed from the two divisors. The last line checks the formula against a direct count.

Why the natural guess fails

The natural guess is that adding the two sizes gives the size of the combined group. It does not. It gives the total number of membership notices: one for each element of the first group and one for each element of the second. An element in both receives two notices but should receive one. Subtracting the overlap once is exactly the repair. This is not division, because the shared element has not been counted in several orders; it has been counted in two different groups.

A direct check separates the right arithmetic from the wrong arithmetic. Writing a loop over 1 to 100 and counting the numbers where n mod 3 is 0 or n mod 5 is 0 gives 47. The formula gives 47 and the naive sum gives 53. The check is cheap because the range is small, and the same test on a small case is evidence for the general formula, since a correct formula must agree at every size.

For any two groups, the sum records each shared member twice and the union wants each shared member once. One copy must go, so one copy of the overlap is subtracted. If the overlap has six members, the sum has six extra entries above the union. The subtraction removes exactly those extras.

Three groups

With three groups, adding the three sizes counts an element in exactly two groups twice, and an element in all three groups three times. Subtracting each pairwise overlap once fixes the exactly-two elements, but it subtracts the triple element three times as well. That triple element has had three additions and three subtractions, netting zero, so it must be added back once. This is why the signs alternate.

FIG 2Adding groups that overlap

: the number of things in group A
: the things in A or B or both
: the things in both A and B
: subtracted once, because the overlap was added twice
: added back because three additions and three subtractions left it at zero

For two groups the repair is one subtraction. For three groups the pairwise overlaps are subtracted and the triple overlap is added back once.

The signs are not arbitrary. An element in one group contributes 1. An element in two groups contributes 1 + 1 - 1 = 1. An element in three groups contributes 1 + 1 + 1 - 1 - 1 - 1 + 1 = 1. Each correction changes the count of an element by exactly the amount needed to bring its contribution back to one.

When plain addition is already right

If the two groups are disjoint, the overlap is empty, its size is zero, and the subtraction changes nothing. Plain addition is then correct. If the groups can share members, the overlap must be found. For divisibility conditions, the overlap is the condition given by the least common multiple of the divisors. The overlap of divisibility by 3 and divisibility by 5 is divisibility by 15, which is why the six multiples of 15 were the ones counted twice.

Worth keeping

Adding the sizes of two groups counts every shared member twice, so the shared part is subtracted once.
If the groups share nothing, plain addition is already correct.
For three groups, pairwise overlaps are subtracted and the triple overlap is added back once.

Where this goes next

This question is one step of Counting Without Listing, a course that works through its subject from the beginning. The page that teaches this part of it is Counting the Same Thing Twice, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course