DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Combinatorics

Inclusion-Exclusion

To count a union of overlapping sets, add the sets, subtract every pairwise overlap, add back the triple overlap — until each region of the Venn diagram is counted exactly once.

Step 1 of 16

Speed

Which of the numbers 1 to 30 are divisible by 2, 3 or 5? Call the three sets A, B and C. Each circle is a set; the badge in every region will show how many times that region has been counted so far.

|A \cup B \cup C| = \textcolor{#475569}{ |A|} \textcolor{#475569}{+ |B|} \textcolor{#475569}{+ |C|} \textcolor{#475569}{- |A \cap B|} \textcolor{#475569}{- |A \cap C|} \textcolor{#475569}{- |B \cap C|} \textcolor{#475569}{+ |A \cap B \cap C|} \\[4pt] \textcolor{#475569}{ 15} \textcolor{#475569}{+ 10} \textcolor{#475569}{+ 6} \textcolor{#475569}{- 5} \textcolor{#475569}{- 3} \textcolor{#475569}{- 2} \textcolor{#475569}{+ 1} \;\to\; \text{running total } \mathbf{0} \ne 22

Numbers 1 to N30

A: divisible by2B: divisible by3C: divisible by5

Each badge is a region's tally: how many of the switched-on terms contain it. The total is right exactly when every non-empty region reads ×1.

Inclusion-Exclusion

To count a union of overlapping sets, add the sets, subtract every pairwise overlap, add back the triple overlap — until each region of the Venn diagram is counted exactly once.

Step 1 of 16

Speed

Which of the numbers 1 to 30 are divisible by 2, 3 or 5? Call the three sets A, B and C. Each circle is a set; the badge in every region will show how many times that region has been counted so far.

|A \cup B \cup C| = \textcolor{#475569}{ |A|} \textcolor{#475569}{+ |B|} \textcolor{#475569}{+ |C|} \textcolor{#475569}{- |A \cap B|} \textcolor{#475569}{- |A \cap C|} \textcolor{#475569}{- |B \cap C|} \textcolor{#475569}{+ |A \cap B \cap C|} \\[4pt] \textcolor{#475569}{ 15} \textcolor{#475569}{+ 10} \textcolor{#475569}{+ 6} \textcolor{#475569}{- 5} \textcolor{#475569}{- 3} \textcolor{#475569}{- 2} \textcolor{#475569}{+ 1} \;\to\; \text{running total } \mathbf{0} \ne 22

Numbers 1 to N30

A: divisible by2B: divisible by3C: divisible by5

Each badge is a region's tally: how many of the switched-on terms contain it. The total is right exactly when every non-empty region reads ×1.

DSAverse

Inclusion-Exclusion

See also

Inclusion-Exclusion

See also