Interactive combinatorics
Permutations, combinations, Pascal's triangle, the binomial theorem and stars and bars are one sentence wearing five hats. Probability on a finite set is that same counting, divided.
The unifying ideaDescribe an object by a sequence of independent choices, multiply the choices, then divide by the number of ways the same object was built twice.
The two rules
Disjoint cases add; independent stages multiply. The word or signals a sum, the word and signals a product. Every formula below is these two rules plus a correction for having counted something twice.
|A ∪ B| = |A| + |B| when A ∩ B = ∅ · n₁n₂⋯nk for staged choicesThe product rule counts procedures, not objects. If every object arises from exactly d procedures, divide by d. That division is where C(n,k) comes from.
Order matters
n choices, then n−1, then n−2. Write it as the product, not as a factorial quotient: P(9,3) = 9·8·7 = 504 is faster and safer than 9!/6!.
Order does not
Each unordered k-set was counted once for every one of its k! orderings, the same number for every set, so the division is exact rather than approximate.
Double counting
Pascal's rule, the hockey stick, Vandermonde and the sum of squares all have the same proof: find a set, count it two ways, conclude the counts are equal. It is shorter and more illuminating than manipulating factorials.
The binomial theorem
Expanding (x+y)n means choosing x or y from each of n brackets. A term is xn−kyk exactly when you chose y from k of the brackets, and there are C(n,k) ways to do that.
(x + y)n = Σ C(n,k) xn−k ykStars and bars
Draw n objects as stars and cut the row with r−1 bars. Every arrangement is one solution of x₁ + ⋯ + xr = n, so the answer is C(n+r−1, r−1).
From counting to probability
On a finite sample space with equally likely outcomes, P(A) = |A| / |S|. The five-card poker hands are a pure counting exercise whose nine categories sum exactly to C(52,5) = 2,598,960, which is the check that the case split was disjoint and exhaustive.
Once outcomes stop being equally likely you need the axioms; once you want an average you need expectation. The counting never goes away.
Expectation
Write X as a sum of indicator variables, one per thing that could happen, and use E[Σ Xᵢ] = Σ E[Xᵢ]. No independence is required, which is why it solves problems whose distributions are hopeless.
The distributions
Binomial counts successes in n trials; geometric waits for the first; negative binomial for the r-th; hypergeometric drops replacement; Poisson is the rare-event limit. Each PMF sums to 1 by an identity from the counting half.
The mistakes that actually get made
The print edition
The PDF covers the same ground at length: the counting rules, permutations and combinations, Pascal identities, the binomial and multinomial theorems, stars and bars, inclusion–exclusion and derangements, bijections and Catalan numbers, then probability from the axioms through Bayes, expectation, variance, the named distributions and the classic problems. It closes with a formula spread, a decision guide and twenty-four problems with full solutions. Every numerical answer was verified against an exact computation before typesetting.