Counting and probability

Probability starts by modelling an experiment.

1. Sample spaces and events (Def. 1.1), the axioms (Def. 1.2) and what follows from them (Prop. 1.3).
2. When outcomes are equally likely (Prop. 1.4), probability becomes counting: the multiplication principle, permutations and combinations (Prop. 1.5, Prop. 1.6, Technique 1.7).
3. Inclusion–exclusion (Theorem 1.8) handles "at least one" questions.

The sample space $\Omega$ is the set of possible outcomes of an experiment; an event is a subset $A\subseteq\Omega$, and "$A$ happens" means the outcome lies in $A$. Set operations describe combined events: $A\cup B$ ($A$ or $B$), $A\cap B$ ($A$ and $B$), $A^c$ (not $A$). $A, B$ are mutually exclusive (disjoint) if $A\cap B = \emptyset$. Example: two dice: $\Omega = \{1, \dots, 6\}^2$ has $36$ outcomes; "sum is $7$" is $\{(1, 6), (2, 5), \dots, (6, 1)\}$.

A probability assigns to each event $A$ a number $\mathbb{P}(A)$ with: (A1) $\mathbb{P}(A)\ge0$; (A2) $\mathbb{P}(\Omega) = 1$; (A3) if $A_1, A_2, \dots$ are pairwise disjoint then $\mathbb{P}\big(\bigcup_iA_i\big) = \sum_i\mathbb{P}(A_i)$ (countable additivity).

For all events: (i) $\mathbb{P}(A^c) = 1 - \mathbb{P}(A)$, so $\mathbb{P}(\emptyset) = 0$; (ii) if $A\subseteq B$ then $\mathbb{P}(A)\le\mathbb{P}(B)$, so $0\le\mathbb{P}(A)\le1$; (iii) $\mathbb{P}(A\cup B) = \mathbb{P}(A) + \mathbb{P}(B) - \mathbb{P}(A\cap B)$; (iv) $\mathbb{P}(A\cup B)\le\mathbb{P}(A) + \mathbb{P}(B)$ (union bound).

If $\Omega$ is finite and all outcomes are equally likely, then $\mathbb{P}(A) = \frac{|A|}{|\Omega|}$.

If a choice is made in $k$ stages with $n_1, n_2, \dots, n_k$ options at each stage (whatever was chosen before), there are $n_1n_2\cdots n_k$ outcomes. Hence:

• ordered selections of $r$ from $n$ with repetition: $n^r$;
• ordered selections without repetition (permutations): $n(n - 1)\cdots(n - r + 1) = \frac{n!}{(n - r)!}$; arrangements of all $n$: $n!$.

The number of unordered selections of $r$ objects from $n$ (without repetition) is $\binom nr = \frac{n!}{r!\,(n - r)!}$. The number of ways to split $n$ objects into groups of sizes $n_1, \dots, n_k$ is the multinomial coefficient $\frac{n!}{n_1!\cdots n_k!}$.

To find $\mathbb{P}(A) = \frac{|A|}{|\Omega|}$: choose a sample space of equally likely outcomes (usually unordered hands, or ordered sequences), and count $A$ in the same way. Use the complement for "at least one". Classic results: a 5-card hand has $\mathbb{P}(\text{exactly 2 aces}) = \frac{\binom42\binom{48}3}{\binom{52}5}$; the birthday problem: among $n$ people, $\mathbb{P}(\text{some shared birthday}) = 1 - \frac{365\cdot364\cdots(365 - n + 1)}{365^n}$, which exceeds $\frac12$ for $n = 23$.

Application (derangements): if $n$ letters are put randomly in $n$ envelopes, $\mathbb{P}(\text{no letter in the right envelope}) = \sum_{k=0}^n\frac{(-1)^k}{k!}\to\frac1e$.

• Does order matter? Is repetition allowed? Decide before counting.
• Count numerator and denominator in the same model.
• Avoid double counting: if you choose "a special one, then the rest", you may count each set several times.
• Sanity checks: the answer lies in $[0, 1]$; small cases by listing; complements and symmetry.