第 4 章 · 22 分钟

Overlap: inclusion–exclusion and its price

Why alternating signs cancel the duplicates exactly.

概念地图

Inclusion–exclusion

With overlap, alternate signs so every element nets exactly one.

深色为本章概念，浅色为其他章

陪练模式

不想只是读？让它带你走一遍。

导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。

对话只存在本机

Locus01

延伸阅读

de Montmort · early eighteenth century · the matching problem

Posed 'how many arrangements leave no card in its own place' in a card game and solved it by alternating addition and subtraction. He argued against enumerating case by case; the cost is that the method was then a trick for that problem with no general form.

Foundational

Sylvester and the later formalisation · nineteenth century

Wrote the alternating sum as a general formula over any finite family of sets and proved it by induction. This made it a theorem; the cost is that the number of terms grows exponentially with the number of sets, which limits its practical reach.

Turn

Bonferroni inequalities · early twentieth century

Noted that the partial sums of the expansion alternately over- and under-shoot the true value, so truncating gives bounds. A practical revision of 'you must compute every term', and this chapter's second mechanism.

Revision

Brualdi · the chapters on inclusion–exclusion

The subject of this course. The textbook gives the formula and the derangement application; this chapter says the alternating signs are not a trick but the solution of 'every element must net exactly one'.

Subject of this course

机制02

Balance by net multiplicity

Chapter 1 said the addition principle's only condition is disjointness. What if the sets overlap? The answer is not a new rule but the same bijection: make every element net exactly one in the final count. The alternating signs of inclusion–exclusion are decided entirely by that requirement — they were not contrived, they were solved for.

机制An overlapping union, through alternately adding and subtracting the intersections, gives every element a net count of exactly one.

可迁移性测试

Move it to deduplicating across channels: one user may sit in all three lists, so adding directly double-counts. Add the three lists, subtract the pairwise overlaps, add back the triple. The isomorphism breaks in that 'the same person' in real lists has to be judged by an identifier and can be judged wrongly, while equality of set elements is determinate.

机制03

Truncation gives bounds

The number of terms grows exponentially with the number of sets, so computing them all is often out of reach. You may instead compute only the first few: stopping after an odd-order term gives an upper bound, after an even one a lower bound. These Bonferroni inequalities turn an exact formula into a stoppable approximation that knows which side it stopped on. It is one of the rare places in this course where not finishing still leaves you certain of something.

机制An exponential exact expansion, through being truncated at some term, yields a bound whose direction is known.

可迁移性测试

Move it to summing an alternating series: the partial sums straddle the true value, so each one is a bound rather than merely an approximation. The isomorphism breaks in that a series' bounds tighten as terms are added, while inclusion–exclusion's need not, depending on how the intersection sizes fall away.

Derivation04

The alternating signs are solved for, not contrived

What is being proved is the inclusion–exclusion formula, with the emphasis on why the signs must alternate.

The sets A1​,…,An​ are finite
A hypothesis. On infinite sets adding and subtracting sizes of unions is meaningless.
Consider any element x belonging to exactly k of the sets, k≥1
A hypothesis. Elements with k=0 are not in the union and take no part in the count.
Target: every x is counted net exactly once
A hypothesis, and the design requirement of the whole formula; the signs follow from it uniquely.

推导 · 0 / 4

Worked derivation05

Derangements: the standard application

n

letters go randomly into

n

envelopes. What is the probability that none is in the right envelope?

Let

A_{i}

be 'letter

i

is right' and count the arrangements where no

A_{i}

occurs.

裂缝06

The boundary of this chapter's claims

争议地形07

本书主张

Inclusion–exclusion is the general tool for overlapping counts: write the formula, compute term by term, get the exact answer.

另一种看法

The approximation and probabilistic line holds that once the number of sets grows, the terms are exponentially many with comparable magnitudes and opposite signs, so the computation is numerically fragile; in practice one should prefer truncated bounds or randomised estimates over an exact expansion.

分歧扎在

The disagreement is rooted in whether exactness or computability comes first, not in the mathematics. Both accept the formula; at issue is the scale at which it is still worth using.

什么证据能裁决

What would settle it is numerical experiment: across a series of instances with growing numbers of sets, compare the error and running time of the full expansion against truncated bounds or sampled estimates. If beyond some scale the full expansion's error, through floating-point cancellation, exceeds the truncated bound's, the practical claim holds.

The evidence points to 'it depends on how the intersection sizes fall away': with fast decay the full expansion is excellent, with slow decay truncated bounds are steadier. What is missing is a criterion for judging the decay in advance — current practice finds out by computing.

Boundary and counterexample08

The 'balance by net multiplicity' commitment as a testable specification

The modelling commitment under test: membership in a real deduplication is determinate and repeatable, so the net count inclusion–exclusion gives is the true deduplicated result.

Hypothesis dropped: membership judgement is determinate and repeatable
The prerequisite for inclusion–exclusion to correspond to reality; with unstable judgement the intersections have no determinate size.
The counterexample: two runs of the same deduplication rule giving different intersection sizes (identifying a person by email one time and by device the next)
There is then no determinate intersection to substitute into the formula.
The observable: the intersection sizes obtained by repeated runs of the same rule
It must be the same rule on the same raw data, run again.
What counts against it: the difference between runs exceeds a pre-registered threshold
The threshold is fixed in advance on the recording noise of the data.
Pre-registered failure condition: differences above threshold, or the inclusion–exclusion result differing from an independent full deduplication beyond the threshold
Either counts as the commitment failing.

推导 · 0 / 3

接口09

Which slot it hangs on

挂在哪个槽位The conclusion you already hold is probably 'just subtract the duplicates' — a judgement about deduplication. This chapter goes at its complete form.

Does this chapter (a) replace 'subtract the duplicates', or (b) constrain it: after subtracting the pairwise overlaps you must add the triples back?

慢变量Register two slow variables: how many of your deduplications involve three or more sources, and in how many of those the triple overlap was added back. Look at the second first.

小结10

本章小结

01With overlap you do not switch rules; you return to 'every element nets exactly one'.

02The alternating signs are the unique solution of that requirement, given by the binomial theorem, not contrived.

03With two sets it looks like subtracting duplicates; with three or more it does not.

04The Bonferroni inequalities let the expansion stop early, and you know which side of the truth you stopped on.

05The practical prerequisite is computable intersections; without it the formula holds and offers no way in.

提取练习 · 合上书，先自己答一遍。

?Is 'the alternating signs give a net count of one' (a) solved for via the binomial theorem or (b) a modelling commitment about reality?

?With many sets, the difficulty with inclusion–exclusion is mainly (a) that the formula fails or (b) that the intersections cannot be computed?

Forced choice11

B · Identify the tag

'The alternating sign

(- 1)^{j + 1}

gives every element a net count of one' — what kind of step is that?

二选一

Forced choice12

C · Locate the crack

In which situation does this framework give a confident and wrong answer?

二选一

读到这里，把它记为已读。