Project Euler | 欧拉计划
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:

  • $P_1$ = keep the initial order
  • $P_2$ = exchange the 1st and 2nd elements
  • $P_3$ = exchange the 1st and 3rd elements
  • $P_4$ = exchange the 2nd and 3rd elements
  • $P_5$ = rotate the elements to the right
  • $P_6$ = 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 $P_i$, let $f(P_i)$ be the number of steps required to restore the initial order by applying the permutation $P_i$ repeatedly.

For $n = 3$, we obtain:

  • $f(P_1) = 1 : (1,2,3) → (1,2,3)$
  • $f(P_2) = 2 : (1,2,3) → (2,1,3) → (1,2,3)$
  • $f(P_3) = 2 : (1,2,3) → (3,2,1) → (1,2,3)$
  • $f(P_4) = 2 : (1,2,3) → (1,3,2) → (1,2,3)$
  • $f(P_5) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)$
  • $f(P_6) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3)$

Let $g(n)$ be the average value of $f^2(P_i)$ over all permutations $P_i$ of length $n$.

$g(3) = (1^2 + 2^2 + 2^2 + 2^2 + 3^2 + 3^2)/3! = 31/6 ≈ 5.166666667e0$

$g(5) = 2081/120 ≈ 1.734166667e1$

$g(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$种重排：

  • $P_1$ = 保持顺序不变
  • $P_2$ = 交换第一个和第二个元素
  • $P_3$ = 交换第一个和第三个元素
  • $P_4$ = 交换第二个和第三个元素
  • $P_5$ = 循环右移一位
  • $P_6$ = 循环左移一位

如果从这些重排中选择一种，并且对重排后的序列重复进行相同的重排，最终元素会回到初始顺序。
对于任意重排$P_i$，记$f(P_i)$为回到初始顺序所需要的重复次数。

对于$n = 3$可以得到：

  • $f(P_1) = 1 : (1,2,3) → (1,2,3)$
  • $f(P_2) = 2 : (1,2,3) → (2,1,3) → (1,2,3)$
  • $f(P_3) = 2 : (1,2,3) → (3,2,1) → (1,2,3)$
  • $f(P_4) = 2 : (1,2,3) → (1,3,2) → (1,2,3)$
  • $f(P_5) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)$
  • $f(P_6) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3)$

对于所有长度为$n$的重排$P_i$，记$g(n)$为$f^2(P_i)$的平均值。

$g(3) = (1^2 + 2^2 + 2^2 + 2^2 + 3^2 + 3^2)/3! = 31/6 ≈ 5.166666667e0$

$g(5) = 2081/120 ≈ 1.734166667e1$

$g(20) = 12422728886023769167301/2432902008176640000 ≈ 5.106136147e3$

求$g(350)$，并用四舍五入至$10$位小数的科学计数法表示，用小写字母$e$来分隔尾数和指数，如上述样例所示。