exact-combinatorics-0.2.0.11: Efficient exact computation of combinatoric functions.

Math.Combinatorics.Exact.Binomial

Description

Binomial coefficients (http://oeis.org/A007318), aka the count of possible combinations. For negative inputs, all functions return 0 (rather than throwing an exception or using Maybe).

Synopsis

# Documentation

choose :: Integral a => a -> a -> a Source #

Exact binomial coefficients. For a fast approximation see math-functions:Numeric.SpecFunctions.choose instead. The naive definition of the binomial coefficients is:

n choose k
| k < 0     = 0
| k > n     = 0
| otherwise = factorial n div (factorial k * factorial (n-k))

However, we use a fast implementation based on the prime-power factorization of the result (Goetgheluck, 1987). Each time n is larger than the previous calls, there will be some slowdown as the prime numbers must be computed (though it is still much faster than the naive implementation); however, subsequent calls will be extremely fast, since we memoize the list of primes. Do note, however, that this will result in a space leak if you call choose for an extremely large n and then don't need that many primes in the future. Hopefully future versions will correct this issue.