1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutation approximation

  1. Aug 30, 2013 #1
    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
     
  2. jcsd
  3. Aug 30, 2013 #2
    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: Aug 30, 2013
  4. Aug 30, 2013 #3
    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.
     
  5. Aug 30, 2013 #4
    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.
     
  6. Aug 30, 2013 #5
    I'm afraid I don't know how to do it. Could you write it explicitly? Many thanks
     
  7. Aug 30, 2013 #6
    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....
     
  8. Aug 31, 2013 #7
    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.
     
  9. Sep 1, 2013 #8
    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).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Permutation approximation
I Permutation of identical elements
B Permutations and combinations