Slot-size bound for hash chaining (Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms, Problem 11-2, page 250):

Suppose we have a hash table with n slots, with collisions resolved by
chaining, and suppose that n keys are inserted into the table. (That is,
the fill ratio is 1). Each key is equally likely to be hashed to each
slot, independently of the other keys. Let M be the maximum number of
keys in any slot after all the keys have been inserted. Your mission is
to prove an O(log n / log log n) upper bound on E[M], the expected value
of M.

(a) Argue that the probability Q_k that exactly k keys hash to a
particular slot is given by
    Q_k = (1/n)^k (1 - 1/n)^(n-k) (n choose k)
(The last term is the binomial coefficient that counts the number of
distinct k-tuples that can be formed by n items; it equals n!/k!(n-k)!.)

(b) Let P_k be the probability that M = k; that is, the probability that
the slot containing the most keys contains k keys. Show that P_k <= n Q_k.

(c) Use Stirling's approximation to show that Q_k < e^k / k^k.
Stirling's approximation is:
    n! = sqrt(2 pi n) (n/e)^n (1 + Theta(1/n))
where e ~ 2.71828 is the base of the natural logarithm.

(d) Show that there exists a constant c > 1 such that Q_k0 < 1/n^3
for k0 = c log n / log log n. Conclude that P_k < 1/n^2 for k >= k0.

(e) By arguing that
    E[M] <= n Pr[ M > c log n / log log n] +
                (c log n / log log n) Pr[ M <= c log n / log log n],
conclude that E[M] = O(log n / log log n).