Maths for Algorithms: Counting & Probability

By the end of this lesson you will be able to count arrangements and choices without listing them out (permutations, combinations, Pascal's triangle), reason correctly about chance with dice, coins and disease tests (sample spaces, conditional probability, Bayes' theorem), use linearity of expectation — the single most powerful trick in algorithm analysis — to predict how many hires a random-order interview process makes, and understand exactly why shuffling an array the "obvious" way is wrong while Fisher–Yates is provably fair.

1. Counting: rule of sum & rule of product

These two rules are the foundation of every counting formula in this lesson. Getting "and" vs "or" right — multiply vs add — is the single most common source of counting mistakes.

In Dart: the two counting rules on real lists: Set union of disjoint piles for "or" (3 + 2 = 5), a nested for over both piles for "and" (3 × 2 = 6), and three groups multiplied (3·2·4 = 24).

Input size → what's feasible: group sizes up to ~10⁷ combinations can be enumerated; beyond that just multiply the sizes (a 64-bit int holds products up to 9.2·10¹⁸).

2. Permutations: arranging things in order

What if you only want to arrange k of the n people (say, who gets gold/silver/bronze out of 5 runners)? Same logic, but you stop after k seats: n × (n−1) × … × (n−k+1), which is n! / (n−k)!. This is called a k-permutation.

In Dart: n! as a loop, every ordering generated by recursion (the "fill seat 1, then arrange the rest" argument) and counted for n = 0…7, the k-permutation n!/(n−k)! as a product of k terms, and the gold/silver/bronze count P(5,3) = 60 by brute force.

Input size → what's feasible: listing all orderings only for n ≤ 8–9 (9! = 362,880); counting them with n! works up to n = 20 in a 64-bit int (native Dart; in JavaScript-compiled web builds int is a double and loses exactness above 2⁵³).

3. Combinations & Pascal's triangle

This gives the famous formula for "n choose k", written C(n,k) or ⁿCₖ:

In Dart: "n choose k" three ways: kPerm / k!, the factorial form n!/(k!(n−k)!), and by actually counting teams (every bitmask of n bits with exactly k ones is one team), plus symmetry and the "k! orderings per team" argument.

Input size → what's feasible: n ≤ 20 → factorials still fit a 64-bit int (21! overflows); n ≤ 60 → use the multiplicative form (Q6); beyond that → BigInt or work mod a prime.

Pascal's triangle is a beautifully simple way to build every C(n,k) using only addition: each entry is the sum of the two entries diagonally above it. Row n, position k is exactly C(n,k) — because when you choose k people from n, the last person is either IN (then choose the other k−1 from the remaining n−1: C(n−1,k−1) ways) or OUT (then choose all k from the remaining n−1: C(n−1,k) ways). This "either the last item is IN the group or it's OUT" split is Pascal's identity: C(n,k) = C(n−1,k−1) + C(n−1,k).

In Dart: Pascal's triangle built by addition only (nextRow): row n position k is C(n,k), Pascal's identity, the left-right symmetry and the row sum 2ⁿ are all checked for rows 1…30. Math notation and Dart both start the row index at 0 here, so no index shift is needed.

Input size → what's feasible: rows up to 60 fit a 64-bit int (C(60,30) ≈ 1.2·10¹⁷); a full table up to n = 2000 costs ≈ 2·10⁶ additions (use a modulus, Q12).

4. The binomial theorem, strings & subsets

Pascal's triangle isn't just a counting curiosity — the same numbers are the coefficients when you expand (x+y)ⁿ:

Setting x = y = 1 gives a nice special case: 2ⁿ = Σ C(n,k) — every row of Pascal's triangle sums to a power of 2. That's not a coincidence: it's also exactly the number of subsets of an n-element set, because every subset is decided by n independent yes/no choices ("is element i in the subset?") — a rule-of-product count of 2×2×…×2 (n times). Grouping subsets by their SIZE k gives C(n,k) subsets of size k, and summing over all sizes must give all 2ⁿ subsets.

A closely related idea: a string over an alphabet of size n and length k (e.g. a k-character password using n possible characters, with repeats allowed) has exactly n^k possibilities — rule of product applied k times, once per position.

In Dart: the binomial theorem expanded term by term and compared with (x+y)ⁿ for several (x, y, n); the subsets of a 5-set via bitmasks, counted by size (1,5,10,10,5,1) and in total 2⁵ = 32; and the strings count nᵏ by building all 3⁴ strings.

Input size → what's feasible: subsets by bitmask → n ≤ 25 (2²⁵ ≈ 3·10⁷ masks); strings over 62 symbols, length 8 = 2.2·10¹⁴ → count with ipow, never enumerate.

5. Sample space, events & the probability axioms

The probability axioms are almost embarrassingly simple, yet everything else is built from them: (1) probabilities are never negative, (2) the whole sample space has probability 1 (something always happens), (3) for outcomes that can't happen together (mutually exclusive), probabilities add. For a uniform sample space, Pr{event} = (number of outcomes in the event) / (total number of outcomes) — which is exactly why the counting techniques above (Sections 1–4) are the engine that powers probability calculations.

In Dart: the sample space of two dice as a list of records, events as predicates, Pr = count / 36, and the three axioms checked on it (non-negative, Pr{S} = 1, additive for the mutually exclusive events "sum = 7" and "sum = 11").

Input size → what's feasible: 36 outcomes → exact integer counts; counts stay integers so no rounding until the final division.

6. Complement, union & inclusion–exclusion

The complement of event A (written Ā, "not A") is everything in the sample space that ISN'T in A. Since S is split entirely between A and Ā, their probabilities must add to 1: Pr{Ā} = 1 − Pr{A}. This is often the easiest way to compute a probability — "at least one" questions are usually much easier to answer as "1 − none".

In Dart: "at least one six in 4 rolls" by enumerating all 6⁴ = 1296 outcomes (671 have a six, 625 do not) and by 1 − (5/6)⁴.

Input size → what's feasible: up to ~10⁷ outcomes can be enumerated; "1 − none" needs only a power, so it scales to any number of rolls.

For two events that CAN overlap, you can't just add their probabilities — that would double-count the overlap. The fix is inclusion–exclusion:

// Inclusion-exclusion for two events:
Pr(A union B) == Pr(A) + Pr(B) - Pr(A intersect B)

In Dart: A = "sum is even", B = "sum is above 7" on the 36 two-dice outcomes, built as Dart Sets: union, intersection and the identity |A ∪ B| = |A| + |B| − |A ∩ B|, plus the mutually exclusive special case.

Input size → what's feasible: sample space of 36 → enumerate and count; with 10⁶ outcomes you would still just count with sets (O(size)).

7. Conditional probability & independence

Pr(A given B) == Pr(A intersect B) / Pr(B)     // requires Pr(B) != 0

In Dart: conditioning as "shrink the sample space to B": the two-coin and two-dice examples computed by the definition Pr{A∩B}/Pr{B} and by dividing counts directly.

Input size → what's feasible: a sample space up to ~10⁷ outcomes can be enumerated in a second; for larger spaces use the counting formulas.

Two events are independent when knowing one happened tells you NOTHING about the other: Pr{A∩B} = Pr{A}·Pr{B}, equivalently Pr{A|B} = Pr{A}. A subtle trap: it's possible for three events to be pairwise independent (every PAIR multiplies correctly) while still not being mutually independent (the probability of all three together is wrong). Flip two fair coins and define A₁ = "first is heads", A₂ = "second is heads", A₃ = "the two coins differ". Every pair of these multiplies correctly (each pair has probability 1/4 = 1/2 × 1/2), but A₁, A₂ and A₃ can never ALL be true simultaneously (both heads means they can't differ) — so Pr{A₁∩A₂∩A₃} = 0, not the 1/8 that mutual independence would require.

In Dart: independence as Pr{A∩B} == Pr{A}·Pr{B}: the three coin events A₁, A₂, A₃ are independent in every pair (1/4 each) but the triple has probability 0, not 1/8; and "first die even" / "second die even" on 36 outcomes.

Input size → what's feasible: 4 outcomes (coins) and 36 outcomes (dice) → exact; the same test works on any finite space you can list.

8. Bayes' theorem: Monty Hall & the medical test

Pr(A given B) == Pr(A) * Pr(B given A) / Pr(B)

In Dart: Bayes' theorem derived on real events (A = "dice sum to 8", B = "first die is 6"): the two products Pr{A|B}·Pr{B} and Pr{B|A}·Pr{A} are both Pr{A∩B}, so dividing gives the theorem.

Input size → what's feasible: 36 outcomes → exact counts; probabilities are doubles, so compare with a tolerance.

The Monty Hall problem: there's a car behind one of 3 doors, goats behind the other two. You pick a door. The host — who KNOWS where the car is — opens a different door, always revealing a goat. Should you switch to the remaining door?

In Dart: Monty Hall three ways: all 9 (car, pick) cases (switching wins 6, staying 3), Bayes with the likelihoods 1/2, 1, 0, and a seeded 20,000-game simulation.

Input size → what's feasible: 9 exact cases; simulation error ≈ 0.47/√trials → 20,000 games give ±0.003.

Now a case where Bayes' theorem is genuinely needed: a disease affects 1% of a population. A test correctly detects it 99% of the time (sensitivity) when someone has it, and correctly comes back negative 95% of the time (specificity) when someone doesn't. If your test comes back POSITIVE, what's the chance you actually have the disease?

In Dart: the rare-disease test twice: with Bayes and the total-probability denominator (Pr{sick | positive} = 1/6), and by counting a town of 10,000 people (99 true alarms against 495 false ones).

Input size → what's feasible: exact with 4 numbers; the town is just integer arithmetic (use ~/ so nothing becomes a float).

9. Random variables, expectation & linearity

E[X] == sum over every possible value x of ( x * Pr(X == x) )

In Dart: E[X] = Σ x·Pr{X = x} as a loop over the faces (and over the 36 outcomes of two dice), including a value→count table.

Input size → what's feasible: finite sample spaces up to ~10⁷ outcomes are fine to enumerate; otherwise use linearity (next).

Here is the single most useful fact in this entire lesson for analysing algorithms:

In Dart: E[X+Y] = E[X]+E[Y] as a function e(f) averaging over all 36 outcomes: independent dice, a dependent Y (the running total), Y = X², and E[3X] = 3E[X] — no independence used anywhere.

Input size → what's feasible: 36 outcomes → exact (use a tolerance for double averages); the point is that you never need the joint distribution in practice.

10. Indicator random variables: hiring the best so far

In Dart: an indicator variable as a 0/1 list: E[X_A] equals Pr{A} for "the die shows 5 or 6" (1/3), and the number of sixes in 5 rolls (a sum of 5 indicators) averages 5·(1/6) over all 6⁵ = 7776 outcomes.

Input size → what's feasible: 7776 outcomes → exact enumeration; for 100 rolls you use linearity (100/6) instead of enumerating 6¹⁰⁰.

The always-hire-the-best-so-far problem: you interview n candidates one at a time, in a random order, always hiring whoever is the best so far (replacing your current hire). How many times do you expect to hire, total? Let X_i = 1 if candidate i is a "record" (better than everyone interviewed before them). Candidate i is a record exactly when the best of the first i candidates (a uniformly random subset in random order) happens to BE candidate i — which, by symmetry, happens with probability exactly 1/i. By linearity:

E[number of hires] == sum(i = 1..n) of Pr(candidate i is a record)
                    == sum(i = 1..n) of (1 / i)
                    == H(n)   // the n-th harmonic number

In Dart: E[hires] = Σ 1/i = Hₙ checked exactly: all 720 arrival orders of 6 candidates are generated, the number of hires is counted for each, and the average is exactly 49/20 = H₆ = 2.45; then H₁₀₀ ≈ 5.19.

