[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

### 15.7.3 Binomial Coefficients

Binomial coefficients *C(n,k)* are calculated
by first arranging *k <= n/2* using *C(n,k) = C(n,n-k)* if necessary, and then
evaluating the following product simply from *i=2* to *i=k*.

k (n-k+i) C(n,k) = (n-k+1) * prod ------- i=2 i

It’s easy to show that each denominator *i* will divide the product so
far, so the exact division algorithm is used (see section Exact Division).

The numerators *n-k+i* and denominators *i* are first accumulated
into as many fit a limb, to save multi-precision operations, though for
`mpz_bin_ui`

this applies only to the divisors, since *n* is an
`mpz_t`

and *n-k+i* in general won’t fit in a limb at all.

This document was generated on *March 31, 2014* using *texi2html 5.0*.