Advanced Counting

Study Sheet

Advanced Counting

Recursion, expectation, and the binomial theorem

Building Recurrences

Concept
Condition on the last step

Count by splitting on the final move: a tiling ending in a square leaves an−1a_{n-1} ways, one ending in a domino leaves an−2a_{n-2}, so an=an−1+an−2a_n = a_{n-1}+a_{n-2}.

In plain terms. Ask "what could the last piece be?" Each choice reduces to a smaller version of the same problem, giving a recurrence.

Example. Ways to tile a 1×n1\times n strip with squares and dominoes: a1=1,a2=2,a3=3,a4=5a_1=1, a_2=2, a_3=3, a_4=5 — the Fibonacci numbers.

Tip
Binomial theorem

(x+y)n=∑k=0n(nk)xn−kyk(x+y)^n = \sum_{k=0}^n\dbinom nk x^{n-k}y^k.

In plain terms. Expanding a power of a sum spreads it into terms weighted by "choose" numbers; plugging in clever x,yx,y evaluates tricky sums.

Example. Set x=y=1x=y=1: ∑k(nk)=2n\sum_k\dbinom nk = 2^n. Set x=1,y=−1x=1,y=-1: the alternating sum is 00.

Reminder — The binomial theorem:  (x+y)n=∑k=0n(nk)x n−kyk(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{\,n-k}y^{k}

Expected Value

Tip
Linearity of expectation

The expected value of a sum equals the sum of expected values, even when the parts depend on each other.

In plain terms. To find an average total, add up the average of each little piece — you never need the pieces to be independent.

Example. Expected number of heads in 1010 flips: each flip contributes 12\tfrac12, so the total is 10⋅12=510\cdot\tfrac12 = 5.