Fall 2011 Strategic Practice 1: Section 1 (Naive Definition of Probability) - Question 4
A norepeatword is a sequence of at least one (and possibly all) of the usual 26 letters a, b, c, ... , z, with repetitions not allowed. For example, "course" is a norepeatword, but "statistics" is not. Order matters, e.g., "course" is not the same as "source". A norepeatword is chosen randomly, with all norepeatwords equally likely. Show that the probability that it uses all 26 letters is very close to 1/e.
Solution: The number of norepeatwords having all 26 letters is the number of ordered arrangements of 26 letters: 26!. To construct a norepeatword with k less than or equal to 26 letters, we first select k letters from the alphabet (26 C k selections) and then arrange them into a word (k! arrangements). Hence there are (26 C k)k! norepeatwords with k letters, with k ranging from 1 to 26. With all norepeatwords equally likely, we have P (norepeatword having all 26 letters) = no. norepeatwords having all 26 letters / no. norepeatwords. The denominator is the first 26 terms in the Taylor series e^x = 1 + x + x^2/2! + ..., evaluated at x = 1. Thus the probability is approximately 1/e (this is an extremely good approximation since the series for e converges very quickly; the approximation for e differs from the truth by less than 10^-26).