*A proof that $\frac{1}{2}\frac{n^k}{k!}\lt{n\choose k}$.*

In a blog post, rjlipton proves that $$\frac{1}{4}\frac{n^k}{k!}\le{n \choose k}\le\frac{n^k}{k!}$$ when $k\le\sqrt{n}$. I posted a comment trying to strengthen the first inequality to $$\frac{1}{2}\frac{n^k}{k!}\lt{n \choose k}$$ That comment is almost unreadable because (1) I don't know how to use LaTeX on wordpress, (2) especially if I get only one try (can't edit). Here, I don't have such problems.

*Proof.*
Consider a hashtable with $n$ buckets and $k$ items.
There are $n^k$ ways to distribute the items, out of which ${n \choose k}k!$ have no collision.
The probability of having some collision is $1 - {n \choose k}k!/n^k$.
Now suppose $Y$ is a random variable whose value says how many collisions there are.
So,
$$P(Y\gt 0)=1-\frac{{n \choose k}}{n^k/k!} \le \mathop{\rm E} Y$$
The inequality comes from the first moment principle. The expected number of collisions increases with $k$, so we just look at the case $k=\sqrt{n}$.
There are $\sqrt{n}(\sqrt{n}-1)/2$ possible collisions, each happening with probability $1/n$.
Thus,
$$\mathop{\rm E}Y=\frac{\sqrt{n}(\sqrt{n}-1)}{2}\frac{1}{n}=\frac{1}{2}-\frac{1}{2\sqrt{n}}$$
Putting the previous two displayed inequalities together, we get
$$1-\frac{{n \choose k}}{n^k/k!}\le\frac{1}{2}-\frac{1}{2\sqrt{n}}$$
and finally
$$\frac{{n \choose k}}{n^k/k!} \ge \frac{1}{2}+\frac{1}{2\sqrt{n}} \gt \frac{1}{2}$$

**Update:** Stefan Kiefer pointed out that the tight bounds are
$$\frac{1}{\sqrt{e}}\frac{n^k}{k!}\lt{n \choose k}\le\frac{n^k}{k!}\qquad\text{if $k\le\sqrt{n}$}$$

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.