# Factorial division using Pascal's triangle.

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?

• 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

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.

int fac[tot+1];
fac=fac=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;

• Welcome to math.Stackexchange. Please give a better formatting in order to be easily readable. – Davide Giraudo Mar 28 '13 at 14:50