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).