  Suppose $n$ boys and $n$ girls rank each other at random. We show that any
particular girl has at least $({1\over 2}-\epsilon) \ln n$ and at most
$(1+\epsilon)\ln n$ different husbands in the set of all Gale/Shapley stable
matchings defined by these rankings, with probability approaching 1 as $n \to
\infty$, if $\epsilon$ is any positive constant. The proof emphasizes general
methods that appear to be useful for the analysis of many other combinatorial
algorithms.
