Most counting problems come down to two questions: how many choices are there, and does anything get counted more than once?

Cardinality

The cardinality of a finite set $A$, written $|A|$, is the number of elements in $A$. For example,

$$A=\{2,5,7\} \qquad\Longrightarrow\qquad |A|=3.$$

The empty set has no elements, while a set containing the empty set has one element:

$$|\varnothing|=0 \qquad\text{but}\qquad |\{\varnothing\}|=1.$$

The vertical bars in $|A|$ mean cardinality here, not absolute value.

The product principle

Use the product principle, also called the multiplication principle, when you make several choices in order. If the first choice has $m$ options and, after every possible first choice, the second choice has the same $n$ options, there are

$$m\cdot n$$

possible combinations. For more steps, multiply the number of options at each step when each count stays the same for every earlier valid choice. If the number of continuations depends on what was chosen earlier, split into cases or add the branch counts instead.

For finite sets $A$ and $B$, this gives the cardinality of their Cartesian product:

$$|A\times B|=|A|\,|B|.$$

If $A=\{2,5,7\}$ and $B=\{1,2\}$, then

$$|A\times B|=3\cdot2=6.$$

Example: Canadian postal codes

Let $L$ be the set of 26 uppercase letters and $D$ the set of 10 digits:

$$L=\{\mathrm A,\mathrm B,\ldots,\mathrm Z\}, \qquad D=\{0,1,\ldots,9\}.$$

In a simplified format model, a Canadian postal code has the pattern

$$L\,D\,L\;D\,L\,D.$$

This model ignores the real restrictions on which letters may appear in particular positions. There are three letter positions and three digit positions. Each position can be chosen independently, and characters can repeat, so the number of strings matching the simplified pattern is

$$26\cdot10\cdot26\cdot10\cdot26\cdot10 =26^3\cdot10^3 =17{,}576{,}000.$$

For example, Santa's postal code H0H 0H0 follows this pattern. Each 0 is the digit zero, not the letter O. The calculation counts format-matching strings, not actual assignable postal codes.

Why a power set has size $2^n$

The power set $\mathcal P(A)$ contains every subset of $A$. Suppose

$$A=\{a_1,a_2,\ldots,a_n\}.$$

To choose a subset $X\subseteq A$, decide what to do with each element $a_i$:

• include $a_i$ in $X$; or
• leave $a_i$ out of $X$.

There are two choices for each of the $n$ elements, so the product principle gives

$$|\mathcal P(A)|=2^n=2^{|A|}.$$

This also works for the empty set:

$$|\mathcal P(\varnothing)|=2^0=1,$$

because $\mathcal P(\varnothing)=\{\varnothing\}$.

The sum principle

Two sets are disjoint when they have no elements in common:

$$A\cap B=\varnothing.$$

For disjoint finite sets, the sum principle, also called the addition principle, says

$$|A\cup B|=|A|+|B|.$$

Because the sets do not overlap, nothing is counted twice. The same rule works for any number of pairwise-disjoint finite sets.

Example: usernames of length 6, 7, or 8

Suppose a username may contain uppercase letters, lowercase letters, and digits. There are

$$26+26+10=62$$

allowed characters in total.

Let $S_n$ be the set of valid usernames of length $n$. Since characters can repeat, the product principle gives

$$|S_6|=62^6, \qquad |S_7|=62^7, \qquad |S_8|=62^8.$$

A string cannot have two different lengths, so $S_6$, $S_7$, and $S_8$ are disjoint. The sum principle therefore gives

$$|S_6\cup S_7\cup S_8| =62^6+62^7+62^8 =221{,}918{,}520{,}426{,}688.$$

The complement principle

Suppose $A\subseteq B$ and $B$ is finite. The complement principle counts the elements that are in $B$ but not in $A$:

$$|B\setminus A|=|B|-|A|.$$

This works because $B$ splits into two parts that do not overlap:

$$B=A\cup(B\setminus A).$$

The sets $A$ and $B\setminus A$ do not overlap, so the sum principle gives

$$|B|=|A|+|B\setminus A|.$$

Solving this equation for $|B\setminus A|$ gives the complement principle.

Example: usernames containing at least one digit

Let $B$ be the set of all valid usernames of length 6, 7, or 8, and let $A\subseteq B$ contain the usernames with no digits. A username in $B$ can use any of the 62 characters, while a username in $A$ can use only the 52 letters. Therefore,

$$\begin{aligned} |B|&=62^6+62^7+62^8,\\ |A|&=52^6+52^7+52^8. \end{aligned}$$

The set $B\setminus A$ contains exactly the usernames with at least one digit. By the complement principle,

$$\begin{aligned} |B\setminus A| &=(62^6+62^7+62^8)-(52^6+52^7+52^8)\\ &=167{,}410{,}949{,}583{,}040. \end{aligned}$$

Inclusion–exclusion for two sets

If finite sets $A$ and $B$ overlap, simply adding $|A|+|B|$ counts every element of $A\cap B$ twice: once in $A$ and once in $B$.

The inclusion–exclusion principle fixes this by subtracting the overlap once:

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

1. Count A2. Add B3. The overlap was counted twice4. Subtract one copy of A ∩ B

Another way to see the formula is to split the union into three regions that do not overlap:

$$A\setminus B, \qquad A\cap B, \qquad B\setminus A.$$

Since the regions do not overlap, we can add their sizes:

$$\begin{aligned} |A\cup B| &=|A\setminus B|+|A\cap B|+|B\setminus A|\\ &=(|A|-|A\cap B|)+|A\cap B|+(|B|-|A\cap B|)\\ &=|A|+|B|-|A\cap B|. \end{aligned}$$

Example: bit strings

A bit is either $0$ or $1$. How many bit strings of length 8 start with $1$ or end with $00$?

Let

$$A=\{\text{length-8 bit strings that start with }1\}$$

and

$$B=\{\text{length-8 bit strings that end with }00\}.$$

For $A$, the first bit is fixed and the remaining seven bits are free, so

$$|A|=2^7.$$

For $B$, the last two bits are fixed and the remaining six are free, so

$$|B|=2^6.$$

A string in $A\cap B$ starts with $1$ and ends with $00$. Five positions remain free, so

$$|A\cap B|=2^5.$$

By inclusion–exclusion,

$$|A\cup B|=2^7+2^6-2^5=160.$$

Inclusion–exclusion for three or more sets

For three finite sets, inclusion–exclusion becomes

$$\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}$$

Start by adding the sizes of the three sets, then subtract the three pairwise overlaps. A point in all three sets was added three times and then subtracted three times, so it is missing from the count. Add the triple intersection once to put it back.

For finite sets $A_1,A_2,\ldots,A_n$, write out the pattern like this:

$$\begin{aligned} |A_1\cup A_2\cup\cdots\cup A_n| ={}&|A_1|+|A_2|+\cdots+|A_n|\\ &-\bigl(|A_1\cap A_2|+|A_1\cap A_3|+\cdots+|A_{n-1}\cap A_n|\bigr)\\ &+\bigl(|A_1\cap A_2\cap A_3|+\cdots+|A_{n-2}\cap A_{n-1}\cap A_n|\bigr)\\ &-\text{all quadruple intersections}\\ &+\text{all quintuple intersections}-\cdots\\ &+(-1)^{n+1}|A_1\cap A_2\cap\cdots\cap A_n|. \end{aligned}$$

The signs alternate as the intersections get larger:

1. add the size of each set;
2. subtract every pairwise intersection;
3. add every triple intersection;
4. subtract every quadruple intersection;
5. add every quintuple intersection, and keep alternating.

For four sets, this becomes: add the four set sizes, subtract the six pairwise intersections, add the four triple intersections, then subtract the four-way intersection.

Example: integers with none of three properties

How many integers from 1 through 1000 have none of these properties: perfect square, perfect cube, or multiple of 7?

Let

$$U=\{1,2,\ldots,1000\},$$

and define

$$\begin{aligned} A&=\{n\in U\mid n=k^2\text{ for some integer }k\},\\ B&=\{n\in U\mid n=k^3\text{ for some integer }k\},\\ C&=\{n\in U\mid 7\text{ divides }n\}. \end{aligned}$$

Here, $A$ contains the perfect squares, $B$ contains the perfect cubes, and $C$ contains the multiples of 7.

The floor function $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$. We use it here because the square and cube roots must be whole numbers:

$$|A|=\left\lfloor\sqrt{1000}\right\rfloor=31, \qquad |B|=\left\lfloor\sqrt[3]{1000}\right\rfloor=10,$$

and

$$|C|=\left\lfloor\frac{1000}{7}\right\rfloor=142.$$

Now count the intersections:

• A number that is both a square and a cube is a sixth power, so $$|A\cap B|=\left\lfloor\sqrt[6]{1000}\right\rfloor=3.$$
• A square divisible by 7 has a square root divisible by 7. Among $1,2,\ldots,31$, there are four multiples of 7, so $$|A\cap C|=4.$$
• A cube divisible by 7 has a cube root divisible by 7. Among $1,2,\ldots,10$, only $7$ qualifies, so $$|B\cap C|=1.$$
• A number in all three sets would be a sixth power whose base is divisible by 7. The smallest is $7^6=117{,}649>1000$, so $$|A\cap B\cap C|=0.$$

Inclusion–exclusion gives

$$|A\cup B\cup C| =31+10+142-3-4-1+0 =175.$$

The question asks for the numbers outside all three sets, so subtract the union from $U$:

$$\begin{aligned} |U\setminus(A\cup B\cup C)| &=|U|-|A\cup B\cup C|\\ &=1000-175\\ &=825. \end{aligned}$$