Question

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

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

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

In general,

$$^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.013s
user   0m0.013s
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.023s
user   0m0.015s
sys    0m0.008s