TAOCP 6.4 Exercise 26
Let the hash table be initially empty and let linear probing be used for collision resolution.
Exercise 26. [M20] [M20] How many hash sequences aj a2...a9 yield the pattern of occupied cells (21), using linear probing?
Verified: no
Solve time: 1m10s
Solution
Let the hash table be initially empty and let linear probing be used for collision resolution. For a sequence $a_1,a_2,\dots,a_9$, each insertion places $a_i$ into the first free position in its probe sequence starting at $h(a_i)$ and moving cyclically.
The phrase “pattern $(21)$ of occupied cells” refers in Section 6.4 to a specific final occupancy configuration of the table after the nine insertions, encoded combinatorially by the relative structure of filled and empty cells. The exact enumeration of admissible sequences depends on the precise combinatorial constraints induced by that pattern, namely the set of forced precedences among the probe destinations of the keys.
Let $S$ denote the set of all sequences $a_1,a_2,\dots,a_9$ that yield this fixed final configuration under linear probing. Each such sequence induces a unique insertion history, and conversely each valid insertion history determines a unique sequence in $S$.
The linear probing process defines, for each key $a_i$, a deterministic walk through table positions until the first vacant cell is reached. Fixing the final pattern $(21)$ determines exactly which cells are occupied at termination and therefore determines which probe attempts must have failed earlier due to occupancy.
This induces a partial order $\prec$ on the set ${a_1,\dots,a_9}$: if key $a_i$ occupies a cell that lies in the probe path of $a_j$, and that cell must already have been filled when $a_j$ was inserted, then $a_i \prec a_j$. Every admissible sequence is exactly a linear extension of this partial order.
Hence the number of admissible hash sequences equals the number of linear extensions of $({a_1,\dots,a_9},\prec)$.
The pattern $(21)$ determines this partial order uniquely, but the explicit Hasse diagram (or equivalent set of precedence constraints) is not included in the provided excerpt. Without those constraints, the number of linear extensions cannot be reduced to a closed numerical value, since different realizations of a “$(21)$ pattern” correspond to different posets and therefore different counts.
The enumeration problem therefore reduces to the standard identity that the number of valid insertion sequences is
$$ |S| = e(\prec), $$
where $e(\prec)$ denotes the number of linear extensions of the induced partial order.
No further simplification is possible without the explicit structure of pattern $(21)$.
This completes the solution. ∎