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.79.1">
7 <link rel="home" href="../../index.html" title="Math Toolkit 2.11.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 20. 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 20. 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 20. 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 20. 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 <code class="computeroutput"><span class="identifier">T</span></code> can not be deduced from
66 the arguments passed to the function. Therefore if you write something
70 <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>
73 You will get a compiler error, ususally indicating that there is no such
74 function to be found. Instead you need to specifiy the return type explicity
78 <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>
81 So that the return type is known. Further, the template argument must be
82 a real-valued type such as <code class="computeroutput"><span class="keyword">float</span></code>
83 or <code class="computeroutput"><span class="keyword">double</span></code> and not an integer
84 type - that would overflow far too easily!
89 <a name="math_toolkit.factorials.sf_binomial.h0"></a>
90 <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>
93 The accuracy will be the same as for the factorials for small arguments (i.e.
94 no more than one or two epsilon), and the <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>
95 function for larger arguments.
98 <a name="math_toolkit.factorials.sf_binomial.h1"></a>
99 <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>
102 The spot tests for the binomial coefficients use data generated by <a href="http://www.wolframalpha.com/" target="_top">Wolfram Alpha</a>.
105 <a name="math_toolkit.factorials.sf_binomial.h2"></a>
106 <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>
109 Binomial coefficients are calculated using table lookup of factorials where
112 <div class="blockquote"><blockquote class="blockquote"><p>
113 <span class="serif_italic"><span class="emphasis"><em><sub>n</sub>C<sub>k</sub> = n! / (k!(n-k)!)</em></span></span>
114 </p></blockquote></div>
116 Otherwise it is implemented in terms of the beta function using the relations:
118 <div class="blockquote"><blockquote class="blockquote"><p>
119 <span class="serif_italic"><span class="emphasis"><em><sub>n</sub>C<sub>k</sub> = 1 / (k * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k,
120 n-k+1))</em></span></span>
121 </p></blockquote></div>
125 <div class="blockquote"><blockquote class="blockquote"><p>
126 <span class="serif_italic"><span class="emphasis"><em><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,
127 n-k))</em></span></span>
128 </p></blockquote></div>
130 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
131 <td align="left"></td>
132 <td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar
133 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
134 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan
135 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg,
136 Daryle Walker and Xiaogang Zhang<p>
137 Distributed under the Boost Software License, Version 1.0. (See accompanying
138 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>)
143 <div class="spirit-nav">
144 <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>