Rule of sum

5+0=5 illustrated with collections of dots.

In combinatorics, the rule of sum^{[1][2][verification needed]} or addition principle^[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 A + B ways to choose one of the actions.^[1][3]

3+2=5 illustrated with shapes.^[relevant?]

More formally, the rule of sum is a fact about set theory.^{[verification needed]} It states that sum of the sizes of a finite collection of pairwise disjoint sets is the size of the union of these sets. That is, if ${\displaystyle S_{1},S_{2},...,S_{n}}$ are pairwise disjoint sets, then we have:^[3][4]

$${\displaystyle |S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|.}$$

Simple example[]

A person has decided to shop at one store today, either in the north part of town or the south part of town. If they visit the north part of town, they will shop at either a mall, a furniture store, or a jewelry store (3 ways). If they visit the south part of town then they will shop at either a clothing store or a shoe store (2 ways).

Thus there are 3+2=5 possible shops the person could end up shopping at today.^{[citation needed]}

Inclusion–exclusion principle[]

A series of Venn diagrams illustrating the principle of inclusion-exclusion.

The inclusion–exclusion principle (also known as the sieve principle^[3]) can be thought of as a generalization of the rule of sum in that it too enumerates the number of elements in the union of some sets (but does not require the sets to be disjoint). It states that if A₁, ..., A_n are finite sets, then^[3]

$${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}$$

References[]

See also[]

• Combinatorial principle
• Rule of product
• Inclusion–exclusion principle

This combinatorics-related article is a stub. You can help Wikipedia by .

• v
• t