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

[Dirk Laurie <dirk.laurie@gmail.com>]

---------- 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