Problem239 22個の場違いな素数たち

問題

それぞれ1から100まで番号の書かれたディスクが1列に無作為に並んでいる.

ちょうど 22 個の素数の番号のディスクが, 番号順の位置と異なる場所にある確率を求めよ.
(素数でない番号のディスクはどれも番号順の位置にあってもなくてもよい)

解答は小数点以下12桁に四捨五入し,
0.abcdefghijkl の形で求めよ.

ソース

using System;

class Program
{
    static void Main()
    {
        //2と3と5が正位置にある確率
        decimal Answer = 1M / 100M / 99M / 98M;

        //7が正位置にある、または、11が正位置にある、または、13が正位置にある、または、・・・
        //の確率を、包除原理で求める
        decimal OrKakuritu = 0M;
        decimal wkProd = 1M;
        for (int I = 1; I <= 22; I++) {
            //包除原理なので、符号は交互になる
            int wkSign = (I % 2 == 1 ? 1 : -1);

            wkProd *= 1M / (97 - I + 1);

            decimal wkCombi = DeriveCombi(22, I);

            OrKakuritu += wkSign * wkProd * wkCombi;
        }
        Answer *= (1 - OrKakuritu);
        Answer *= DeriveCombi(25, 3);
        Answer = Math.Round(Answer, 12, MidpointRounding.AwayFromZero);
        Console.WriteLine("Answer={0}", Answer);
    }

    //nCrを求める
    static decimal DeriveCombi(int pN, int pR)
    {
        decimal WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        for (int I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
        }
        for (int I = 2; I <= pR; I++) {
            WillReturn /= I;
        }
        return WillReturn;
    }
}

実行結果

Answer=0.001887854841

解説

100以下の素数は25個あります。

2と3と5が正位置にある確率は、
1/100 * 1/99 * 1/98 で求まります。

2と3と5が正位置にあり、
7または11または13または17または19または・・・が正位置にある確率は、
包除原理を使った下記の式で求まりますので、
22C1 * (1/97) - 22C2 * (1/97) * (1/96) + 22C3 * (1/97)*(1/96)*(1/95) ・・・

7または11または13または17または19または・・・が正位置にある事象の余事象の確率を使って、
2と3と5が正位置にあり、他の素数が正位置にない確率が求まります。

正位置にある3つの素数を選ぶ方法は25C3であり、どの2つも互いに排反ですので
(2と3と5が正位置にあり、他の素数が正位置にない確率) * 25C3
が解となります。