1. Prove that, for any n that is not one less than a power of 2, there does not exist a bijection from P({1, 2, . . . , n − k}) to {0, 1, 2, . . . , n}.
2. In the corporate and political worlds, there’s a dubious technique called URL squatting, where someone creates a website whose name is very similar to a popular site and uses it to skim the traffic generated by poor-typing internet
users. For example, Google owns the addresses gogle.com and googl.com, which redirect to google.com. (But, as of this writing, someone else owns oogle.com, goole.com, and googe.com.) Consider an n-letter company name. How
many single-typo manglings of the name are there if we consider the following kinds of errors? Consider only uppercase letters throughout. (If your answers depend on the particular n-letter company name, then say how they depend on
that name. Note that no transposition errors are possible for the company name MMM, for example.)
1 one-letter substitutions
2 one-letter insertions
3 one-pair transpositions (two adjacent letters written in the wrong order)
4 one-letter deletions