4.1: Fundamental Counting Rules – Counting

# 4.1: Fundamental Counting Rules – Counting

To begin, we will formalize two of the most basic rules in counting – the product rule and sum rule. We will then look at several examples that apply both of these rules.

## Product Rule

### Example: Number of Factors

How many factors does $1200$ have?

We could sit down and manually enumerate through all factors of 1200, one by one - 1, 2, 3, 4, 5, 6, … but that would take quite a bit of time. Instead, we will look at the prime factorization of 1200: $1200 = 2^4 \cdot 3 \cdot 5^2$.

We know each factor of 1200 will have some number of $2$s, some number of $3$s, and some number of $5$s. There are 5 options for the number of $2$s a factor could have: 0, 1, 2, 3 or 4 (meaning a factor of 1200 could either have a factor of $2^0$, or $2^1$, or $2^2$, or $2^3$, or $2^4$). Similarly, there are 2 options for the number of $3$s a factor could have (either 0 or 1) and 3 options for the number of $5$s (0, 1, or 2).

Since we’re making three successive choices, we take the product of the number of choices at each step, yielding

$\text{number of factors of } 1200 = (4 + 1) (1 + 1) (2 + 1) = 30$

In general, if we have $n = p_1^{e_1} \cdot p_2^{e_2} \cdot … \cdot p_k^{e_k}$, the following holds:

$\text{number of factors of } n = \prod_{i = 1}^k (e_i + 1) = (e_1 + 1) \cdot (e_2 + 1) \cdot ... \cdot (e_{k - 1} + 1) \cdot (e_k + 1)$

### Example: Cardinality of the Power Set

The power set $P(S)$ of a set $S$ is a set of all possible subsets of $S$. For example, if $S = {1, 2, 3}$, we have $P(S) = \{ \emptyset , \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}$.

If $S$ is a set such that $|S| = n$, what is $|P(S)|$?

When creating a subset of $S$, for each of the $n$ items in $S$, we have two options: either we include it in the subset, or do not include it in the subset. Since we have two options for each of the $n$ items, the total number of ways we can create a subset of $S$ is $2 \cdot 2 \cdot … \cdot 2 = 2^n$.