Inclusion-exclusion principle

For finite sets

A_{1}, \dots, A_{n}

, the cardinality of their union is

∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{\emptyset \neq = J \subseteq {1, \dots, n}} (- 1)^{∣ J ∣ + 1} ⋂_{j \in J} A_{j} .

(1)

Add the individual cardinalities, subtract pairwise intersection counts, add triple intersection counts, and continue alternating. This is useful whenever one object can satisfy several conditions: a search result can match several filters, or a permutation can have several forbidden fixed points.

Among the integers from 1 to 30, let

A

contain the multiples of 2 and

B

the multiples of 3. Then

∣ A ∣ = 15

∣ B ∣ = 10

, and

∣ A \cap B ∣ = 5

, because their common multiples are the multiples of 6. The naive sum

25

counts those five twice; the correct union size is $15 + 10 - 5 = 20$ . The regions contain ten in

A

alone, five in both, five in

B

alone, and ten in neither.

Figure 1.
Subtracting overlap counts each selected integer once; a third divisibility condition requires adding the triple overlap back
. **Details**.

Add a third set

C

containing the multiples of 5. Its size is 6; the three pairwise intersections have sizes

5, 3, 2

; and the triple intersection contains only 30. The inclusion-exclusion principle gives $15 + 10 + 6 - 5 - 3 - 2 + 1 = 22$ integers divisible by at least one of 2, 3, and 5.

The alternating corrections have a local explanation. An object belonging to exactly

r \geq 1

of the sets is counted

(1 r) - (2 r) + \dots + (- 1)^{r + 1} (r r) = 1

times, by the binomial theorem applied to

(1 - 1)^{r}

. An object in none contributes zero. Thus overlapping descriptions are repaired without requiring the sets themselves to be disjoint. For probability, the same calculation applies to event probabilities in place of cardinalities, giving the inclusion-exclusion principle for probabilities.

Table of contents

Inclusion-exclusion principle for probabilities ( $P (A \cup B) = P (A) + P (B) - P (A \cap B)$ )

 0  0

For a finite family of events, the probability of their union is the alternating sum of their intersection probabilities, with the same pattern as the inclusion-exclusion principle. Expand the indicator function of the union and apply linearity of expectation; this does not require independent events.

Weighted inclusion-exclusion principle ( $\sum_{x \in / ⋃_{i} A_{i}} f (x) = \sum_{S \subseteq {1, \dots, m}} (- 1)^{∣ S ∣} \sum_{x \in ⋂_{i \in S} A_{i}} f (x)$ )

 0  0

For finite subsets

A_{i}

of a finite ambient set

X

, the indicator function of their complement is

\prod_{i} (1 - 1_{A_{i}})

. Expanding this finite product and summing it against any weight

f : X \to R

proves the weighted formula. The empty intersection is

X

. Negative weights are allowed; finiteness removes every convergence issue.

Inclusion-exclusion for exact block occupancy ( $\sum_{r \geq 1} (- 1)^{r - 1} (r N) (q m)^{r} (K - r q ( N - r ) m)$ )

 0  0

Suppose

N

disjoint blocks each have

m

elements. The number of

K

-element subsets having exactly

q > 0

elements in at least one block is the displayed sum, with

1 \leq r \leq min (N, ⌊ K / q ⌋)

and invalid binomial coefficients interpreted as zero. For a specified set of

r

blocks, choose

q

elements in each and all remaining elements outside those blocks; inclusion-exclusion then counts the union of the exact-occupancy events. Excluding the rest of each specified block is essential.

// Target: algebra.bigb

Cyclic difference constraints ( $\sum_{j} c_{j} = 0$ )

 0  0

Let

f

take values in the additive cyclic group

Z / n Z

on a cycle with

n

vertices. A constraint on edge

j

prescribes

f (j) - f (j - 1) = c_{j}

. Any proper selection of

k < n

edges leaves disjoint paths, hence

n - k

free initial values and

n^{n - k}

solutions. The full cycle has

n

solutions if

\sum_{j} c_{j} = 0

and none otherwise. Combining these intersection counts with the inclusion-exclusion principle gives

# {f : f (j) - f (j - 1) \neq = c_{j} for every j} = (n - 1)^{n} + (- 1)^{n} (F - 1),

(1)

where

F

n

or zero according to the full-cycle consistency condition. This is a useful example in which every proper collection of local constraints is independent, but the full collection has one global obstruction.

Bonferroni inequalities

 0  0

Truncating the inclusion-exclusion principle after an odd number of terms gives an upper bound, and truncating after an even number gives a lower bound. In particular,

P (⋃_{i} A_{i}) \geq \sum_{i} P (A_{i}) - \sum_{i < j} P (A_{i} \cap A_{j}) .

(1)

Jordan-Bonferroni exact-occurrence inequalities ( $T_{2 s + 1} \leq Pr (N = k) \leq T_{2 s}$ )

 0  0

For the number

N

of occurring events, write

S_{j} = E (j N)

and

T_{m} = \sum_{r = 0}^{m} (- 1)^{r} (k k + r) S_{k + r}

. Then odd truncations bound

Pr (N = k)

below and even truncations above. For each integer

N > k

, the truncated binomial sum equals

(- 1)^{m} (k N) (m N - k - 1)

when

m < N - k

, and is zero otherwise. Its sign proves the bounds on taking expectations. This is the exact-count version of the Bonferroni inequalities.

codex/inclusion-exclusion

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Inclusion–exclusion principle by

Wikipedia Bot  1

 View more

The Inclusion-Exclusion Principle is a fundamental concept in combinatorics and probability theory that is used to calculate the size of the union of multiple sets when there is overlap between the sets. It provides a systematic way to count the number of elements in the union of several sets by including the sizes of the individual sets and then systematically excluding the sizes of their intersections to avoid over-counting.

 Read the full article

  See all articles in the same topic Create my own version

Inclusion-exclusion principle

Inclusion-exclusion principle for probabilities ( $P (A \cup B) = P (A) + P (B) - P (A \cap B)$ )

Weighted inclusion-exclusion principle ( $\sum_{x \in / ⋃_{i} A_{i}} f (x) = \sum_{S \subseteq {1, \dots, m}} (- 1)^{∣ S ∣} \sum_{x \in ⋂_{i \in S} A_{i}} f (x)$ )

Inclusion-exclusion for exact block occupancy ( $\sum_{r \geq 1} (- 1)^{r - 1} (r N) (q m)^{r} (K - r q ( N - r ) m)$ )

Cyclic difference constraints ( $\sum_{j} c_{j} = 0$ )

Bonferroni inequalities

Jordan-Bonferroni exact-occurrence inequalities ( $T_{2 s + 1} \leq Pr (N = k) \leq T_{2 s}$ )

 Ancestors (4)

 Incoming links (75)

 Synonyms (1)

 Discussion (0) New discussion

 Articles by others on the same topic (1)

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion