清理一

有一位小朋友，他有一种叫做数字毛毛虫的拼板玩具，每块拼板上都按标有1到40之间的一个编号，不同拼板上的编号互不相同，如果把它们按顺序拼接就得到一条直线。

每天晚上，小朋友的爸爸都要把玩具房里撒了一地的毛毛虫拼板捡起来并按照正确的顺序拼好。

拼板捡起时的顺序是随机的，因而在这一过程中这些拼板会不断形成一些连续片段，直到最后组成完整的毛毛虫直线。

根据经验，片段数会从0开始（没有捡起任何一块拼板），逐渐上升到大约11或12左右，然后下降，直到最终只有一段（所有的拼板都组合起来了）。

例如，若拼板捡起的顺序是$12, 4, 29, 6, 34, 5, 35, \ldots$的话，那么片段数依次是$1,2,3,4,5,4,4,\ldots$，注意第六步片段数下降到了4，这是因为4,5,6三块拼板形成了一个片段。

记M为清理拼板过程中出现过的最大片段数。若只有十块拼板，则M可以取值1,2,3,4,5，对应的情况数分别是512, 250912, 1815264, 1418112, 144000，因此最可能出现的M值为3，M的平均值约为$385643/113400\approx3.400732$。

若共有四十块拼板，那么最可能出现的M值为11，求此时M的平均值，结果保留六位小数。

本题难度:

解答

记$f(i,j,k)$为捡起i块拼板后形成j个片段，且在此过程中出现过的最大片段数不超过k的情况总数。

注意片段上的绝对编号对f的值没有影响，只需要关注其相对大小，比如捡起3,2,5,7和捡起3,2,5,6的机会完全相同，前者形成3个片段，后者形成2个片段，因此在考虑递推关系时只要保持相对顺序不变，就可以根据状态转化的需要来取片段上的编号值。由此可得递推公式： $$f(i,j,k)=j\cdot f(i-1,j-1,k)+j\cdot f(i-1,j+1,k)+2j\cdot f(i-1,j,k),$$ 其中右侧第一项表示可以在$j-1$段首尾和之间的共j个位置插入新拼板得到j段，第二项表示可以在$j+1$段之间的共j个位置插入新拼板使得原先分离的两段合并（例如在3,4和6,7,8之间插入5），最后一项表示可以在j段每一段的首尾共2j个位置放置新拼板以拓展已有的片段。

f有初值$f(1,1,k)=1, (k\ge 1)$，此外，符合逻辑的i,j,k（例如显然i,k都需要不小于j）才能作为f的支撑集中元素。

递推计算，最终结果是 $$\sum_{k=1}^{20}k\cdot \frac{f(40,1,k)-f(40,1,k-1)}{40!}\approx11.492847$$ 注：以下代码为Python 3，因需要使用缓存特性作记忆化搜索。

from functools import *
import math

@cache
def f(i,j,k):
    if i==j==1:
        return 1
    if min(i,j,k)<=0 or j>min(i,k):
        return 0
    return j*f(i-1,j-1,k)+j*f(i-1,j+1,k)+2*j*f(i-1,j,k)

print("%.6f" %(sum(k*(f(40,1,k)-f(40,1,k-1)) for k in range(1,21))/math.factorial(40)))