Dirk Laurie on Sun, 26 Jun 2016 10:47:28 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Fwd: Need permutation help for n!/(n-r)!


---------- Forwarded message ----------
From: Dirk Laurie <dirk.laurie@gmail.com>
Date: 2016-06-26 10:46 GMT+02:00
Subject: Re: Need permutation help for n!/(n-r)!
To: chandra sekaran <sekar.bc@gmail.com>


2016-06-26 8:19 GMT+02:00 chandra sekaran <sekar.bc@gmail.com>:

> If n and r big number(n=600,r=25) it will take long time to find.
>
> (11:39) gp > 600!/(600-25)!
> %59 = 1712444741995872743767068314898968290507882039321992936466415616000000
>
> Is there any efficient algorithm for solving above problem or not.

If as in that example r is small compared to n, you can iterate
on r, replace the factorials by Stirling's approximation, solve
numerically for n, and if the result is close enough to an
integer to be interesting, check it with exact factorials.

For very small r, sfac(n) overflows. Exercise for the reader:
write an equivalent function for sbinom that does not overflow.

In your example, with c=...

? sfac(n)=(n/exp(1))^n*sqrt(n); \\ factor sqrt(2*Pi) cancels
? sbinom(n,r) = sfac(n)/sfac(n-r);
? initn(c,n,r) = c^(1/r)+(r-1)/2;
? {for(r=6,30,n0=initn(c,n,r);
n1=solve(x=n0-0.5,n0+0.5,sbinom(x,r)-c);
n=round(n1);
err=n1-n;
if(abs(err)<0.05, if(r!*binomial(n,r)==c,
print("r=",r,"  n=",n))  ))  }
r=25  n=600