First, look at some sites like tinyurl.com or snurl.com which take long URLs and create new short names for them. You might wonder how quickly such sites will run out of short names.

How many different characters does the site choose from, when generating shortened-URLs? (More than 26, as a-z are all used, as well as ...?) If you need to generate one or two short-URLs, go ahead. Both snurl.com and TinyURL use lower-case letters and digits only (36). How many possible shortened-URLs have length exactlylength 6, counting only the part after the domain name and the following slash, of course. 6? ³⁶ How many possible shortened-URLs have length 6 or less? ^_Σ 36 = (³⁶-1)/35 (by the formula for geometric series, in Rosen)

If there are ¹⁰ static web pages, and every single one of them were registered on such a site, how long would be the longest small URL be? (Just count the encoded part of the name, without the initial ``http://www.snurl.com/'' prefix.) We want an n such that
     (³⁶-1)/35 ≥ ¹⁰
⇔ ³⁶ ≥ 35·¹⁰+1
⇔ _log(³⁶) ≥ _log( 35·¹⁰+1 )
⇐ n+1 ≥ _log( 36·¹⁰ )
⇔ n+1 ≥ _log(¹⁰)+1
⇔ n ≥ _log(¹⁰)
        = 10 · _log(10)
        = 10 · log(10)/log(36)
        ≈ 10 · 0.64
⇐ n ≥ = 7.
Reversing these implications, we see that using n=7 characters in the URL ensures that there are more than ¹⁰ possible URLs.

We might then start to wonder, is ¹⁰ a reasonable upper estimate on the number of web pages? After all, one of the best use of these sites is for abbreviating dynamic URLs which contain (long) queries embedded inside them (e.g. mapquest URLs). So we'll ask the same question, but now suppose that ¹⁰ people each generate one dynamic request per second, for ¹⁰sec (about 320 years — e.g. since William of Orange took the English throne in 1688). How long will the longest short-URLs be now?

By the same reasoning as above (but using ¹⁰ rather than ¹⁰), we get
     n ≥ _log(¹⁰)
       = 20 · _log(10)
       = 20 · log(10)/log(36)
       ≈ 20 · 0.64
⇐ n ≥ 13.
Even after 320 years, short-URLs won't be particularly long!

To think about to yourself:
Does one of these sites do a better job than the other? Which do you prefer?

p.344, #30a-e (5ed, p.310 #28a-e): alphabet soup ²⁶ ≈ 209 billion P(26,18) = 26!/18! ≈ 63 billion ²⁶ ≈ 8 billion P(25,18) = 25!/18! ≈ 2 billion ²⁶ ≈ 0.3 billion p. 361 #18 (5ed, p.324 #18): flipping eight coins ² = 256 C(8,3) = 8·7·6/3·2·1 = 56 The number of toss-sequences which have 3 or more heads is ² minus the number of sequences with 2 or fewer tails: ² - (C(8,0)+C(8,1)+C(8,2)) = 256-(1+8+28) = 219 C(8,4) = 8!/4!4! = 8·7·6·5/4·3·2·1 = 2·7·5 = 70. p. 369 #9 variant (5ed, p.333 #9, variant) What is the coefficient of ^x101^y99 in the expansion of ^(x+y)200? What is the coefficient of ^u101^v99 in the expansion of ^(3u-2v)200? p.398, #4 (5ed p.360, #4) Remember: divide the number of "desired" outcomes by the number of possible outcomes.
(We presume that each day is equally likely, out of the 366 possibilities). 30/366 = 5/61, or approx 8% p.398, #6 (5ed p.360, #6) When counting desired outcomes, be sure not to accidentally count the ace of hearts twice! (4+13-1)/52 = 16/52, approx 31%. p.398, #8 (5ed p.361, #8) C(51,4)/C(52,5) = (51·50·49·48/4·3·2) / (52·51·50·49·48/5·4·3·2) = 5/52, or approx 10%. Reading: (5ed §11.1) Languages and Grammars (5ed p.749, #4ab).
As mentioned in the reading, S→AB means you can replace the substring "S" with the substring "AB"; the question asks you to keep making substitutions until you only have lower-case letters (terminals). {abbb}, a set with only a single string. {aba,aa}, a set with only two strings.