# 9. Words and Maps

This chapter covers global properties of *words*
(`N`-letter strings from an `M`-letter alphabet),
which are well-studied in classical combinatorics
(because they model sequences of independent Bernoulli trials) and in
classical applied algorithmics
(because they model input sequences for hashing algorithms).
The chapter also covers random *maps*
(`N`-letter words from an `N`-letter alphabet)
and discusses relationships with trees and permutations.

## 9.1 Hashing with Separate Chaining

## 9.2 Basic Properties of Words

## 9.3 Birthday Paradox and Coupon Collector Problem

## 9.4 Occupancy Restrictions and Extremal Parameters

## 9.5 Occupancy Distributions

## 9.6 Open Addressing Hashing

## 9.7 Maps

## 9.8 Integer Factorization and Maps

#### Selected Exercises

## 9.5

For $M=365$, how many people are needed to be 99% sure that two have the
same birthday?

## 9.22

Give a plot (for $M=365$) of the probability that

*three* people have
the same birthday.

## 9.23

For $M=365$, how many people are needed to be 50% sure that three have the
same birthday? Four?

## 9.28

What is the probability that one urn will get all the balls
when 100 balls are randomly distributed among 100 urns?

## 9.29

What is the probability that each urn will get one ball
when 100 balls are randomly distributed among 100 urns?

## 9.37

Find $[z^n]e^{\alpha C(z)}$ where $C(z)$ is the Cayley function (see
the discussion at the end of Section 6.14 and in Section 9.7 in this chapter).5

## 9.38

(``Abel's binomial theorem.'') Use the result of the previous exercise
and the identity $e^{(\alpha+\beta)C(z)}=e^{\alpha C(z)}e^{\beta C(z)}$ to
prove that
$$(\alpha+\beta)(n+\alpha+\beta)^{n-1}
=\alpha\beta\sum_k{n\choose k}(k+\alpha)^{k-1}(n-k+\beta)^{n-k-1}.$$

## 9.50

A map with no repeated integers is a permutation.
Give an efficient algorithm for determining whether a map is
a tree.

## 9.57

Generate 100 random maps of size 100, 1000, and
10000 and empirically verify that about 48% of the nodes are in
the largest tree, that about 76% of the nodes are in the largest cycle,
and that, in a random map of size $N$, the number of nodes
in the longest tail, cycle, and rho-path are about $1.74\sqrt{N}$,
$.78\sqrt{N}$, and $2.41\sqrt{N}$, respectively.

## 9.58

Use Floyd's method to test the random number
generator on your machine for short cycles.

## 9.99

Show that the probability that a random mapping of size N has no singleton
cycles is $\sim 1/e$, the same as for permutations (!).