# 4.1: Fundamental Counting Rules – Counting

Jump to:

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

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

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