3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
4 <title>Binomial Coefficients</title>
5 <link rel="stylesheet" href="../../math.css" type="text/css">
6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
7 <link rel="home" href="../../index.html" title="Math Toolkit 2.1.0">
8 <link rel="up" href="../factorials.html" title="Factorials and Binomial Coefficients">
9 <link rel="prev" href="sf_falling_factorial.html" title="Falling Factorial">
10 <link rel="next" href="../sf_beta.html" title="Beta Functions">
12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
13 <table cellpadding="2" width="100%"><tr>
14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
22 <div class="spirit-nav">
23 <a accesskey="p" href="sf_falling_factorial.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../factorials.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_beta.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
26 <div class="titlepage"><div><div><h3 class="title">
27 <a name="math_toolkit.factorials.sf_binomial"></a><a class="link" href="sf_binomial.html" title="Binomial Coefficients">Binomial Coefficients</a>
28 </h3></div></div></div>
29 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">binomial</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
31 <pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span>
33 <span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">></span>
34 <span class="identifier">T</span> <span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">k</span><span class="special">);</span>
36 <span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <a class="link" href="../../policy.html" title="Chapter 14. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">></span>
37 <span class="identifier">T</span> <span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">k</span><span class="special">,</span> <span class="keyword">const</span> <a class="link" href="../../policy.html" title="Chapter 14. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&);</span>
39 <span class="special">}}</span> <span class="comment">// namespaces</span>
42 Returns the binomial coefficient: <sub>n</sub>C<sub>k</sub>.
48 The final <a class="link" href="../../policy.html" title="Chapter 14. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can
49 be used to control the behaviour of the function: how it handles errors,
50 what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter 14. Policies: Controlling Precision, Error Handling etc">policy
51 documentation for more details</a>.
54 May return the result of <a class="link" href="../error_handling.html#math_toolkit.error_handling.overflow_error">overflow_error</a>
55 if the result is too large to represent in type T.
57 <div class="important"><table border="0" summary="Important">
59 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Important]" src="../../../../../../doc/src/images/important.png"></td>
60 <th align="left">Important</th>
62 <tr><td align="left" valign="top">
64 The functions described above are templates where the template argument
65 T can not be deduced from the arguments passed to the function. Therefore
66 if you write something like:
69 <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="number">10</span><span class="special">,</span> <span class="number">2</span><span class="special">);</span></code>
72 You will get a compiler error, ususally indicating that there is no such
73 function to be found. Instead you need to specifiy the return type explicity
77 <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">binomial_coefficient</span><span class="special"><</span><span class="keyword">double</span><span class="special">>(</span><span class="number">10</span><span class="special">,</span> <span class="number">2</span><span class="special">);</span></code>
80 So that the return type is known. Further, the template argument must be
81 a real-valued type such as <code class="computeroutput"><span class="keyword">float</span></code>
82 or <code class="computeroutput"><span class="keyword">double</span></code> and not an integer
83 type - that would overflow far too easily!
88 <a name="math_toolkit.factorials.sf_binomial.h0"></a>
89 <span class="phrase"><a name="math_toolkit.factorials.sf_binomial.accuracy"></a></span><a class="link" href="sf_binomial.html#math_toolkit.factorials.sf_binomial.accuracy">Accuracy</a>
92 The accuracy will be the same as for the factorials for small arguments (i.e.
93 no more than one or two epsilon), and the <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>
94 function for larger arguments.
97 <a name="math_toolkit.factorials.sf_binomial.h1"></a>
98 <span class="phrase"><a name="math_toolkit.factorials.sf_binomial.testing"></a></span><a class="link" href="sf_binomial.html#math_toolkit.factorials.sf_binomial.testing">Testing</a>
101 The spot tests for the binomial coefficients use data generated by functions.wolfram.com.
104 <a name="math_toolkit.factorials.sf_binomial.h2"></a>
105 <span class="phrase"><a name="math_toolkit.factorials.sf_binomial.implementation"></a></span><a class="link" href="sf_binomial.html#math_toolkit.factorials.sf_binomial.implementation">Implementation</a>
108 Binomial coefficients are calculated using table lookup of factorials where
112 <sub>n</sub>C<sub>k</sub> = n! / (k!(n-k)!)
115 Otherwise it is implemented in terms of the beta function using the relations:
118 <sub>n</sub>C<sub>k</sub> = 1 / (k * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k,
125 <sub>n</sub>C<sub>k</sub> = 1 / ((n-k) * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k+1,
129 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
130 <td align="left"></td>
131 <td align="right"><div class="copyright-footer">Copyright © 2006-2010, 2012-2014 Nikhar Agrawal,
132 Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
133 Holin, Bruno Lalande, John Maddock, Johan Råde, Gautam Sewani, Benjamin Sobotta,
134 Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
135 Distributed under the Boost Software License, Version 1.0. (See accompanying
136 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
141 <div class="spirit-nav">
142 <a accesskey="p" href="sf_falling_factorial.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../factorials.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_beta.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>