Stirling's approximation

<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, Stirling's approximation (or Stirling's formula) is an <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic</a> approximation for <a href="/facts/Factorial/kkfy1Bwe">factorials</a>. It is a good approximation, leading to accurate results even for small values of 
  
    
      
        n
      
    
    {\displaystyle n}
  
. It is named after <a href="/facts/James_Stirling_(mathematician)/XmIkBrUE">James Stirling</a>, though a related but less precise result was first stated by <a href="/facts/Abraham_de_Moivre/m9hpa6Mb">Abraham de Moivre</a>.
</p><p>One way of stating the approximation involves the <a href="/facts/Logarithm/QeXaV97q">logarithm</a> of the factorial:

ln
        ⁡
        (
        n
        !
        )
        =
        n
        ln
        ⁡
        n
        −
        n
        +
        O
        (
        ln
        ⁡
        n
        )
        ,
      
    
    {\displaystyle \ln(n!)=n\ln n-n+O(\ln n),}

where the <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a> means that, for all sufficiently large values of 
  
    
      
        n
      
    
    {\displaystyle n}
  
, the difference between 
  
    
      
        ln
        ⁡
        (
        n
        !
        )
      
    
    {\displaystyle \ln(n!)}
  
 and 
  
    
      
        n
        ln
        ⁡
        n
        −
        n
      
    
    {\displaystyle n\ln n-n}
  
 will be at most proportional to the logarithm of 
  
    
      
        n
      
    
    {\displaystyle n}
  
. In computer science applications such as the <a href="/facts/Comparison_sort/X1PvE50c">worst-case lower bound for comparison sorting</a>, it is convenient to instead use the <a href="/facts/Binary_logarithm/Uy7kAtRm">binary logarithm</a>, giving the equivalent form

log
          
            2
          
        
        ⁡
        (
        n
        !
        )
        =
        n
        
          log
          
            2
          
        
        ⁡
        n
        −
        n
        
          log
          
            2
          
        
        ⁡
        e
        +
        O
        (
        
          log
          
            2
          
        
        ⁡
        n
        )
        .
      
    
    {\displaystyle \log _{2}(n!)=n\log _{2}n-n\log _{2}e+O(\log _{2}n).}
  
 The error term in either base can be expressed more precisely as 
  
    
      
        
          
            
              1
              2
            
          
        
        
          log
          
            2
          
        
        ⁡
        (
        2
        π
        n
        )
        +
        O
        (
        
          
            
              1
              n
            
          
        
        )
      
    
    {\displaystyle {\tfrac {1}{2}}\log _{2}(2\pi n)+O({\tfrac {1}{n}})}
  
, corresponding to an approximate formula for the factorial itself,

n
        !
        ∼
        
          
            2
            π
            n
          
        
        
          
            (
            
              
                n
                e
              
            
            )
          
          
            n
          
        
        .
      
    
    {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}.}

Here the sign 
  
    
      
        ∼
      
    
    {\displaystyle \sim }
  
 means that the two quantities are asymptotic, that is, their ratio tends to 1 as 
  
    
      
        n
      
    
    {\displaystyle n}
  
 tends to infinity.
</p>

Stirling's approximation open-in-new

Stirling's approximation