Math.Combinatorics.Binomial

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

Documentation

choose :: Integral a => a -> a -> a

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.

• P. Goetgheluck (1987) Computing Binomial Coefficients, American Mathematical Monthly, 94(4). pp.360--365. http://www.jstor.org/stable/2323099, http://dl.acm.org/citation.cfm?id=26272