令$f(n,k)$为长度为n的排列中前k个元素不在原位的排法总数，并规定边界值$f(n,0)=n!$，则有
$$f(n,k)=f(n,k-1)-f(n-1,k-1),$$
这是因为前k个元素不在原位的排法等于从前$k-1$个元素不在原位的排法、即$f(n,k-1)$，中扣除第k个元素不动的排法，而第k个元素既然不动，则将其移除也不影响数量，也就是这样的排法有$f(n-1,k-1)$个。
从而递推计算就可得结果
$$\frac{\binom{25}{22}f(97,22)}{100!}\approx0.001887854841.$$
f=[[0]*min(n+1,23) for n in range(101)]
f[0][0]=f[1][0]=1
for n in range(2,101):
f[n][0]=f[n-1][0]*n
for n in range(1,101):
for k in range(1,min(n+1,23)):
f[n][k]=f[n][k-1]-f[n-1][k-1]
print "%.12f" %(1.0*(f[25][0]/(6*f[22][0]))*f[97][22]/f[100][0])
|
