Problem
COM-B2-M02-P017 Contribution of One Object
#17
★★★★☆ Level 4 of 5
Prove the general inclusion-exclusion formula by explaining the contribution of one object that belongs to exactly \(r\) of the sets \(A_1,\ldots,A_m\).
Its contribution is \(\binom r1-\binom r2+\binom r3-\cdots\).
In the formula for \(|A_1\cup\cdots\cup A_m|\), an object lying in exactly \(r\) sets is counted \(\binom r1\) times in the single sums, \(\binom r2\) times in pairwise intersections, and so on. Its total contribution is \(\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr\). This equals \(1-(1-1)^r=1\). Hence every object in the union is counted exactly once.
A conceptual, non-computational problem.