Permutation approximation

  • Thread starter ppedro
  • Start date
  • #1
22
0

Main Question or Discussion Point

How can I prove that, for [itex]N\gg n[/itex]

[itex]\frac{N!}{(N-n)!}\approx N^{n}[/itex]

I've tried doing

[itex]\frac{N!}{(N-n)!}=\exp\left(\ln\frac{N!}{(N-n)!}\right)=\exp\left(\ln N!-\ln\left(N-n\right)!\right)[/itex]

[itex]\underset{stirling}{\approx}\exp\left(N\ln N-N-\left(N-n\right)\ln\left(N-n\right)+N-n\right)[/itex]

[itex]=N^{N}+\left(N-n\right)^{n-N}+\exp-n[/itex]

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

Answers and Replies

  • #2
210
10
I don't think you need Stirling's Approximation to show this:

[tex]\frac{N!}{(N-n)!} = N(N-1)...(N-n+1)[/tex]
[tex]\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)[/tex]

So for any fixed [itex]n[/itex], [itex]N^n[/itex] becomes a better approximation as [itex]N[/itex] becomes larger. (How good depending on the size of [itex]n[/itex]).
 
Last edited:
  • Like
Likes 1 person
  • #3
22
0
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.
 
  • #4
210
10
Well to avoid the ...'s, you can use the [itex]\prod[/itex] 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.
 
  • #5
22
0
I'm afraid I don't know how to do it. Could you write it explicitly? Many thanks
 
  • #6
160
21
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....
 
  • Like
Likes 1 person
  • #7
22
0
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

[itex]=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}[/itex]

and I see that[itex] \left(\frac{N}{N-n}\right)^{N-n}=e^{n}[/itex] leading to the final answer.
 
  • #8
210
10
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:

[tex]\frac{N!}{(N-n)!} = \prod_{k=0}^{n-1}(N-k)[/tex]
[tex]\frac{N!}{N^n(N-n)!} = \frac{1}{N^n}\prod_{k=0}^{n-1}(N-k)[/tex]
[tex]\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)[/tex]
[tex]\frac{N!}{N^n(N-n)!} = \prod_{k=0}^{n-1}\frac{N-k}{N}[/tex]
[tex]\frac{N!}{N^n(N-n)!} = \prod_{k=0}^{n-1}\left(1-\frac{k}{N}\right)[/tex]

Now, assuming [itex]n[/itex] is constant, take the limit as [itex]N[/itex] approaches [itex]∞[/itex].
[tex] \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[/tex]

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

Related Threads on Permutation approximation

  • Last Post
Replies
4
Views
851
  • Last Post
Replies
1
Views
641
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
609
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
10
Views
5K
  • Last Post
Replies
20
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
2
Views
2K
Top