How Is the Permutation Approximation Proven for Large N?

[ppedro]

How can I prove that, for $N\gg n$

$\frac{N!}{(N-n)!}\approx N^{n}$

I've tried doing

$\frac{N!}{(N-n)!}=\exp\left(\ln\frac{N!}{(N-n)!}\right)=\exp\left(\ln N!-\ln\left(N-n\right)!\right)$

$\underset{stirling}{\approx}\exp\left(N\ln N-N-\left(N-n\right)\ln\left(N-n\right)+N-n\right)$

$=N^{N}+\left(N-n\right)^{n-N}+\exp-n$

But it doesn't look like I'm getting there

 

[Boorglar]

I don't think you need Stirling's Approximation to show this:

$$\frac{N!}{(N-n)!} = N(N-1)...(N-n+1)$$
$$\frac{N!}{N^n(N-n)!} = \left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right)...\left(1-\frac{n-1}{N}\right)$$

So for any fixed $n$, $N^n$ becomes a better approximation as $N$ becomes larger. (How good depending on the size of $n$).

 

[ppedro]

I understand what you wrote in the first line. I have n factors involving N minus something which is to be small compared with N. But I should be able to say it formally.

 

[Boorglar]

Well to avoid the ...'s, you can use the $\prod$ product notation, and then take the limit as N goes to infinity of both sides, using the properties of the limit of a finite product.

 

[ppedro]

I'm afraid I don't know how to do it. Could you write it explicitly? Many thanks

 

[eigenperson]

You were almost there in the first post -- you just need to use the fact that n is much smaller than N.

How big is n? Let's say that $n = \log N$. (If n is too big, it won't be true any more!)

Then $\log(N - n) = \log\left(N - \log N\right) = \log N - \int_{N-\log N}^N {1 \over x}\,dx.$ And $\int_{N-\log N}^N {1 \over x}\,dx = {\log N \over N} + O\left((\log N)^2 \over N^2\right),$ so
$\log(N - n) = \log N - {\log N \over N} + O\left((\log N)^2 \over N^2\right)$.

Now you can do the last step:

$N\log N - (N−n)\log(N−n) − n = N\log N - (N-\log N)\left(\log N - {\log N \over N} + O\left((\log N)^2 \over N^2\right)\right) - \log N = (\log N)^2 + O\left((\log N)^2/N\right).$ Then you can exponentiate to get the answer you wanted (don't forget that $n = \log N$).

I hope I did all the math correctly there...

 

[ppedro]

I saw I made a careless mistake on the last step of my approach. I was summing the terms where they should be multiplied. So I end up with

$=N^{N}\left(N-n\right)^{n-N}e^{-n}=e^{-n}\frac{N^{N}}{\left(N-n\right)^{N-n}}=e^{-n}N^{n}\left(\frac{N}{N-n}\right)^{N-n}$

and I see that$\left(\frac{N}{N-n}\right)^{N-n}=e^{n}$ leading to the final answer.

 

[Boorglar]

I'm afraid I don't know how to do it. Could you write it explicitly? Many thanks

Oh sorry I should've been more clear I guess:

$$\frac{N!}{(N-n)!} = \prod_{k=0}^{n-1}(N-k)$$
$$\frac{N!}{N^n(N-n)!} = \frac{1}{N^n}\prod_{k=0}^{n-1}(N-k)$$
$$\frac{N!}{N^n(N-n)!} = \left(\prod_{k=0}^{n-1}\frac{1}{N}\right)\left(\prod_{k=0}^{n-1}(N-k)\right)$$
$$\frac{N!}{N^n(N-n)!} = \prod_{k=0}^{n-1}\frac{N-k}{N}$$
$$\frac{N!}{N^n(N-n)!} = \prod_{k=0}^{n-1}\left(1-\frac{k}{N}\right)$$

Now, assuming $n$ is constant, take the limit as $N$ approaches $∞$.
$$\lim_{N \rightarrow ∞} \frac{N!}{N^n(N-n)!} = \lim_{N \rightarrow ∞}\prod_{k=0}^{n-1}\left(1-\frac{k}{N}\right) = \prod_{k=0}^{n-1}\lim_{N \rightarrow ∞}\left(1-\frac{k}{N}\right) = \prod_{k=0}^{n-1}1 = 1$$

which proves that for large enough $N$, the ratio of $\frac{N!}{N^n(N-n)!} ≈ 1$. So the two expressions are asymptotically the same (in terms of ratio).