A question posed on John D. Cook's blog asks:
Suppose you have a large number of buckets and an equal number of balls. You randomly pick a bucket to put each ball in one at a time. When you’re done, about what proportion of buckets will be empty?
Can you explain the answer to this question in a way understandable to high school students? How about to ten year olds?
Let $F_n$ be the set of functions from $[1,\ldots,n]$ to $[1,\ldots,n]$. We want to approximate:
$$ \sum_{f\in F_n}|\operatorname{Im} f|, $$
so we set a "double counting" approach.
$$ \sum_{f\in F_n}|\operatorname{Im} f| = \sum_{i\in[1,\ldots,n]}\left|\left\{ f\in F_n:i\in\operatorname{Im} f\right\}\right| = \sum_{i\in[1,\ldots,n]}\left(n^n-\left|\left\{ f\in F_n:i\not\in\operatorname{Im} f\right\}\right|\right),$$
so:
$$ \sum_{f\in F_n}|\operatorname{Im} f| = n(n^n-(n-1)^n)$$
and the average cardinality of $|\operatorname{Im}f|$ turns out to be:
$$ n\left(1-\left(1-\frac{1}{n}\right)^n\right), $$
so, for a large number of buckets, $\frac{n}{e}$ of them will be empty, in the average case.