module Binomial where

import Data.MemoTrie

-- binomial coefficients
binomial :: Int -> Int -> Integer
binomial = memo2 b where
    b n k = if k > n
            then 0
            else if n <= 5
                 then table !! n !! k
                 else binomial (n-1) k + binomial (n-1) (k-1)
    table = [ [1]
            , [1, 1]
            , [1, 2, 1]
            , [1, 3, 3, 1]
            , [1, 4, 6, 4, 1]
            , [1, 5, 10, 10, 5, 1] ]