読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 239 / 場違いな素数たち

それぞれ 1 から 100 まで番号の書かれたディスクが一列に無作為に並んでいる。ちょうど 22 個の素数の番号のディスクが番号順の位置と異なる場所にある確率を求めよ。素数でない番号のディスクはどれも番号順の位置にあってもなくてもよい。

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

Problem 239 - Project Euler


完全順列(攪乱順列)の問題です。
完全順列 - Wikipedia

100以下の素数は25個。25-22=3 個は正しい場所にあります。この素数の選び方は
C[25,3] 通り。

残りの数については素数→男子,非素数→女子と言い換えて考えます。全97人中男子が22人いて,その22人は誰も自分の席に座らない方法は何通りあるか? 男子が r 人,女子が n-r 人のときの場合の数を f(n,r) であらわします。

■男子rが男子席i (1≦i≦r-1)に座るとき

男子iが男子席rに座る(男子rと男子iが席を交換する)とき,残りの人の座り方は
f(n-2,r-2) 通り。

男子iが男子席rに座らないとき,この男子iは自分の席には座りませんが,「男子席rに座らない」という制約がある点で他の男子と同じです。この場合は
f(n-1, r-1) 通り。

■男子rが女子席i (1≦i≦n-r)に座るとき

女子iは「女子席iに座らない」という制約がある点で男子と同じです。この場合は
f(n-1, r-1) 通り。

以上をまとめます。

f(n,r)
=(r-1){f(n-2,r-2)+f(n-1, r-1)}+(n-r)f(n-1, r-1)
=(r-1)f(n-2,r-2)+(n-1)f(n-1, r-1)

あとは Mathematica に頑張ってもらいましょう。