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

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

• To: "pari-users@pari.math.u-bordeaux.fr" <pari-users@pari.math.u-bordeaux.fr>
• Subject: Fwd: Need permutation help for n!/(n-r)!
• From: Dirk Laurie <dirk.laurie@gmail.com>
• Date: Sun, 26 Jun 2016 10:47:19 +0200
• Delivery-date: Sun, 26 Jun 2016 10:47:28 +0200
• References: <CAC6O5f6gMxbvp72fUGGrqe0ChkBBV0zXa=OPq=pPU154FuEg=A@mail.gmail.com> <CABcj=tn-W-2hiLzvRr1Gu2CtEf=L6EJQeKrpfOdFKLSt1PfNOA@mail.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.

? 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

```