Skip to content

Counting

Counting is the prerequisite for computing probabilities -- you must know how many outcomes exist before you can assign likelihoods. This file covers the multiplication and addition rules, factorials, permutations, combinations, and the binomial coefficient -- combinatorial tools that underpin sampling, hashing, and probabilistic analysis in ML.

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

Tree diagram showing 3 shirts times 4 pants equals 12 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!\).

Side-by-side comparison: permutations count all orderings, combinations collapse identical groups

  • 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:

Scenario Formula
Ordered, no repetition (permutation) \(P(n,r) = \frac{n!}{(n-r)!}\)
Unordered, no repetition (combination) \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)
Ordered, with repetition \(n^r\)
Unordered, with repetition \(\binom{n+r-1}{r}\)
  • 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()