Counting

• Before we can compute probabilities, we need to count outcomes. If you want to know the chance of drawing a winning hand in poker, you first need to know how many possible hands exist and how many of those are winners. Counting is the machinery that makes probability precise.

• The simplest counting principle is the multiplication rule. If one decision has $m$ options and a second independent decision has $n$ options, the total number of combined outcomes is $m \times n$.

• Picture getting dressed in the morning. You have 3 shirts and 4 pants. Each shirt can pair with every pant, giving you $3 \times 4 = 12$ possible outfits.

• The multiplication rule extends to any number of choices. If you also have 2 pairs of shoes, the total outfits become $3 \times 4 \times 2 = 24$. Each new independent choice multiplies the count.

• The addition rule handles "or" scenarios. If event A can happen in $m$ ways and event B can happen in $n$ ways, and they cannot both happen at the same time (mutually exclusive), the total number of ways is $m + n$.

• Suppose you can travel from city X to city Y by car (3 routes) or by train (2 routes). You cannot take both simultaneously, so the total options are $3 + 2 = 5$.

• When events overlap, you need to subtract the double-counted outcomes. If $A$ and $B$ can co-occur, the count is $|A \cup B| = |A| + |B| - |A \cap B|$. This is the inclusion-exclusion principle, and it will reappear when we discuss probability addition rules.

• The factorial of a non-negative integer $n$ is the product of all positive integers up to $n$:

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

• Think of the factorial as answering: in how many ways can you arrange $n$ distinct objects in a line? Three books on a shelf can be arranged in $3! = 3 \times 2 \times 1 = 6$ ways. By convention, $0! = 1$.

• Factorials grow extremely fast. $10! = 3{,}628{,}800$ and $20!$ is already over $2.4 \times 10^{18}$. This explosive growth is why brute-force search becomes impractical in combinatorial problems.

• A permutation is an ordered arrangement of objects. When you pick $r$ items from $n$ distinct objects and the order matters, the number of permutations is:

$$P(n, r) = \frac{n!}{(n - r)!}$$

• Imagine picking a president, vice president, and treasurer from a club of 10 people. The first role has 10 candidates, the second has 9 remaining, the third has 8. That gives $P(10, 3) = 10 \times 9 \times 8 = 720$. The formula confirms this: $\frac{10!}{7!} = 720$.

• A combination is an unordered selection. When you pick $r$ items from $n$ and the order does not matter, we divide out the redundant orderings:

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!}$$

• The notation $\binom{n}{r}$ is read "n choose r." The key insight is that every combination corresponds to $r!$ permutations (the $r$ chosen items can be rearranged in $r!$ ways), so we divide the permutation count by $r!$.

• Example: from a group of 10 people, how many ways can you form a committee of 3? Order does not matter (there is no president or vice president, just members), so we use combinations:

$$\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$$

• The same 10 people produce 720 permutations but only 120 combinations, because each group of 3 has $3! = 6$ internal orderings.

• Combinations are central to probability. The binomial coefficient $\binom{n}{r}$ counts the number of ways to get exactly $r$ successes in $n$ trials, which is the heart of the binomial distribution (covered in file 03).

• Let us work through a classic committee problem that combines multiple counting ideas.

• Problem: A club has 8 men and 6 women. How many ways can you form a committee of 5 that includes exactly 3 men and 2 women?

• Step 1: Choose 3 men from 8.

$$\binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$

• Step 2: Choose 2 women from 6.

$$\binom{6}{2} = \frac{6!}{2! \cdot 4!} = \frac{6 \times 5}{2 \times 1} = 15$$

• Step 3: Apply the multiplication rule. Each selection of men can pair with each selection of women:

$$56 \times 15 = 840 \text{ committees}$$

• This pattern, breaking a complex counting problem into independent sub-choices and multiplying, is the standard approach in combinatorics.

• There are also permutations with repetition. When items can repeat, choosing $r$ items from $n$ types gives $n^r$ outcomes. A 4-digit PIN using digits 0-9 has $10^4 = 10{,}000$ possibilities. Each position has 10 options, and the multiplication rule handles the rest.

• Combinations with repetition (also called "stars and bars") count how many ways to choose $r$ items from $n$ types when repeats are allowed and order does not matter:

$$\binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!(n - 1)!}$$

• Example: choosing 3 scoops from 4 ice cream flavours (repeats allowed) gives $\binom{4 + 3 - 1}{3} = \binom{6}{3} = 20$ options.

• To summarise the counting toolkit:

• Every probability calculation involving equally likely outcomes uses the formula $P(\text{event}) = \frac{\text{favourable outcomes}}{\text{total outcomes}}$. Counting gives us both numbers. With this foundation, we are ready to formalise probability itself in the next file.

Coding Tasks (use CoLab or notebook)

1. Compute $P(10, 3)$ and $\binom{10}{3}$ using both the factorial formula and direct computation. Verify that the permutation count is always $r!$ times the combination count.

import jax.numpy as jnp
from math import factorial

n, r = 10, 3

perm = factorial(n) // factorial(n - r)
comb = factorial(n) // (factorial(r) * factorial(n - r))

print(f"P({n},{r}) = {perm}")
print(f"C({n},{r}) = {comb}")
print(f"P / C = {perm // comb} (should equal {r}! = {factorial(r)})")

2. Solve the committee problem (3 men from 8, 2 women from 6) programmatically and verify by enumerating all valid committees.

from itertools import combinations
from math import factorial

def comb_count(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

# Formula approach
men_ways = comb_count(8, 3)
women_ways = comb_count(6, 2)
print(f"Formula: {men_ways} × {women_ways} = {men_ways * women_ways}")

# Enumeration approach
men = [f"M{i}" for i in range(1, 9)]
women = [f"W{i}" for i in range(1, 7)]
count = sum(1 for _ in combinations(men, 3) for _ in combinations(women, 2))
print(f"Enumeration: {count}")

3. Count how many 4-character passwords can be made from 26 lowercase letters (with repetition allowed). Then count how many contain no repeated letters.

from math import factorial

n = 26
r = 4

with_rep = n ** r
without_rep = factorial(n) // factorial(n - r)

print(f"With repetition:    {with_rep:>10,}")
print(f"Without repetition: {without_rep:>10,}")
print(f"Fraction with repeats: {1 - without_rep/with_rep:.2%}")

4. Simulate the birthday problem: in a group of $k$ people, what is the probability that at least two share a birthday? Plot the probability for $k = 1$ to $60$ and find where it crosses 50%.

import jax
import jax.numpy as jnp
import matplotlib.pyplot as plt

def birthday_prob_exact(k):
    """Probability of at least one shared birthday in group of k."""
    p_no_match = 1.0
    for i in range(k):
        p_no_match *= (365 - i) / 365
    return 1 - p_no_match

ks = list(range(1, 61))
probs = [birthday_prob_exact(k) for k in ks]

plt.figure(figsize=(8, 4))
plt.plot(ks, probs, color="#3498db", linewidth=2)
plt.axhline(y=0.5, color="#e74c3c", linestyle="--", alpha=0.7, label="50%")
cross = next(k for k, p in zip(ks, probs) if p >= 0.5)
plt.axvline(x=cross, color="#e74c3c", linestyle="--", alpha=0.7)
plt.xlabel("Group size (k)")
plt.ylabel("P(at least one shared birthday)")
plt.title(f"Birthday Problem (crosses 50% at k={cross})")
plt.legend()
plt.grid(alpha=0.3)
plt.show()