0%

Problem 483


Problem 483


Repeated permutation

We define a permutation as an operation that rearranges the order of the elements {1, 2, 3, …, n}. There are n! such permutations, one of which leaves the elements in their initial order. For n = 3 we have 3! = 6 permutations:

  • P1 = keep the initial order  
  • P2 = exchange the 1st and 2nd elements  
  • P3 = exchange the 1st and 3rd elements 
  • P4 = exchange the 2nd and 3rd elements 
  • P5 = rotate the elements to the right  
  • P6 = rotate the elements to the left  

If we select one of these permutations, and we re-apply the same permutation repeatedly, we eventually restore the initial order.
For a permutation Pi, let f(Pi) be the number of steps required to restore the initial order by applying the permutation Pi repeatedly.
For n = 3, we obtain:

  • 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)

Let g(n) be the average value of f2(Pi) over all permutations Pi of length n.

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

Find g(350) and write the answer in scientific notation rounded to 10 significant digits, using a lowercase e to separate mantissa and exponent, as in the examples above.


重复进行的排列

我们将改变集合{1, 2, 3, …, n}种元素顺序的操作称为一次排列。一共有 n! 种排列,其中一种就是保持所有元素的位置不变。对于n = 3,我们有如下 3! = 6 种排列:

  • P1 = 保持顺序不变
  • P2 = 交换第一个和第二个元素
  • P3 = 交换第一个和第三个元素
  • P4 = 交换第二个和第三个元素
  • P5 = 循环右移一位
  • P6 = 循环左移一位

如果我们从这些排列中选择一种,并且对排列后的集合重复进行相同的排列,我们最终会回到一开始的顺序。
对于任意排列 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,记g(n)为 f2(Pi)的平均值。

求g(350)并像上述样例那样用精确到十位小数的科学计数法表示,并用小写字母e来分割指数部分。