Project Euler 807

题目

Loops of Ropes

Given a circle \(C\) and an integer \(n > 1\), we perform the following operations.

In step \(0\), we choose two uniformly random points \(R_0\) and \(B_0\) on \(C\).

In step \(i\) (\(1 \leq i < n\)), we first choose a uniformly random point \(R_i\) on \(C\) and connect the points \(R_{i - 1}\) and \(R_i\) with a red rope; then choose a uniformly random point \(B_i\) on \(C\) and connect the points \(B_{i - 1}\) and \(B_i\) with a blue rope.

In step \(n\), we first connect the points \(R_{n - 1}\) and \(R_0\) with a red rope; then connect the points \(B_{n - 1}\) and \(B_0\) with a blue rope.

Each rope is straight between its two end points, and lies above all previous ropes.

After step \(n\), we get a loop of red ropes, and a loop of blue ropes.

Sometimes the two loops can be separated, as in the left figure below; sometimes they are “linked”, hence cannot be separated, as in the middle and right figures below.

Let \(P(n)\) be the probability that the two loops can be separated.

For example, \(P(3) = \dfrac{11}{20}\) and \(P(5) \approx 0.4304177690\).

Find \(P(80)\), rounded to \(10\) digits after decimal point.

解决方案

可见，点在圆上的具体角度值并不重要；在连续变形且不改变端点在圆周上循环次序的过程中，拓扑类型（是否可分离）不会改变。

又因为所有点独立均匀随机，几乎必然不会重合，所以固定 \(B_0\) 作为起点后，其余 \(2n-1\) 个点在圆周上的循环顺序是等概率的，共有 \((2n-1)!\) 种。

因此问题变成：在 \((2n-1)!\) 个等概率排列中，有多少个排列对应可分离？

我们设法把所有蓝点 \(B_1,\ldots,B_{n-1}\) 依次沿圆周移动到 \(B_0\) 附近（保持圆上的相对运动，追踪与红点穿越的影响）。最终蓝点都聚在一起时，蓝环显然可以与红环分离，因此最终状态是未链接的。

在移动过程中，只有当某个 \(B_i\) 穿过某些特定红点时，链接数会发生变化。局部分析可得（下标模 \(n\)）：\(B_i\) 穿过 \(R_i\)，那么链接数变化 \(+1\)；\(B_i\) 穿过 \(R_{i+1}\)，那么链接数变化 \(-1\)；穿过其他红点那么变化 \(0\)。

于是，原配置是否可分离，等价于上述所有变化量总和是否为 \(0\)。

固定一个标签顺序（去掉已经固定的 \(B_0\)）：\(R_1, B_1, R_2, B_2, \ldots, R_{n-1}, B_{n-1}, R_0.\)记这 \(2n-1\) 个点从 \(B_0\) 开始逆时针数的位置（相对名次）为一个排列：\(p_0, p_1, \ldots, p_{2n-2}.\)那么根据上面的局部规则，变化量总和为

\[ \Delta =\sum_{i=1}^{n-1}\mathbf{1}\{p_{2i-1}>p_{2i-2}\} -\sum_{i=1}^{n-1}\mathbf{1}\{p_{2i-1}>p_{2i}\}, \]

利用无相等时恒有\(\mathbf{1}\{p_{2i-1}>p_{2i}\} = 1-\mathbf{1}\{p_{2i}>p_{2i-1}\},\)可化简为\(\displaystyle\Delta=\sum_{j=1}^{2n-2}\mathbf{1}\{p_j>p_{j-1}\}-(n-1).\)

而\(\displaystyle\sum_{j=1}^{2n-2}\mathbf{1}\{p_j>p_{j-1}\}\)正是排列 \(p_0,p_1,\ldots,p_{2n-2}\) 的上升下标数。因此，两个环可分离当且仅当 \(\Delta=0\)，即该排列恰有 \(n-1\) 个上升。

长度为 \(m\) 的排列中，恰有 \(k\) 个上升的个数是 Eulerian 数。

这里 \(m=2n-1,k=n-1\)，所以可分离配置数为\(A(2n-1,n-1)\)（这里使用 \(A(m,k)\) 表示恰有 \(k\) 个上升下标的排列的数量。）

因此概率为\(P(n)=\dfrac{A(2n-1,n-1)}{(2n-1)!}.\)

OEIS 的 A008292 给出了该类数的递推与显式公式；其中显式公式可写为（按本题参数代入后）：

\[A(2n-1,n-1)=\sum_{i=0}^{n}(-1)^i\binom{2n}{i}(n-i)^{2n-1}.\]

代码

import math
N = 80

def solve(n: int) -> str:
    s = 0
    for i in range(n + 1):
        s += (-1 if i & 1 else 1) * math.comb(2 * n, i) * (n - i) ** (2 * n - 1)
    den = math.factorial(2 * n - 1)
    x = s / den
    return x

print(f"{solve(80):.10f}")