Problem 483

Repeated permutation

We define a permutation as an operation that rearranges the order of the elements ${1, 2, 3, \dots, 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 1^st and 2^nd elements
$P_{3}$ = exchange the 1^st and 3^rd elements
$P_{4}$ = exchange the 2^nd and 3^rd 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) \to (1, 2, 3)$
$f (P_{2}) = 2 : (1, 2, 3) \to (2, 1, 3) \to (1, 2, 3)$
$f (P_{3}) = 2 : (1, 2, 3) \to (3, 2, 1) \to (1, 2, 3)$
$f (P_{4}) = 2 : (1, 2, 3) \to (1, 3, 2) \to (1, 2, 3)$
$f (P_{5}) = 3 : (1, 2, 3) \to (3, 1, 2) \to (2, 3, 1) \to (1, 2, 3)$
$f (P_{6}) = 3 : (1, 2, 3) \to (2, 3, 1) \to (3, 1, 2) \to (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 \approx 5.166666667 e 0$

$g (5) = 2081 / 120 \approx 1.734166667 e 1$

$g (20) = 12422728886023769167301 / 2432902008176640000 \approx 5.106136147 e 3$

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, \dots, 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) \to (1, 2, 3)$
$f (P_{2}) = 2 : (1, 2, 3) \to (2, 1, 3) \to (1, 2, 3)$
$f (P_{3}) = 2 : (1, 2, 3) \to (3, 2, 1) \to (1, 2, 3)$
$f (P_{4}) = 2 : (1, 2, 3) \to (1, 3, 2) \to (1, 2, 3)$
$f (P_{5}) = 3 : (1, 2, 3) \to (3, 1, 2) \to (2, 3, 1) \to (1, 2, 3)$
$f (P_{6}) = 3 : (1, 2, 3) \to (2, 3, 1) \to (3, 1, 2) \to (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 \approx 5.166666667 e 0$

$g (5) = 2081 / 120 \approx 1.734166667 e 1$

$g (20) = 12422728886023769167301 / 2432902008176640000 \approx 5.106136147 e 3$

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