Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Binomial Coefficients

#include <boost/math/special_functions/binomial.hpp>
namespace boost{ namespace math{

template <class T>
T binomial_coefficient(unsigned n, unsigned k);

template <class T, class Policy>
T binomial_coefficient(unsigned n, unsigned k, const Policy&);

}} // namespaces

Returns the binomial coefficient: nCk.

Requires k <= n.

The final Policy argument is optional and can be used to control the behaviour of the function: how it handles errors, what level of precision to use etc. Refer to the policy documentation for more details.

May return the result of overflow_error if the result is too large to represent in type T.

[Important] Important

The functions described above are templates where the template argument T can not be deduced from the arguments passed to the function. Therefore if you write something like:

boost::math::binomial_coefficient(10, 2);

You will get a compiler error, ususally indicating that there is no such function to be found. Instead you need to specifiy the return type explicity and write:

boost::math::binomial_coefficient<double>(10, 2);

So that the return type is known. Further, the template argument must be a real-valued type such as float or double and not an integer type - that would overflow far too easily!

Accuracy

The accuracy will be the same as for the factorials for small arguments (i.e. no more than one or two epsilon), and the beta function for larger arguments.

Testing

The spot tests for the binomial coefficients use data generated by functions.wolfram.com.

Implementation

Binomial coefficients are calculated using table lookup of factorials where possible using:

nCk = n! / (k!(n-k)!)

Otherwise it is implemented in terms of the beta function using the relations:

nCk = 1 / (k * beta(k, n-k+1))

and

nCk = 1 / ((n-k) * beta(k+1, n-k))


PrevUpHomeNext