Addition principle

In combinatorics, the addition principle^[1][2] or rule of sum^[3][4] 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.^[3][1] In mathematical terms, the addition principle states that, for disjoint sets A and B, we have ${\displaystyle |A\cup B|=|A|+|B|}$,^[2] provided that the intersection of the sets is without any elements.

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

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:^[1][2]$${\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.^[2]