Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
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;
share|improve this answer
1  
Welcome to math.Stackexchange. Please give a better formatting in order to be easily readable. –  Davide Giraudo Mar 28 '13 at 14:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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