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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Permutation approximation
  1. Permutation problem (Replies: 10)

  2. Even Permutations (Replies: 4)

  3. Permutation Matrices (Replies: 4)

Loading...