 # FPGA Central

## World's 1st FPGA Portal

 DSP comp.dsp newsgroup, mailing list  chaselweng Guest Posts: n/a A Stirling Approximation question....

I read a paper and see below inequality

1/sqrt(2*pi*n) * n^n * exp( -n + 1/(12*n) - 1/(360*n^3) ) <= C(n, l) <=
1/sqrt(2*pi*n) * n^n * exp( -n + 1/ (12*n) )

where C(n,l) means the combination with n!/( l! * (n-l)! )...
I tried to use stirling approximation, but i can't get the same
result....

Can anyone help me for any kinds of comment......

 robert bristow-johnson Guest Posts: n/a Re: A Stirling Approximation question....

chaselweng wrote:
> I read a paper and see below inequality
>
> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/(12*n) - 1/(360*n^3) ) <= C(n, l) <=
> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/ (12*n) )
>
> where C(n,l) means the combination with n!/( l! * (n-l)! )...
> I tried to use stirling approximation, but i can't get the same
> result....
>
> Can anyone help me for any kinds of comment......

there are slightly different formulae for Stirling's approximation,
some are a little more accurate than others, but they all have the same
asymtotic behavior when n gets large. i recommend looking at

http://en.wikipedia.org/wiki/Stirling%27s_approximation

anyway it says that

n! = sqrt(2*pi*n) exp(n*log(n)-n) * exp(lambda)

where 12*n < 1/lambda < 12*n + 1

that's the best approximation and shows the error constraint. i have
also seen

n! approx= exp(n*log(n)-n)

which will also work in most cases when n is super large.

r b-j

 chaselweng Guest Posts: n/a Re: A Stirling Approximation question....

I have refered to the website you provide...
But i still can get the same inequality...

I think a lot of terms are be ignore in the above inequality..
I have no sense what's kinds of term i can ignore with n is large...

Can anyone tell me what's happen in the inequality...thx a lot!!

 robert bristow-johnson Guest Posts: n/a Re: A Stirling Approximation question....

chaselweng wrote:
> I have refered to the website you provide...
> But i still can get the same inequality...
>
> I think a lot of terms are be ignore in the above inequality..
> I have no sense what's kinds of term i can ignore with n is large...

>>> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/(12*n) - 1/(360*n^3) ) <= C(n, l) <=
>>> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/ (12*n) )
>>>
>>> where C(n,l) means the combination with n!/( l! * (n-l)! )...

well, one problem with it is that there is no function of "l" on either
left or right expression. there is no "l" in

1/sqrt(2*pi*n) * n^n * exp(-n + 1/(12*n))

or in

1/sqrt(2*pi*n) * n^n * exp(-n + 1/(12*n) - 1/(360*n^3))

where the 1/(360*n^3) term comes from, i do not know.

again, what Stirling's approximation says most concisely is:

1/(12*n+1) < log(n!) - (1/2)*log(2*pi) - (n+1/2)*log(n) + n < 1/(12*n)

note that the expression gets squeezed between 1/(12*n+1) and 1/(12*n)
as n gets large making the approximation really good for large n.

r b-j

 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are On Forum Rules Similar Threads Thread Thread Starter Forum Replies Last Post chaselweng DSP 0 05-11-2006 03:45 AM chaselweng DSP 0 05-11-2006 03:43 AM Lars Hansen DSP 9 10-06-2005 09:37 PM kiki DSP 4 11-25-2004 04:57 PM MadJock DSP 9 12-16-2003 04:49 PM

All times are GMT +1. The time now is 06:38 AM. Copyright 2008 @ FPGA Central. All rights reserved