random_function_short_period_probability.hs

import Data.Ratio

fact :: Integer -> Integer
fact 0 = 1
fact n = (fact (n - 1)) * n

solve2 :: Integer -> Rational
solve2 m = sum $ map (\k -> sum [term r s | r <- [0..m], s <- [0..m], r + s == k && r + 2 * s <= m]) [1..m]
  where term r s = (-1)^(r+s-1)%(2^s*(fact r)*(fact s))*(product [1-i%m | i <- [0..r+2*s-1]])

solve3 :: Integer -> Rational
solve3 m = sum $ map (\k -> sum [term r1 r2 r3 | r1 <- [0..m], r2 <- [0..m], r3 <- [0..m], r1 + r2 + r3 == k && r1 + 2 * r2 + 3 * r3 <= m]) [1..m]
  where term r1 r2 r3 = (-1)^(r1+r2+r3-1)%(2^r2*3^r3*(fact r1)*(fact r2)*(fact r3))*(product [1-i%m | i <- [0..r1 + 2 * r2 + 3 * r3-1]])