Input size → what's feasible: all n! orders only for n ≤ 8 (8! = 40,320); for n = 100…10⁶ use the formula or a seeded simulation (Q30).

where H_n = 1 + 1/2 + 1/3 + … + 1/n is the n-th harmonic number, which grows like ln n (see lesson M01). So out of, say, 100 candidates interviewed in random order, you expect only about H₁₀₀ ≈ 5.19 hires — dramatically better than the worst case of hiring all 100 times (if they happened to arrive in increasing order of quality).

In Dart: all n! permutations for n = 1…7: the total number of fixed points equals n!, so the average is exactly 1; and the dependence between the indicators for n = 3 (Pr{slots 0 and 1 fixed} = 1/6 ≠ 1/9) while linearity still holds.

Input size → what's feasible: n ≤ 8 for enumeration; the proof by indicators works for every n.

11. Variance — how spread out is X?

Var[X] == E[(X - E[X]) ^ 2]  ==  E[X^2] - E[X]^2

In Dart: Var[X] = E[X²] − E[X]² and the definition E[(X − E[X])²] computed side by side for a die (35/12), a constant (0) and the sum of two independent dice (35/6).

Input size → what's feasible: sums over ≤ 36 outcomes here; for n samples it is one pass keeping the sum and sum of squares, O(n) time, O(1) space.

For a fair die: E[X]=3.5, E[X²] = (1+4+9+16+25+36)/6 = 91/6 ≈ 15.17, so Var[X] = 91/6 − 3.5² = 35/12 ≈ 2.92. A useful fact used later for tail bounds: variance of a SUM of pairwise-independent variables is the sum of the variances — no cross terms, unlike the mean, which needs no independence at all.

12. Geometric & binomial distributions

Geometric:  Pr(X == k) == (1-p)^(k-1) * p          E[X] == 1 / p
Binomial:   Pr(X == k) == C(n,k) * p^k * (1-p)^(n-k)   E[X] == n * p

In Dart: geometric and binomial formulas as functions: Pr{X = k} tables summing to 1, the means 1/p and np, the variance np(1−p), the exactly-2-heads-in-3 = 3/8 value, and a seeded simulation.

Input size → what's feasible: geometric: truncating at 2000 terms is exact enough for p = 1/4; binomial with n ≤ 60 → choose fits an int; for larger n use logs.

The binomial distribution's mean is simply np — provable instantly by linearity: write X as the sum of n independent 0/1 indicators (one per trial, each with E=p), so E[X] = n·p, no combinatorics needed at all (a second, harder proof exists using the raw formula and Pascal's identity, but the indicator-variable proof is the one worth remembering).

In Dart: a Galton board as 10 coin flips per ball: 20,000 seeded balls fall into bins whose frequencies match C(10,k)/2¹⁰ to within 1.5 percentage points.

Input size → what's feasible: 10 pegs × 20,000 balls = 2·10⁵ flips; error ≈ 1/√balls, so 20,000 balls give about ±0.3% per bin.

13. The birthday paradox

Pr(at least one shared birthday among k people)
  == 1 - ( 365/365 * 364/365 * 363/365 * ... * (365-k+1)/365 )

In Dart: the exact product 1 − Π(365−i)/365 as a loop, the smallest group above one half (23), the pigeonhole case (366 → 1.0) and a seeded simulation using a Set to detect a repeat.

Input size → what's feasible: k ≤ 365 → at most 365 multiplications; the product never underflows (365!/365³⁶⁵ ≈ 10⁻¹⁵⁷ is still a normal double).

In Dart: the indicator-variable birthday argument: C(23,2) = 253 pairs, E[matching pairs] = C(k,2)/365 verified exactly on a tiny 4-day year with 3 people (all 64 outcomes), and k(k−1)/730 = 1 ⇒ k ≈ √730 ≈ 27.

Input size → what's feasible: k ≤ 10⁵ → C(k,2) ≈ 5·10⁹ fits a 64-bit int; the tiny-year check enumerates only days^people outcomes.

