§2 Counting Principles

Counting problems become easier when we describe the objects as sets and then find their cardinalities. The main question is always the same: what choices build one valid object, and can any object be 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

The product principle, also called the multiplication principle, applies when an object is built through a sequence of choices. If the first choice has $m$ options and the second has $n$ options, then the pair of choices has

$$m\cdot n$$

possible outcomes. The same idea extends to any finite number of steps: multiply the number of options available at each step.

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\}.$$

A Canadian postal code has the pattern

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

There are three letter positions and three digit positions. Since the six choices are independent and repetition is allowed, the number of possible codes 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 round character is the digit zero, not the letter O.

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 construct a subset $X\subseteq A$, make one choice for 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|.$$

Nothing is counted twice because the sets do not overlap. More generally, the cardinalities of any finite collection of pairwise-disjoint sets can be added.

Example: usernames of length 6, 7, or 8

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

$$|C|=26, \qquad |L|=26, \qquad |D|=10,$$

where $C$, $L$, and $D$ are the three character sets. They are disjoint, so there are

$$26+26+10=62$$

allowed characters.

Let $S_n$ be the set of valid strings of length $n$. Repetition is allowed, so 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$. The complement principle counts the elements of $B$ that are not in $A$:

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

This follows from the disjoint decomposition

$$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|.$$

Rearranging produces 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. Let $A\subseteq B$ be the set of usernames containing no digits.

There are 62 allowed alphanumeric characters in total, but a username with no digits may use only the 52 uppercase and lowercase letters. Therefore,

$$|B|=62^6+62^7+62^8$$

and

$$|A|=52^6+52^7+52^8.$$

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

The sum principle cannot be applied directly when $A$ and $B$ overlap. In $|A|+|B|$, every element of $A\cap B$ is counted once as part of $A$ and again as part of $B$.

The inclusion–exclusion principle corrects this double count:

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

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

We can also derive the formula by splitting the union into three disjoint regions:

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

Their cardinalities add:

$$\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}$$

First add the three individual cardinalities. This overcounts every pairwise overlap, so subtract all three pairwise intersections. An element in all three sets was then added three times and subtracted three times, leaving it uncounted; add the triple intersection once.

The same alternating pattern continues for more sets:

1. add all one-set cardinalities;
2. subtract all pairwise intersections;
3. add all triple intersections;
4. subtract all four-set intersections;
5. continue alternating signs.

For four sets $A$, $B$, $C$, and $D$, this means adding the four individual sizes, subtracting all six pairwise intersections, adding all four triple intersections, and subtracting $|A\cap B\cap C\cap D|$.

Example: integers with none of three properties

How many integers from 1 through 1000 are neither perfect squares, nor perfect cubes, nor multiples 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}$$

Thus, $A$ is the set of perfect squares, $B$ the set of perfect cubes, and $C$ the set of multiples of 7.

The floor function $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$. It lets us count the possible integer bases:

$$|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.$$

We want the integers in none of the three sets, which form the complement of this union in $U$:

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