Factorial estimates

Let us start with a simple question:

There are $n$ students in class. Each student is assigned a random number in $\{1,\ldots, n\}$ What is the probability that no two students are assigned the same number?

In other words, pick a random function $f: [n] \rightarrow [n]$. What is the probability that $f$ is a permutation? We should now know that this is $n!/ n^n$. But what exactly is this number? Does it converge to zero, or is it closer to one? Let us start with a simple lemma.

Lemma 14 (Gauß)

$n^{n/2} \leq n! \leq \left(\frac{n+1}{2}\right)^n$

Proof:

We work with the square of $n!$ (and will be taking the square root later). Rewrite $(n!)^2 = (1\cdot 2 \cdots n)(n \cdot (n-1) \cdots 1)$, so we have two groups of the products. We pair $1$ (from the first group) with $n$ (from the second group), $2$ with $(n-1)$ and so on; more generally, we pair $i$ with $(n-i+1)$. This implies that

$n! = \left(\prod_{i=1}^n (i \cdot (n-i+1))\right)^{1/2}$

Now we analyze the two directions of the inequality:

• To prove the upper bound, by AM-GM, we have $\sqrt{i (n-i+1)} \leq (n+1)/2$, so this implies that $n! \leq \left((n+1)/2\right)^n$.
• To see the lower bound, notice that $i (n-i+1) \geq n$ for all $i=1,\ldots, n$. (do you see why? maybe try to prove this before reading the footnote 😊)¹

Now let us return to the probability $p=n!/n^n$. Plugging in the above estimates,

$n^{-n/2} \leq p \leq \frac{1}{2^n}(1+1/n)^n$

Using Lemma 13, we have that $(1+1/n)\leq e^{1/n}$, so $p \leq e/2^n$. This simple estimate implies that the probability term converges to zero at exponential rate. Notice that we still have a very large gap between the lower and the upper bounds. Let us try to get a better estimate.

Theorem 28

$e(n/e)^n \leq n! \leq en (n/e)^n$

Notice that the ratio between the upper and lower bounds is exactly $n$ (which is a very low order term compared to $(n/e)^n$). Therefore, this bound is considered relatively tight and the proof is quite elementary. Now, using this theorem, the probability $p$ becomes already nicely estimated:

$1/e^{n-1} \leq p \leq n/e^{n-1}$

Exercise 79

Prove the upper bound side of Theorem 28. Use induction on $n$.

Theorem 29 (Stirling's formula)

$n! \sim (n/e)^n \sqrt{2 \pi n}$

The Stirling formula is a very tight estimate of factorials (recall the meaning of asymptotic equality, that when $n$ is large, the two sides of the equation are practically the same). For instance, when $n= 8$, the error of this estimate is already less than $1$ percent.

Footnotes

1. A simple argument: When $i=1$ or $i=n$, this is obvious. Otherwise, when $i \geq 2$, this is a product between two numbers. The smaller number is always at least $2$ and the bigger number is at least $n/2$. ↩