Addition principle

In combinatorics, the addition principle or rule of sum is a basic counting principle. Stated simply, it is the intuitive idea that if we have A number of ways of doing something and B number of ways of doing another thing and we can not do both at the same time, then there are ${\displaystyle A+B}$ ways to choose one of the actions. In mathematical terms, the addition principle states that, for disjoint sets A and B, we have ${\displaystyle |A\cup B|=|A|+|B|}$, provided that the intersection of the sets is without any elements.

The rule of sum is a fact about set theory, as can be seen with the previously mentioned equation for the union of disjoint sets A and B being equal to |A| + |B|.

The addition principle can be extended to several sets. If ${\displaystyle S_{1},S_{2},\ldots ,S_{n}}$ are pairwise disjoint sets, then we have:$${\displaystyle |S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|.}$$This statement can be proven from the addition principle by induction on n.