A Question on Permutations and Binomial Distributions

Question

I am not a mathematician but I stumbled across the following formula when I was reading about binomial distribution in statistics.

$$N(N-1)...(N-n+1)\approx N^n$$ If $$n<<N$$ Could anyone please provide me with the theoretical derivation of the above equation?

Answer 1

It is a little bit ambiguous. I guess what they really mean is that :

when n is given, then

$N(N-1)...(N-n+1) \underset{N \rightarrow \infty}{\sim} N^n$

which means that $\lim\limits_{N \rightarrow +\infty}\frac{N^n}{N(N-1)...(N-n+1)}=1$

You can prove it by writting :

$1<\frac{N^n}{N(N-1)...(N-n+1)}<\frac{N^n}{(N-n+1)^n}=(\frac{N}{N-n+1})^n$

and $\lim\limits_{N \rightarrow +\infty} \frac{N}{N-n+1}=1$

so, $\lim\limits_{N \rightarrow +\infty} (\frac{N}{N-n+1})^n=1$

Answer 2

It's not an equality, but it can work as an approximation.

It can be "justified" seeing that:

$$\frac{N(N-1)(N-2)\ldots(N-n+1)}{N^n}=\frac{N(N-1)(N-2)\ldots(N-n+1)}{N\cdot N\cdot N \ldots N},$$ where the $N$ in the denominator appears $n$ times.

Then the former expresion equals, $$\frac NN \frac{(N-1)}N \frac{(N-2)}N\ldots\frac{(N-n+1)}N=1\cdot \left(1-\frac1N\right)\cdot \left(1-\frac2N\right)\cdot \ldots\cdot\left(1-\frac{n-1}N\right).$$

Now, if $n<<N$, then all the terms $\frac1N$, $\frac 2N$, $\ldots$, $\frac{n-1}N$ are nearly zero, so every factor is close to $1$. Then $$\frac{N(N-1)(N-2)\ldots(N-n+1)}{N^n}\approx 1,$$ and so $$N(N-1)(N-2)\ldots(N-n+1)\approx N^n.$$

Having say that... saying that something is approximately some other thing, doesn't have a clear mathematical meaning, so you should check under which conditions the approximation gives an error margin which is not relevant in the context you want to use it.

In this case, if you want to keep your error in a reasonable margin (say around $1\%$), for $N=500$ you need $n\le 3$, and if $N=1000$, then you need $n\le 5$.

For $N=10000$ you should take $n\le 15$ and for $N=100000$, $n\le 45$.

Based on this figures, we can conclude that not only has $n$ to be way smaller than $N$, $n$ also has to be really small itself. That is, when you increase $N$ a lot, you can barely increase $n$ a little if you want to stay within that $1\%$ error margin.

So, in conclusion, it is (kind of) an approximation, but not a very good one.