## Question

There are exactly ten ways of selecting three from five, 12345:

$\displaystyle 123, 124, 125, 134, 135, 145, 234, 235, 245, \text{ and } 345$

In combinatorics, we use the notation, $^5C_3 = 10$.

In general,

$\displaystyle ^nC_r = \frac{n!}{r!(n-r)!}, \text{ where } r \leq n, n! = n\times(n-1)\times...\times3\times2\times1, \text{ and } 0! = 1.$

It is not until $n = 23$, that a value exceeds one-million: $^{23}C_{10} = 1144066$.

How many, not necessarily distinct, values of $^nC_r$, for $1 \leq n \leq 100$, are greater than one-million?

## Haskell

choose :: Integer -> Integer -> Integer
choose _ 0 = 1
choose 0 _ = 0
choose n r = choose (n-1) (r-1) * n div r

main :: IO ()
main = print $length$ filter (> 1000000) [n choose r | n <- [1..100], r <- [1..n]]
$ghc -O2 -o combinatoric-selections combinatoric-selections.hs$ time ./combinatoric-selections
real   0m0.019s
user   0m0.016s
sys    0m0.000s

## Python

#!/usr/bin/env python
from gmpy2 import comb
count = 0
for n in range(1, 101):
for r in range(1, n):
c = comb(n,r)
if c > 1000000:
count += 1
print(count)
\$ time python3 large-combos.py
real   0m0.026s
user   0m0.024s
sys    0m0.000s

Questions? Comments? Send me an email: z@chdenton.com