0307 电路瑕疵
* * * *
拉格朗日计划
* * * *
电路瑕疵

某工厂生产的n块集成电路上随机分布有k个瑕疵(一块集成电路上可能有任意数量的瑕疵,瑕疵的分布是相互独立的事件)。

记$p(k,n)$为在上述设定下存在一块至少有3个瑕疵的集成电路的概率。可以验证,$p(3,7)\approx0.0204081633$。

求$p(20000,1000000)$,答案应四舍五入至10位小数,即0.abcdefghij的形式。

本题难度:



解答

显然只需计算出所有零件至多只有2个瑕疵的概率。

设有i个零件有2个瑕疵,则有k-2i个零件只有1个瑕疵,n-k+i个零件没有瑕疵,这样的情况共有 $$q_i=\binom{n}{i}\cdot\binom{n-i}{k-2i}\cdot\frac{k!}{2^i},$$ 种,因此结果为 $$1-\frac{1}{n^k}\sum_iq_i\approx0.7311720251。$$ 注:以下代码为Python 3,并打印了进度信息。因数值较大,先将阶乘转换为对数后再计算,不过math库无法达到所要求的精度,因此使用decimal库作计算。

import decimal

k=20000
n=1000000
f=[0]*(n+k+1)

for i in range(1,n+k+1):
    #f[i]=f[i-1]+math.log(i)
    f[i]=f[i-1]+decimal.Decimal(i).ln()
    if i%10000==0:print(i//10000,"percent completed")

a,b=k*decimal.Decimal(n).ln(),decimal.Decimal(2).ln()

print(1-sum((f[n]+f[k]-f[i]-f[k-2*i]-f[n-k+i]-a-i*b).exp() for i in range(min(k//2,n)+1)))