I am reading Section 3.4 of Algorithms, 4th Edition. Page 466 is a proof of the following proposition:
In a separate-chaining hash table with $M$ lists and $N$ keys, the probability (under Assumption J) that the number of keys in a list is within a small constant factor of $N/M$ is extremely close to 1.
The proof:
The probability that a given list will contain exactly k keys is given by the binomial distribution
$\binom{N}{k}(\frac{1}{M})^k(\frac{M-1}{M})^{N-k}$
When $N$ is large and $p=\frac{1}{M}$ is small, binomial distribution can be approximated by Poisson distribution (The book uses $\alpha$ for $\lambda$):
$\frac{\alpha^ke^{k}}{k!}$
It follows that the probability that a list has more than $t\alpha$ keys on it is bounded by the quantity $(\alpha\frac{e}{t})^t e^{-\alpha}$.
In other words, the probability that $P(X > t\alpha)$ is bounded by the quantity $(\alpha\frac{e}{t})^t e^{-\alpha}$.
I searched the web and browsed https://en.wikipedia.org/wiki/Poisson_distribution. But I couldn't find a reference for the formula $(\alpha\frac{e}{t})^t e^{-\alpha}$.
Here is a candidate answer combining @Did's and @ClementC's comments:
From the background in the book, we can assume that $\alpha \geqslant 10$ and $t \geqslant 2$.
For $s > 0$, $\{X \geqslant t\alpha \} = \{sX \geqslant st\alpha\} = \{e^{sX} \geqslant e^{st\alpha}\}$, so
$P(X > t\alpha ) \leqslant P(X \geqslant t\alpha) \leqslant \frac{E[e^{sX}]}{e^{st\alpha}}$
by Markov's inequality. Since $E[e^{sX}] = e^{\alpha(e^{s}-1)}$, we have:
$P(X > t\alpha ) \leqslant \frac{e^{\alpha(e^{s}-1)}}{e^{st\alpha}} = e^{\alpha(e^{s}-1)-st\alpha}$
Maximizing this bound is equivalent to maximizing $\alpha(e^{s}-1)-st\alpha$. And it is obvious that maximizing $\alpha(e^{s}-1)-st\alpha$ is equivalent to maximizing $f(s) = e^{s}-st$ since $\alpha > 0$.
$f\prime(s) = e^{s} - t$
$f\prime\prime(s) = e^{s}$
Solve $f\prime(s) = 0$, we have $s = \ln{t}$. And $f\prime\prime(\ln{t}) = t > 0$. So $s = \ln{t}$ maximizes $f(s)$.
$P(X > t\alpha ) \leqslant \frac{e^{\alpha(t-1)}}{t^{t\alpha}} = (\frac{e^{\alpha}}{t^{\alpha}})^t e^{-\alpha} $
Now let's compare $\frac{e^{\alpha}}{t^{\alpha}}$ with $\alpha \frac{e}{t}$. When $t \geqslant 3$, we have $\frac{e^{\alpha}}{t^{\alpha}} < \alpha \frac{e}{t}$.
When $t= 2$, we have $(\frac{e}{2})^\alpha$ and $\alpha \frac{e}{2}$. When $\alpha = 10$, we have $(\frac{e}{2})^\alpha = 21.51022050274092$ and $\alpha \frac{e}{2} = 13.591409142295225 $. When $\alpha = 20$, we have $(\frac{e}{2})^\alpha = 462.68958607653593$ and $\alpha \frac{e}{2} = 27.18281828459045$. So when $t = 2$, $\frac{e^{\alpha}}{t^{\alpha}} < \alpha \frac{e}{t}$ is not true.
By the above discussion, we can prove $P(X > t\alpha ) \leqslant (\alpha \frac{e}{t})^{t} e^{-\alpha}$ for $t \geqslant 3$. But we can't prove the $t = 2$ case.
I've been spending hours thinking about the same problem!
It turns out that the formula $(\alpha e/t)^t e^{-\alpha}$ is incorrect. The correct formula is $(e/t)^{\alpha t}e^{-\alpha}$.
The correction is posted on the textbook website: Errata.