Counting and the Product Rule

Why Counting?

Many probability problems reduce to counting: determining how many outcomes lie in an event. If we can count the total number of equally likely outcomes and count how many satisfy our criterion, the probability is their ratio.

The Product Rule

Principle: If an experiment has $n_1$ possible outcomes, and for each of these, a second experiment has $n_2$ possible outcomes, then the combined experiment has $n_1 \times n_2$ possible outcomes.

More generally, for $r$ experiments:

$\text{Total outcomes} = n_1 \times n_2 \times \cdots \times n_r$

Why does this work? Each outcome of the first experiment branches into $n_2$ outcomes of the second, each of those branches into $n_3$ outcomes of the third, and so on. The total is the product.

Examples

Example 1: Rolling Two Dice

Each die has 6 outcomes. The pair of dice has $6 \times 6 = 36$ possible outcomes.

Example 2: Coin Flips

Three coin flips: each flip has 2 outcomes. Total: $2 \times 2 \times 2 = 8$ outcomes.

The sample space: $\{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT\}$

Example 3: Licence Plates

A licence plate has 3 letters followed by 3 digits. How many possible plates?

• Each letter position: 26 choices
• Each digit position: 10 choices
• Total: $26^3 \times 10^3 = 17{,}576{,}000$

Example 4: Hash Tables

A hash table has 100 buckets. Two strings are hashed independently. How many ways can they be stored?

Each string can go to any of 100 buckets. Total: $100 \times 100 = 10{,}000$ possible storage configurations.

Ordered vs Unordered

The product rule counts ordered outcomes: the sequence matters.

Example (ordered): Drawing two balls from an urn with replacement, recording the order. If we have 5 balls, there are $5 \times 5 = 25$ ordered pairs.

Example (unordered): If we only care about which two balls we get (not the order), we divide by 2! for each pair: $\frac{25 - 5}{2} + 5 = 15$ distinct unordered outcomes (the 5 pairs of the same ball, plus 20 ordered pairs reduced by a factor of 2).

The Pigeonhole Principle

Principle: If $n$ items are placed into $k$ boxes and $n > k$, at least one box contains at least $\lceil n/k \rceil$ items.

Corollary: If $n$ items are placed into $n-1$ boxes, at least one box contains at least 2 items.

Example: Hash Collisions

A hash table has 100 buckets. We hash 950 strings.

• Is it possible some bucket has no entries? Yes, the items might cluster.
• Is it guaranteed at least one bucket has at least 2 entries? Yes: $950 > 100$, so by pigeonhole, at least one bucket has at least $\lceil 950/100 \rceil = 10$ entries.
• Is it guaranteed at least one bucket has at least 11 entries? No: we could potentially distribute 950 items with 9 buckets having 10 items and the rest having fewer.

Counting with Restrictions

Sometimes we impose restrictions that reduce the number of valid outcomes.

Example: iPhone Passcodes

Old iPhone passcodes were 4 digits. If fingerprints appear on 3 digits (one digit used twice), how many distinct passcodes?

The passcode uses digits $\{a, b, c\}$ where one appears twice. We need to count sequences of length 4 using exactly these three digits.

Method: Choose which digit appears twice (3 choices). Then arrange 4 items where 2 are identical: $\frac{4!}{2!} = 12$ arrangements.

Total: $3 \times 12 = 36$.

If fingerprints on only 2 digits: one digit used twice, another used twice. Choose which two digits (from the visible 2): must be those 2. Arrange: $\frac{4!}{2! \cdot 2!} = 6$ arrangements.

The General Counting Principle

For a sequence of choices where the $i$th choice has $n_i$ options:

$\text{Total} = \prod_{i=1}^{r} n_i$

This assumes choices are independent: the options at each step do not depend on previous choices.

When choices depend on previous selections (sampling without replacement), each $n_i$ decreases.

Example: Drawing Without Replacement

Draw 3 cards from a standard 52-card deck without replacement.

• First card: 52 choices
• Second card: 51 choices
• Third card: 50 choices
• Total ordered draws: $52 \times 51 \times 50 = 132{,}600$

Summary

Concept	Formula
Product rule	$n_1 \times n_2 \times \cdots \times n_r$
Pigeonhole principle	$n$ items in $k$ boxes $\Rightarrow$ some box has $\geq \lceil n/k \rceil$
Ordered sampling with replacement	$n^r$ sequences of length $r$ from $n$ items
Ordered sampling without replacement	$n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}$