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.000sPython
#!/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