4
$\begingroup$

I want to get values of factorial divisions such as 100!/(2!5!60!)(the numbers in the denominator will all be smaller than the numerator, and the sum of the denominators(numbers without factorial) can be at max 100) etc.

I read in a forum that a Pascal's triangle can be used for calculating such results, but a lot of searching didn't tell me how to do so.

It is actually for a programming problem, and I tried using the lgamma function to calculate the value, but that gives an error as I need a lot of precision.

So what could be used to calculate such factorial divisions?

  • 0
    Should basically fit in a `unsigned long long integer`, i.e. `2^64 - 1`2012-01-05

2 Answers 2

11

You can express those in terms of binomial coefficients and factorials.

$\binom{n}{k} = \frac{n!}{k! (n-k)!}$

For example

$\frac{100!}{60! 5! 2!} = \frac{100!}{60! 40!} \cdot \frac{40!}{5! 35!} \cdot \frac{35!}{2! 33!} \cdot 33! = \binom{100}{60} \cdot \binom{40}{5} \cdot \binom{35}{2} \cdot 33!$

Or more generally, if $a_1 \ge a_2 \ge \cdots \ge a_k$ and $a_1 + \cdots + a_k \le n$, we have

$\frac{n!}{a_1! a_2! \ldots a_k!} = \binom{n}{a_1} \cdot \binom{n-a_1}{a_2} \ldots \binom{n-a_1-\cdots-a_{n-1}}{a_n} \cdot (n-a_1-\cdots-a_{n})!$

And binomial coefficients are easily computed (without division) using Pascal's triangle relation.

0
int fac[tot+1];         fac[0]=fac[1]=1;         for(i=2;i<=tot;i++)         fac[i]=i;         for(i=0;i<26;i++)         {             if(num[i]>1)             {                 for(j=2;j<=num[i];j++)                 {                     for(k=j;k<=tot;k=k+j)                     {                         if(fac[k]%j==0)                         {                             fac[k]=k/j;                             break;                         }                     }                 }             }         }         unsigned long long ans=1;         for(i=2;i<=tot;i++)         ans=ans*fac[i];         cout<
  • 1
    Welcome to math.Stackexchange. Please give a better formatting in order to be easily readable.2013-03-28