239 Twenty-two Foolish Primes

Problem 239 – Project Euler

確率の問題．

ちょっと，混乱した．

22個同じなのか，22個違うのか，とか．

確率は難しいです．

とりあえず3つの素数を固定．

残り，22個が異なる位置になる確率を考えた．

これは，少なくとも一つの素数が同じ位置にある確率が分かれば求まる．

簡単に分かるのは，

少なくとも，注目している素数が同じ位置にある確率．

欲しいのは，どの素数か区別するすることなく，少なくとも一つの素数が同じ位置にある確率．

ということで，和集合の確率が分かれば良いと． 

import Data.Ratio (Ratio, (%))
choose :: (Integral a) => a -> a -> a
choose n r = div (product [n-r+1..n]) $ product [1..r]
f :: (Integral a) => a -> a -> a
f p c = sum [ (-1) ^ k * product [1.. p + c - k] * choose p k| k <- [..p] ]
p239 :: (Integral a) => a -> Ratio a
p239 n = f n 75 * choose 25 n % product [1..100]
main :: IO ()
main = print.realToFrac.p239 $ 22

包除原理を利用．

ようやく全問解くことができた．できれば4月前に達成したかった．

次はどんな問題か楽しみ．