# 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.53

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

Describe the graph structure of*partial*mappings, where the image of a point may be undefined. Set up the corresponding EGF equations and check that the number of partial mappings of size $N$ is $(N+1)^N$.

## 9.60

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.61

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 (!).

#### Review Questions

## Q9.1

Give the EGF for random mappings with no singleton cycles. Express your answer as a function of the Cayley function $C(z) = e^{C(z)}$.## Q9.2

This problem involves enumerating the mappings where every character appears exactly twice or not at all. Such mappings must be of even length. There are 2 such mappings of length 2 (11 and 22) and 36 of them of length 4. By a direct combinatorial argument, it is not difficult to derive the explicit form $$C_{2n} = {2n\choose n}{(2n)!\over 2^n}.$$ Give an explicit formula for the EGF $$C(z) = \sum_{n\ge0}{C_{2n}\over(2n)!}z^{2n}$$ and an asymptotic estimate (~-approximation) of $C_{2n}$.*Extra credit*: Give a full derivation via analytic combinatorics.