A set of approximations the central binomial coefficient - sci.math

Message from discussion A set of approximations the central binomial coefficient

David W. Cantrell

View profile

More options Jul 6, 7:38 pm

Newsgroups: sci.math

From: David W. Cantrell <DWCantr...@sigmaxi.net>

Date: 06 Jul 2008 14:38:15 GMT

Local: Sun, Jul 6 2008 7:38 pm

Subject: Re: A set of approximations the central binomial coefficient

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

"sa...@kt-algorithms.com" <sa...@kt-algorithms.com> wrote:
> An interesting type of approximation to the central binomial
> coefficient is of the form:

> C(2n, n) ~= 4^n / sqrt( Rm(n) )

> Rm being a rational function of max. degree m+1 (m>0):

> Rm(n) = (pi n^(m+1) + sum(i=0,m) Pi n^i) / (n^m + sum(i=0,m-1) Qi n^i)

> and where the 2m+1 coefficients are defined by simply requiring exact
> results for 2m>=n>=0; note that C(0,0)=1 implies that Q0=P0.

Hello, Knud!

Yes, your form of approximation is nice.

FWIW, here are simple upper and lower bounds for C(2n, n).

Upper bound: 4^n / sqrt(pi(n + 1/4)) (Ub)

Lower bound: Ub * (1 - 1/(8(n + 1/4))^2) (Lb)

Your approximations are precise for small n, while the relative errors of
my bounds at n = 0 are roughly 13% and -15%, resp. But for large n, those
bounds make reasonably good approximations. For example, at n = 50, their
relative errors are about 6*10^-6 and -4*10^-10, resp.

Best regards,
David W. Cantrell

> Example: m=1
> ------------

> C(2n, n) ~= 4^n / sqrt( (pi n^2 + P1 n + P0)/ (n + Q0) )

> P1 = 53 pi - 164
> P0 = 18 pi - 56
> Q0 = P0

> with a |rel. error| < 5.0*10^-5 for n>=0.

> Error profile:

> n rel. error n rel. error
> ----------------------------------------
> 0 0 12 4.023*10^-5
> 1 0 13 3.845*10^-5
> 2 0 14 3.678*10^-5
> 3 2.923*10^-5 15 3.521*10^-5
> 4 4.312*10^-5 16 3.375*10^-5
> 5 4.850*10^-5 17 3.239*10^-5
> 6 4.983*10^-5 18 3.112*10^-5
> 7 4.927*10^-5 19 2.994*10^-5
> 8 4.782*10^-5 20 2.884*10^-5
> 9 4.600*10^-5 30 2.096*10^-5
> 10 4.406*10^-5 40 1.641*10^-5
> 11 4.211*10^-5 50 1.346*10^-5

> Example: m=2
> ------------

> C(2n, n) ~= 4^n / sqrt( (pi n^3 + P2 n^2 + P1 n + P0)/ (n^2 + Q1
> n + Q0) )

> P2 = 36928 - 11753 pi
> P1 = 30784 - 9798 pi
> P0 = 6912 - 2200 pi
> Q1 = 11743 - 7475 pi/2
> Q0 = P0

> with a |rel. error| < 2.5*10^-7 for n>=0.

> Error profile:

> n rel. error n rel. error
> ----------------------------------------
> 0 0 12 -2.323*10^-7
> 1 0 13 -2.390*10^-7
> 2 0 14 -2.431*10^-7
> 3 0 15 -2.453*10^-7
> 4 0 16 -2.459*10^-7
> 5 -3.706*10^-8 17 -2.454*10^-7
> 6 -8.367*10^-8 18 -2.440*10^-7
> 7 -1.263*10^-7 19 -2.420*10^-7
> 8 -1.611*10^-7 20 -2.394*10^-7
> 9 -1.879*10^-7 30 -2.053*10^-7
> 10 -2.078*10^-7 40 -1.740*10^-7
> 11 -2.222*10^-7 50 -1.496*10^-7

> Best regards,

> Knud Thomsen

Reply to author Forward