module Matchings where

import Data.MemoTrie
import Binomial

-- number of ways to match up k elements with n elements
-- matchings may be partial
matchings :: Int -> Int -> Integer
matchings = memo2 m where
  m n k = if n > k
          then matchings k n
          else sum [ binomial n i * product [fromIntegral (k-i+1) .. fromIntegral k] | i <- [0 .. n]]