The inclusion-exclusion principle and Boole-Bonferroni inequalities

TWO SETS.

Consider a finite set `S` and two subsets `S1,S2` of `S`. These two sets partition `S` into four atoms, some of which may be empty. Let `Nii`, `Nio`, `Noi`, `Noo` denote the sizes of these atoms: let us write

• `Nii` for the number of elements in both `S1` and `S2`,
• `Nio` for the number of elements in `S1` and outside `S2`,
• `Noi` for the number of elements outside `S1` and in `S2`,
• `Noo` for the number of elements outside both `S1` and `S2`.
(Here, `i` is mnemonic for "in" and `o` is mnemonic for "out".) Furthermore, let us write
• `Nid` for the number of elements in `S1`,
• `Ndi` for the number of elements in `S2`,
• `Ndd` for the total number of elements in `S`.
(Here, `d` is mnemonic for "don't care".) By definition, we have
```   Nid = Nii + Nio
Ndi = Nii + Noi
Ndd = Nii + Nio + Noi + Noo;
```
it follows that
```   Noo  = Ndd - (Nii + Nio + Noi)
= Ndd - (Nid + Ndi) + Nii.
```
Identity
```   Noo  = Ndd - (Nid + Ndi) + Nii
```
is a special case of the inclusion-exclusion principle; inequalities
```   Noo <= Ndd
Noo >= Ndd - (Nid + Ndi)
```
a special case of the Boole-Bonferroni inequalities.

THREE SETS.

Consider a finite set `S` and three subsets `S1,S2,S3` of `S`. These three sets partition `S` into eight atoms (some of which may be empty). Let `Niii`, `Niio`, `Nioi`, `Nioo`, `Noii`, `Noio`, `Nooi`, `Nooo` denote the sizes of these atoms: let us write

• `Niii` for the number of elements in `S1`, in `S2`, and in `S3`,
• `Niio` for the number of elements in `S1`, in `S2`, and outside `S3`,
• `Nioi` for the number of elements in `S1`, outside `S2`, and in `S3`,
• `Nioo` for the number of elements in `S1`, outside `S2`, and outside `S3`,
• `Noii` for the number of elements outside `S1`, in `S2`, and in `S3`,
• `Noio` for the number of elements outside `S1`, in `S2`, and outside `S3`,
• `Nooi` for the number of elements outside `S1`, outside `S2`, and in `S3`,
• `Nooo` for the number of elements outside `S1`, outside `S2`, and outside `S3`.
Furthermore, let us write
• `Niid` for the number of elements in `S1` and in `S2`,
• `Nidi` for the number of elements in `S1` and in `S3`,
• `Ndii` for the number of elements in `S2` and in `S3`,
• `Nidd` for the number of elements in `S1`,
• `Ndid` for the number of elements in `S2`,
• `Nddi` for the number of elements in `S3`,
• `Nddd` for the total number of elements in `S`.
By definition, we have
```   Niid = Niii + Niio,
Nidi = Niii + Nioi,
Nidd = Niii + Niio + Nioi + Nioo,
Ndii = Niii + Noii,
Ndid = Niii + Niio + Noii + Noio,
Nddi = Niii + Nioi + Noii + Nooi,
Nddd = Niii + Niio + Nioi + Noii + Nioo + Noio + Nooi + Nooo;
```
it follows that
```   Nooo  = Nddd - (Niii + Niio + Nioi + Noii + Nioo + Noio + Nooi)
= Nddd - (Nidd + Ndid + Nddi) + (2Niii + Niio + Nioi + Noii)
= Nddd - (Nidd + Ndid + Nddi) + (Niid + Nidi + Ndii) - Niii.
```
Identity
```   Nooo  = Nddd - (Nidd + Ndid + Nddi) + (Niid + Nidi + Ndii) - Niii
```
is a special case of the inclusion-exclusion principle; inequalities
```   Nooo <= Nddd
Nooo >= Nddd - (Nidd + Ndid + Nddi)
Nooo <= Nddd - (Nidd + Ndid + Nddi) + (Niid + Nidi + Ndii)
```
are a special case of the Boole-Bonferroni inequalities.

FOUR SETS.

Consider a finite set `S` and four subsets `S1,S2,S3,S4` of `S`. In the notation suggested by the preceding two examples, we have

```   Noooo  = Ndddd
- (Niiii + Niiio + Niioi + Nioii + Noiii +
Niioo + Nioio + Niooi + Noiio + Noioi + Nooii +
Niooo + Noioo + Nooio + Noooi)
= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (3Niiii + 2Niiio + 2Niioi + 2Nioii + 2Noiii +
Niioo + Nioio + Niooi + Noiio + Noioi + Nooii)
= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (3Niiii + Niiio + Niioi + Nioii + Noiii)
= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (Niiio + Niioi + Nioii + Noiii) + Niiii.
```
Identity
```   Noooo  = Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (Niiio + Niioi + Nioii + Noiii) + Niiii
```
is a special case of the inclusion-exclusion principle; inequalities
```   Noooo <= Ndddd
Noooo >= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
Noooo <= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
Noooo >= Ndddd - (Niddd + Ndidd + Nddid + Ndddi)
+ (Niidd + Nidid + Niddi + Ndiid + Ndidi + Nddii)
- (Niiio + Niioi + Nioii + Noiii)
```
are a special case of the Boole-Bonferroni inequalities.

MANY SETS.

Consider a finite set `S` and `k` subsets `S1,S2,...,Sk` of `S`. With the notation suggested by the preceding examples, let `Tj` stand for the sum of all the terms `N**...*` whose subscript `**...*` consists of `j` symbols `i` and `k-j` symbols `d`. The inclusion-exclusion principle states that

```   Noo...o  = T0 - T1 + T2 - T3 + ... + (-1)kTk;
```
the Boole-Bonferroni inequalities assert that prefix-sums of the right-hand side alternate between upper and lower bounds on `Noo...o`:
```   Noo...o <= T0
Noo...o >= T0 - T1
Noo...o <= T0 - T1 + T2
Noo...o >= T0 - T1 + T2 - T3
```
and so on.