空椅子

在一间屋子中，围绕圆桌摆了N把椅子，骑士们依次进入屋子，并随机选择一把空椅子坐下，为保证舒适，两相邻骑士间至少要间隔一把空椅子。 记无法继续入座时空椅子的比例为C，并令$E(N)$为C的期望值。可以验证$E(4)=1/2, E(6)=5/9$。 求$E(10^{18})$，结果保留小数点后14位数字，即0.abcdefghijklmn的形式。

本题难度:

解答

令$F(N)$为其他规则不变但N张椅子排成一排而非一圈时入座者的期望数量，则有 $$E(N)=1-\frac{F(N-3)+1}{N}.$$ $F(N)$可以递推计算： $$NF(N)=(N-1)F(N-1)+2F(N-2)+1,$$ 对应的常微分方程 $nf^{(n)}(x)=(n-1)f^{(n-1)}(x)+2f^{(n-2)}(x)+1$的特解是 $$f(x)=\frac{1-e^{-2x}}{2(x-1)^2}.$$ 在$x=0$处泰勒展开后取系数可得 $$F(N)=\sum_{k=1}^N\frac{(-2)^{k-1}}{k!}(n-k+1).$$ 分母$k!$增长很快，因而此交错级数收敛非常快，大约在$N=22$左右即可得到所需的精度，最终结果是$0.56766764161831$。 本题无需编程，最后交错级数极限的近似值可用Wolfram Alpha等工具计算。 注：本题递推公式的通项推导是我国理工科《高等数学》课程的标准内容。