Rule of sum

In combinatorics, the rule of sum or addition principle is a basic counting principle. Stated simply, it is the idea that if we have a ways of doing something and b 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.

More formally, the rule of sum is a fact about set theory. 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 $S_{{1}},S_{{2}},...,S_{{n}}$ are pairwise disjoint sets, then we have:

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

Simple example

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

Thus there are 3+2=5 possible shops the woman could end up shopping at today.

Inclusion-exclusion principle

Main article: Inclusion-exclusion principle

The inclusion-exclusion principle 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

{\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\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|.\end{aligned}}

Rule of sum

Simple example

Inclusion-exclusion principle

See also