Math 2.0

Combinatorics Theorem

Rule of sum

Builds on Cardinality of a finite set

Statement

Let AA and BB be finite sets with A∩B=∅A \cap B = \varnothing. Then A∪BA \cup B is finite and ∣A∪B∣=∣A∣+∣B∣|A \cup B| = |A| + |B|.

More generally, let A1,…,AkA_1, \dots, A_k be finite sets that are pairwise disjoint. Then ∣A1∪⋯∪Ak∣=∣A1∣+⋯+∣Ak∣|A_1 \cup \dots \cup A_k| = |A_1| + \dots + |A_k|.

Remarks

For the disjoint union A⊔BA \sqcup B of two arbitrary finite sets, the same formula ∣A⊔B∣=∣A∣+∣B∣|A \sqcup B| = |A| + |B| holds. If AA and BB are not disjoint, the formula fails. The inclusion-exclusion formula for two sets gives the correct count.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Cardinality of a finite set, definition, no evidence levelCardinality of a fini…definitionRule of sum, statement, no evidence levelRule of sumstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Cardinality of a finite set definition
  2. Rule of sum statement

Where this leads

4 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Addition_principle, lead section
About this page
Tag0EE2V3CHFK
URIm2://0EE2V3CHFK
Aliasesaddition-principle, sum-rule
Kindstatement, theorem
WritingW0 stub
MSC05A05
StatusThis copy of the site has no build data. Run m2 status 0EE2V3CHFK.
UsesCardinality of a finite set
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by