Combinations

Question:Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.So given 5<=N<=100 5<=M<=100 and M<=N.Compute the EXACT value of: N!/(M!*(N-M)!) The final value of C will fit in a 32-bit Pascal LongInt or a C long. So deduce an approach based on this assumption given.

Solution:At a mere glance,this problem may seem to have a direct solution,though it isn't upon a long thought.The naive approach to calculate combination of N things taken M at a time is obtained by mere application of formula,which mean finding N! ,M! and (N-M)! and the putting them in the expression.But as N and M are independently large enough for overflows to occur in N! and M! calculations.
One of the approaches to solve this problem,based on prime factorization can be formulated in the following manner.

Consider a prime P whose exponents in N!,M! and (N-M)! are p1,p2 and p3 respectively.

therefore the exponent of P in N!/M!*(N-M)! is p1+p2-p3.

This way we can store the exponents of all primes <= the largest prime which divides N.

One this is done ,we can merely multiply all these primes each raised to its exponent to get the required answer.


Now getting on to the tricky part of finding the exponent of a prime P in N!

In general ,if P is any prime,then the no of P's in N! is given by
Sum (floor(n/P^i)) for P^i <= N This apparently weird formula can be explained with ease!! consider the numbers 1,2,3,.........,,N.Every Pth number is divisible by P.So all those multiples of P put together contribute floor(N/P) to the power of P. Similarly every P^2th number is divisible by P^2.And each of them have already contributed 1 to power of P in previous iteration,as each of them are divisible by P.So each of them contribute an additional 1, which means they all together contribute floor(N/P^2) to the already sum. These terms of contribution go on till we have P^i <= N,hence the summation Sum (floor(N/P^i)) for P^i <= N The Cpp implementation of above task is given below

#include<iostream>
using namespace std;
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<vector>
typedef vector<int> powers;
void insert(vector<powers> &P,int i,vector<int> V,int size)
{
       vector<int> temp=P[i-1];
        //calculation of exponent of each prime
       for(int j=0;j <size && i!=1;j++)
       {
               while(i%V[j]==0)
               {
                       temp[j]++;
                       i/=V[j];
               }
       }
       P.push_back(temp);
}
int main()
{
       vector<int> V;
       vector<powers> P;
       V.push_back(2);
       bool flag;
       int N,R;
       for(int i=3;i<100;i+=2)
       {
               flag=true;
               for(int j=0;V[j]*V[j] <=i;j++)
               {
                       if(i%V[j]==0)
                       {
                               flag=false;
                               break;
                       }
               }
               if(flag)
               {
                       V.push_back(i);
               }
       }
       int size=V.size();
       vector<int> temp(size,0);
       P.push_back(temp);
       P.push_back(temp);
       for(int i=2;i<=100;i++)
       {
               insert(P,i,V,size);
       }
       while(cin >> N >>R)
       {
               if(N==0 && R==0)
               {
                       return(0);
               }
               else
               {
                       long sol=1;
                       for(int i=0;i<size;i++)
                       {
               sol*=(long)pow((double)V[i],P[N][i]-P[R][i]
                    -P[N-R][i]); //Pi^(p1-p2-p3)
                       }
                       cout<<N<<" things taken 
                       "<<R<<" at a time is 
                       "<<sol<<" exactly."<<'\n';

               }

       }
       return(0);
}

Click Here for More questions