Counting and Combinatorics

Under an equally-likely-outcomes model, $\mathbb{P}(A) = |A|/|\Omega|$ — computing a probability reduces entirely to counting. That was trivial for the 8-outcome coin-toss sample space in Sample Spaces, Events, and the Probability Axioms, but the sample spaces that matter in practice — the number of ways to allocate $k$ traders to $n$ desks, the number of distinct portfolios of $k$ names out of a universe of $n$, the number of orderings in a matching-engine priority queue — are astronomically large and cannot be enumerated by hand. This note builds the counting toolkit: the multiplication (counting) principle, permutations, combinations (the binomial coefficient), and partitions (the multinomial coefficient). Every later probability calculation involving finite, equally-likely outcomes routes through one of these four counts.

Learning objectives. By the end of this note you should be able to: