Problem 483 「反復置換」

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

  • P1 = 当初の順番を保持
  • P2 = 1番目と2番目の要素を入れ替える
  • P3 = 1番目と3番目の要素を入れ替える
  • P4 = 2番目と3番目の要素を入れ替える
  • P5 = 要素を右方向に循環させる
  • P6 = 要素を左方向に循環させる

これらの置換から一つを選び, 同じ置換を繰り返し再適用すると, 最終的に当初の順番に戻る. ある置換 Pi に対し, 置換 Pi を繰り返し適用して当初の順番に戻るまでに必要な回数を f(Pi) としよう.
n = 3 のとき, このようになる:

  • f(P1) = 1 : (1,2,3) → (1,2,3)
  • f(P2) = 2 : (1,2,3) → (2,1,3) → (1,2,3)
  • f(P3) = 2 : (1,2,3) → (3,2,1) → (1,2,3)
  • f(P4) = 2 : (1,2,3) → (1,3,2) → (1,2,3)
  • f(P5) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)
  • f(P6) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3)

長さ n の全ての置換 Pi に対し f2(Pi) の平均値を g(n) としよう.

g(3) = (12 + 22 + 22 + 22 + 32 + 32)/3! = 31/6 ≈ 5.166666667e0
g(5) = 2081/120 ≈ 1.734166667e1
g(20) = 12422728886023769167301/2432902008176640000 ≈ 5.106136147e3

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


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-11-18 (金) 23:53:08 (336d)