7.01k–7.01m - Inclusion-exclusion and derangements

7.01k–7.01m - Inclusion-exclusion and derangements

Count a union without counting overlaps twice, extending inclusion-exclusion from two sets to three or more. Then count small derangements directly: arrangements in which every object is away from its own position, including questions that prescribe an exact number of correctly placed objects.

Inclusion-exclusion for two sets

Four labelled letters are put into four correspondingly labelled envelopes, one letter per envelope. How many arrangements put every letter in a wrong envelope? “All arrangements minus the ones with a correct letter” sounds promising, but an arrangement with two correct letters belongs to two forbidden groups. We first need a reliable way to correct overlapping counts.

If 88 pupils study a language and 77 study music, with 33 doing both, adding 8+78+7 counts those three pupils twice. The union therefore has 8+7−3=128+7-3=12 pupils. Subtract the overlap once, leaving each person counted once.

You already know

A∪BA\cup B means membership of either set, including both; A∩BA\cap B means membership of both. n(A)n(A) is the size of a finite set. A complement is taken within a stated universal set.

The same correction works whether the elements are people, integers, or arrangements satisfying different conditions.

Two-set inclusion-exclusion

For finite sets AA and BB:

n(A∪B)=n(A)+n(B)−n(A∩B)n(A\cup B)=n(A)+n(B)-n(A\cap B)

This is the two-set case of the three-set formula supplied in the booklet, obtained by taking the third set to be empty.

Not in the formula booklet: learn it.

For divisibility conditions, the intersection consists of multiples of the least common multiple. For example, multiples of both 44 and 66 are multiples of 1212, rather than of 2424. The number of multiples of dd from 11 to NN is ⌊N/d⌋\lfloor N/d\rfloor, where the floor means rounding down; this counting result is not separately printed in the booklet.

Worked example 1: multiples of either divisor

Question. Determine how many integers in {1,2,…,80}\{1,2,\ldots,80\} are divisible by 33 or 55. Hence find how many are divisible by neither.

Plan. Count the two sets and their intersection, then subtract the union from the universal set.

n(A)=⌊80/3⌋=26multiples of 3n(B)=80/5=16multiples of 5n(A∩B)=⌊80/15⌋=5multiples of bothn(A∪B)=26+16−5=37correct the overlapn((A∪B)′)=80−37=43take the complement\begin{aligned} n(A)&=\lfloor80/3\rfloor=26 &&\text{multiples of }3\\ n(B)&=80/5=16 &&\text{multiples of }5\\ n(A\cap B)&=\lfloor80/15\rfloor=5 &&\text{multiples of both}\\ n(A\cup B)&=26+16-5=37 &&\text{correct the overlap}\\ n\big((A\cup B)'\big)&=80-37=43 &&\text{take the complement} \end{aligned}

Why this step? A multiple of 1515 has been included in both initial counts; subtracting its second occurrence leaves it in the union once.

Answer. 3737 integers are divisible by 33 or 55, and 4343 are divisible by neither.

Check. The disjoint regions have sizes 2121, 55, 1111 and 4343, totalling 8080.

The next example changes only the upper limit. Keep the same divisors and overlap rule, but recalculate every count.

Worked example 2: a different upper limit

Question. Determine how many integers in {1,2,…,100}\{1,2,\ldots,100\} are divisible by 33 or 55, and how many are divisible by neither.

Plan. Use the same sets within the new universe.

n(A∪B)=⌊100/3⌋+⌊100/5⌋−⌊100/15⌋=33+20−6=47integer counts of multiplesneither=100−47=53exclude the union\begin{aligned} n(A\cup B)&=\lfloor100/3\rfloor+\lfloor100/5\rfloor-\lfloor100/15\rfloor\\ &=33+20-6=47 &&\text{integer counts of multiples}\\ \text{neither}&=100-47=53 &&\text{exclude the union} \end{aligned}

Why this step? 100/3100/3 is not itself a count of integers: only the 3333 completed multiples fit below or at 100100.

Answer. 4747 are divisible by at least one of the divisors; 5353 by neither.

Check. 47+53=10047+53=100, and the union is at least as large as either individual set.

The words “or” and “neither” lead to different final operations.

Watch out

“Divisible by neither 33 nor 55” means outside the union. Subtracting the intersection from the total instead would leave integers divisible by exactly one of the two divisors, which are forbidden by “neither”.

Write counts of actual elements, not probabilities, when the question asks “how many”.

Three or more overlapping sets

With three sets, subtracting all pairwise intersections removes elements in all three sets too often; they must be added back.

An element in A∩B∩CA\cap B\cap C is counted three times in n(A)+n(B)+n(C)n(A)+n(B)+n(C). It then occurs in each of the three pairwise intersections, so subtracting those leaves it counted zero times. Adding the triple intersection restores its one required occurrence. An element in exactly two sets is counted twice and subtracted once; an element in exactly one set is counted once throughout.

Three-set inclusion-exclusion

For finite sets AA, BB and CC:

n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(A∩C)−n(B∩C)+n(A∩B∩C)\begin{aligned} n(A\cup B\cup C)={}&n(A)+n(B)+n(C)\\ &-n(A\cap B)-n(A\cap C)-n(B\cap C)\\ &+n(A\cap B\cap C) \end{aligned}

In the formula booklet.

Pairwise intersections include the triple intersection. If you are given n(A∩B)n(A\cap B), do not silently treat it as “in AA and BB only”.

[DIAGRAM: asset_name: Three-set overlaps counted once; asset_slug: h245_7_01_three_sets; caption: Among the integers from 1 to 120, the three divisibility sets have seven disjoint regions totalling 88, leaving 32 outside; description: Three overlapping circles labelled A multiples of 2, B multiples of 3 and C multiples of 5. The A-only region is labelled 32, B-only 16, C-only 8; pairwise-only regions AB, AC, BC are labelled 16, 8, 4 respectively; the central triple region is labelled 4. The rectangle outside the circles is labelled 32. A lower counting line reads 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88]
Among the integers from 1 to 120, the three divisibility sets have seven disjoint regions totalling 88, leaving 32 outside

The numbers in the picture are region counts; the pairwise intersection sizes used in the formula also include the centre.

Worked example 3: three divisibility conditions

Question. Use inclusion-exclusion to determine how many integers in {1,2,…,120}\{1,2,\ldots,120\} are divisible by 22, 33 or 55.

Plan. Count each divisor, each pair's least common multiple and the triple's least common multiple.

individual counts=60,40,24divisors 2,3,5pairwise counts=20,12,8divisors 6,10,15triple count=4divisor 30union count=60+40+24−20−12−8+4=88inclusion-exclusion\begin{aligned} \text{individual counts}&=60,40,24 &&\text{divisors }2,3,5\\ \text{pairwise counts}&=20,12,8 &&\text{divisors }6,10,15\\ \text{triple count}&=4 &&\text{divisor }30\\ \text{union count}&=60+40+24-20-12-8+4\\ &=88 &&\text{inclusion-exclusion} \end{aligned}

Why this step? The four multiples of 3030 were included in all three initial sets and all three subtracted intersections; the final addition is essential.

Answer. 8888 integers.

Check. In each consecutive block of 3030 integers, 2222 are divisible by at least one of 2,3,52,3,5. Four such blocks give 4×22=884\times22=88.

The next example changes only the upper limit, so every set and intersection has the same definition.

Worked example 4: a second three-set count

Question. Use inclusion-exclusion to determine how many integers in {1,2,…,150}\{1,2,\ldots,150\} are divisible by 22, 33 or 55.

Plan. Recalculate all seven terms using the upper limit 150150.

union count=75+50+30−25−15−10+5=110three singles, three pairs, one triple\begin{aligned} \text{union count}&=75+50+30-25-15-10+5\\ &=110 &&\text{three singles, three pairs, one triple} \end{aligned}

Why this step? A three-set formula needs all three pairwise terms, not just the intersection of the first two sets followed by an extra single-set count.

Answer. 110110 integers.

Check. Five complete blocks of 3030 give 5×22=1105\times22=110, consistent with the first example.

For four sets, the same correction continues: add singles, subtract all six pairwise intersections, add all four triple intersections, and subtract the intersection of all four. For more sets, continue alternating signs. An element belonging to exactly kk sets must end with total coefficient 11; this explains the repeated corrections. The general extension is not printed in the booklet; reconstruct it from this alternating pattern.

Watch out

Do not omit the final triple intersection. For an element in all three sets, 3−3=03-3=0, so the element would vanish from a union to which it certainly belongs. The correct coefficient is 3−3+1=13-3+1=1.

A direct substitution into the supplied formula gives a cleaner final method than a collection of unlabelled partial sums.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account