Introduction to Probability · Problem 12.1.14

Random Walks — Grinstead & Snell

Mathematics — Probability · random-walks-multinomial

Problem

Prove that

\sum_{j,k} \left(\frac{1}{3^n} \frac{n!}{j!k!(n-j-k)!}\right) = 1,

where the sum extends over all non-negative

j

and

k

such that

j + k \leq n

. Hint: Count how many ways one can place

n

labelled balls in 3 labelled urns.