*[[Problem 483:http://projecteuler.net/problem=483]] 「反復置換」 [#ne7d585b]

要素 {1, 2, 3, ..., n} の順番を並べ替える操作を''置換''と定義しよう.
そのような置換は n! 個あり, そのうちの1つはそれらの要素を当初の順番のままにしておく.
n = 3 のとき 3! = 6 個の置換がある:

- P&sub{1}; = 当初の順番を保持
- P&sub{2}; = 1番目と2番目の要素を入れ替える
- P&sub{3}; = 1番目と3番目の要素を入れ替える
- P&sub{4}; = 2番目と3番目の要素を入れ替える
- P&sub{5}; = 要素を右方向に循環させる
- P&sub{6}; = 要素を左方向に循環させる

これらの置換から一つを選び, %%%同じ%%%置換を繰り返し再適用すると, 最終的に当初の順番に戻る. ある置換 P&sub{i}; に対し, 置換 P&sub{i}; を繰り返し適用して当初の順番に戻るまでに必要な回数を f(P&sub{i};) としよう.~
n = 3 のとき, このようになる:
- f(P&sub{1};) = 1 : (1,2,3) → (1,2,3)
- f(P&sub{2};) = 2 : (1,2,3) → (2,1,3) → (1,2,3)
- f(P&sub{3};) = 2 : (1,2,3) → (3,2,1) → (1,2,3)
- f(P&sub{4};) = 2 : (1,2,3) → (1,3,2) → (1,2,3)
- f(P&sub{5};) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)
- f(P&sub{6};) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3) 

長さ n の全ての置換 P&sub{i}; に対し f&sup{2};(P&sub{i};) の平均値を g(n) としよう.

g(3) = (1&sup{2}; + 2&sup{2}; + 2&sup{2}; + 2&sup{2}; + 3&sup{2}; + 3&sup{2};)/3! = 31/6 ≈ 5.166666667e0~
g(5) = 2081/120 ≈ 1.734166667e1~
g(20) = 12422728886023769167301/2432902008176640000 ≈ 5.106136147e3~

g(350) を求め, 有効数字が10桁になるよう四捨五入して科学的記数法によって回答を記入せよ, 例のように仮数部と指数部のセパレーターには小文字のeを使うこと.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS