1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.12.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"> 11</head> 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> 20</tr></table> 21<hr> 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> 24</div> 25<div class="section"> 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> 30</pre> 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> 32 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> 35 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 21. 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 21. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&);</span> 38 39<span class="special">}}</span> <span class="comment">// namespaces</span> 40</pre> 41<p> 42 Returns the binomial coefficient: <sub>n</sub>C<sub>k</sub>. 43 </p> 44<p> 45 Requires k <= n. 46 </p> 47<p> 48 The final <a class="link" href="../../policy.html" title="Chapter 21. 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 21. Policies: Controlling Precision, Error Handling etc">policy 51 documentation for more details</a>. 52 </p> 53<p> 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. 56 </p> 57<div class="important"><table border="0" summary="Important"> 58<tr> 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> 61</tr> 62<tr><td align="left" valign="top"> 63<p> 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 67 like: 68 </p> 69<p> 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> 71 </p> 72<p> 73 You will get a compiler error, usually indicating that there is no such 74 function to be found. Instead you need to specify the return type explicitly 75 and write: 76 </p> 77<p> 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> 79 </p> 80<p> 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! 85 </p> 86</td></tr> 87</table></div> 88<h5> 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> 91 </h5> 92<p> 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. 96 </p> 97<h5> 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> 100 </h5> 101<p> 102 The spot tests for the binomial coefficients use data generated by <a href="http://www.wolframalpha.com/" target="_top">Wolfram Alpha</a>. 103 </p> 104<h5> 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> 107 </h5> 108<p> 109 Binomial coefficients are calculated using table lookup of factorials where 110 possible using: 111 </p> 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> 115<p> 116 Otherwise it is implemented in terms of the beta function using the relations: 117 </p> 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> 122<p> 123 and 124 </p> 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> 129</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>) 139 </p> 140</div></td> 141</tr></table> 142<hr> 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> 145</div> 146</body> 147</html> 148
