Multinomial coefficient code always delivers the same answer

Question

I have written the following code in order to find the multinomial coefficient, however the same answer, 2.122e-314, always comes out. I've been sitting on this for a while now, and can't find what is missing. We are supposed to do this using recursions. My code is as follows:

#include<iostream>
#include<vector>
#include<cerrno>
#include<cstring>

using namespace std;

double binom(int n,int a)
{
double b;
double i;
for (b = 1, i = 1;i <= a; ++i, --n)
        b *= n/i;
return b;
}

double multi(int n, vector<int> a)
{
double b;
int s1 = n;
for ( int s1 = n, b = 1, i = 0; i <= a.size(); ++i, s1 = s1 - a[i-1] )
    b *= binom(s1, a[i]);
return b;
}



int main()
{
int n, k; 
cout << "dimension k: ";
cin >> k;
vector<int> a(k);
cout << "n: ";
cin >> n;
cout << "a[0],...,a[k-1]: ";
for (int i = 0; i < k; ++i)
cin >> a[i];
cout << "Multinomialcoefficient: " << multi(n,a) << endl;
return 0;
}

Any help is greatly appreciated.

Answer 1

Problem 1

You are performing integer divisions in the line

  b *= n/i;

Change it to

  b *= 1.0*n/i;

Problem 2

This is an insidious problem.

double b;
int s1 = n;
for ( int s1 = n, b = 1, i = 0; i <= a.size(); ++i, s1 = s1 - a[i-1] )
  b *= binom(s1, a[i]);
return b;

The b in the loop, where you use b = 1, is unfortunately not the same b declared at the start of the function. Since you use int s1 = n, b = 1,, the b in the loop is a separate variable, of type int, defined in the scope of the loop. Consequently, the b declared at the top of the function is uninitialized and that is the one you return from the function.

Increasing warning level of your compiler might have revealed that problem. With g++ -Wall, I get the following warning.

socc.cc:23:11: warning: ‘b’ is used uninitialized in this function [-Wuninitialized]
    return b;

       ^

Change that function to:

double multi(int n, vector<int> a)
{
   // Initialize all the variables. Then, the init part of the loop can be empty.
   double b = 1;
   int s1 = n;
   int i = 0;

   for ( ; i <= a.size(); ++i, s1 = s1 - a[i-1] )
      b *= binom(s1, a[i]);
   return b;
}