14. Balls, bins & the coupon collector

E[boxes needed to collect all n coupons] == n * H(n)

In Dart: E = Σ n/(n−i) = n·Hₙ as the stage-by-stage sum, compared with n·Hₙ for several n and with a seeded simulation for n = 8.

Input size → what's feasible: n ≤ 10⁶ → the formula is O(n); a simulation costs ≈ n·Hₙ draws per run (≈ 1.4·10⁷ for n = 10⁶), so keep runs small.

Why n·H_n? Split the process into n stages: stage i starts right after you collect your i-th distinct coupon and ends when you get your (i+1)-th new one. While you already have i distinct coupons out of n, each new box is "useful" with probability (n−i)/n — a geometric distribution with expectation n/(n−i). Summing these n expected stage-lengths for i=0..n−1 gives exactly n(1/n + 1/(n−1) + … + 1/1) = n·H_n.

15. Randomized algorithms: shuffling fairly

The correct algorithm is the Fisher–Yates shuffle (in-place random permutation): walk the array left to right; at each position i, swap it with a uniformly random position chosen from the SHRINKING remaining suffix [i, n−1] — never from the whole array.

In Dart: The in-place shuffle with the 1-indexed → 0-indexed shift written out: math-style RANDOM(i, n) becomes i + rng.nextInt(n − i); then a seeded check that each element lands in slot 0 about 1/5 of the time.

Input size → what's feasible: n ≤ 10⁷ elements → n swaps ≈ 10⁷ steps (roughly a tenth of a second on a laptop); nextInt(max) needs max ≤ 2³².

Now the common bug: swap position i with a random index chosen from the WHOLE array every time, not the shrinking suffix.

In Dart: the fairness test for shuffles: every sequence of random choices for n = 3 is enumerated; Fisher–Yates (3·2·1 = 6 sequences) gives each of the 6 orders exactly once, the naive version (3³ = 27 sequences) gives three orders 4 times and three orders 5 times.

Input size → what's feasible: exhaustive enumeration only for n ≤ 8 (n^n sequences: 8⁸ ≈ 1.7·10⁷); for bigger n use the counting argument.

16. Randomized quicksort & tail bounds

Quicksort's worst case is Θ(n²) — but only for specific, adversarial input orders (already sorted, if you always pick the first element as pivot). The Quicksort lesson shows that picking the pivot uniformly at random at every step (instead of trusting the input to be "nicely shuffled") makes the Θ(n²) worst case astronomically unlikely for ANY fixed input, because the randomness is now inside the algorithm, not an assumption about outside data. The expected number of comparisons works out to a clean closed form, asymptotically 2n ln n — the same Θ(n lg n) as merge sort, just with a random pivot instead of a guaranteed-balanced split.

E[comparisons in randomized quicksort] == 2*(n+1)*H(n) - 4*n  ~=  2 * n * ln(n)

In Dart: the exact expectation from the recurrence E(n) = (n−1) + (2/n)ΣE(q) against the closed form 2(n+1)H(n) − 4n (n ≤ 200), then a seeded randomized-pivot run on 1000 keys compared with the formula and with 2n ln n.

Input size → what's feasible: n = 10⁶ → ≈ 2.5·10⁷ expected comparisons (a fraction of a second); the Θ(n²) worst case would be 5·10¹¹.

How do we know the Θ(n²) case is "astronomically unlikely" rather than merely "not the average"? Tail bounds quantify exactly how unlikely a random variable is to stray far from its mean.

In Dart: Markov's inequality checked on a die for t = 1…6, and the true tail of "heads in 100 flips" against the Markov bound: Pr{X ≥ 75} ≈ 2.8·10⁻⁷ while Markov only promises ≤ 0.667 — the tail collapses exponentially, Markov barely moves.

Input size → what's feasible: 100 flips → exact tail via a running binomial coefficient in double (C(100,50) ≈ 10²⁹ fits); for n in the thousands work in logs.

Quiz

Interview questions

Cheat sheet