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?

$\endgroup$
  • $\begingroup$ How much precision? $\endgroup$ – André Nicolas Jan 5 '12 at 3:02
  • $\begingroup$ @AndréNicolas Correct upto 2^64 - 1. spoj.pl/problems/YODA is the link to the problem. $\endgroup$ – Khushman Patel Jan 5 '12 at 3:07
  • $\begingroup$ Should basically fit in a unsigned long long integer, i.e. 2^64 - 1 $\endgroup$ – Khushman Patel Jan 5 '12 at 3:09
11
$\begingroup$

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.

$\endgroup$
0
$\begingroup$
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<<ans<<endl;
$\endgroup$
  • 1
    $\begingroup$ Welcome to math.Stackexchange. Please give a better formatting in order to be easily readable. $\endgroup$ – Davide Giraudo Mar 28 '13 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.