diff options
Diffstat (limited to 'haskell/053-combinatoric_selections.hs')
| -rw-r--r-- | haskell/053-combinatoric_selections.hs | 19 |
1 files changed, 19 insertions, 0 deletions
diff --git a/haskell/053-combinatoric_selections.hs b/haskell/053-combinatoric_selections.hs new file mode 100644 index 0000000..0fc1211 --- /dev/null +++ b/haskell/053-combinatoric_selections.hs @@ -0,0 +1,19 @@ +-- There are exactly ten ways of selecting three from five, 12345: +-- +-- 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345 +-- +-- In combinatorics, we use the notation, 5C3=10. +-- +-- In general, nCr= n! / r!(n−r)!, where r≤n, n!=n×(n−1)×...×3×2×1, and 0!=1. +-- +-- It is not until n=23, that a value exceeds one-million: 23C10=1144066. +-- +-- How many, not necessarily distinct, values of nCr for 1≤n≤100, are greater than one-million? + + +main = do + print (length [pascal n r | n <- [1..100], r <- [1..n], pascal n r > 1000000]) + +pascal :: Integer -> Integer -> Integer +pascal _ 0 = 1 +pascal n k = (pascal n (k - 1)) * (n + 1 - k) `div` k |