华中科技大学概率统计系副主任王湘君算对了吗？

shshsh_0510

to nnd: 还是不知道怎么算，我就再解释一下,代码示意: M:=Matrix(1138,514); //init as 0 for i from 1 to 1138 do if i< 14 then (break;) for j from 1 to 514 do if j< 14 then (break;) if i< j then (break;) if i==j then (M[i,j]=1;break;) M[i,j]=M[i-1,j]+.....+C(...); end do; end do 无论C或maple都一样。 这个算法是N*M*K阶的，n=1138，m=514,k=14 数不大，可以算出精确值，如果数太大可以近似计算。 比如这个，可以得到递推公式 s(n,k)-s(n-1,k-1)=s(n-1,k)-s(n-15,k-14)+C(k-14,n-14)-C(k-15,n-15) 求双变量生成函数（大概推了一下）：S(x,y)=(x^14y^14-x^15y^15)/(1-x-xy)(1-xy-x+x^15y^14) 有了生成函数，就可以用系统的方法去求近似值了（感兴趣可以看看knuth的“具体数学”之类的书）

sheng_jianguo

sheng_jianguo 说的对，确实少一个右括号。谢谢指正。 (n!/(n-14)!)/((m+1)!/(m+1-14)!) * ((m+1-n)/(m+1-14)///这里少括号/// * Px(m-14,n-14) 但是计算是没有问题。 你的 X=C(n-15,m+1-15)/C(n,m+1)*Px(m-14 ... nnd 发表于 2009-8-7 14:04

应该是X=C(n-14,m+1-15)/C(n,m+1)*Px(m-14,n-14)，谢谢！ 但为什么和shshsh_0510的结果不一样呢?

mathe

因为31#还是错误的.不同位置的数取0,1的概率是不完全相同的

nnd

43# mathe 我的算法去掉了括号错误后算的结果是多少？

nnd

现在我反而怀疑shshsh_0510的算法只能用排列去算，不能用组合。 伟哥说：“唉呀,等等,我脑子有点乱……让我想想,” 我还没想清楚。 呵呵

nnd

s(n,k)就是长度为n,k个数字1,n-k个数字0,其中有14个连续1的不同01序列的数目. 如果再定义一个“s1(n,k)就是长度为n,k个数字1,n-k个数字0,其中有14个连续1的不同01排列的数目.”， 那么，s1(n,k)= k! (n-k)!* s(n,k) 等式1 则，s1(n,k)= (n-k) * s1(n-1,k) + k * (n-k) * s1(n-2,k-1) + k *(k-1) * (n-k) * s1(n-3,k-2)+...+ k * (k-1)*...* (k-12) * (n-k) * s1(n-14,k-13) + k * (k-1)*...* (k-12)*(k-13)*p(n-14,n-14) 等式2 将等式1 代入等式2 就得到： s(n,k)=s(n-1,k)+s(n-2,k-1)+s(n-3,k-2)+...+s(n-14,k-13)+C(k-14,n-14) 所以，shshsh_0510的算法是没有问题的。 我产生45#的幻觉的根本原因是对排列组合的基本概念理解不深。 但是mathe说：“因为31#还是错误的.不同位置的数取0,1的概率是不完全相同的”我还是不能理解。：（

sheng_jianguo

shshsh_0510的算法是没有问题而且很漂亮，但用到求组合或阶乘，当数很大时（如本问题）没有大数计算方法是很难求出结果的。 nnd方法经分析也没有错，好处在于不用求组合或阶乘，当数很大时，一般程序用双精度都能解决问题。我用简单程序很快算出P=0.0083026084182541。关键是初始条件不能搞错。

sheng_jianguo

初始条件：i<14或J<14时，Px(i,j)=1。 计算递推公式： Px(m,n)=(m-n)/m*Px(m-1,n)+n/m*Px(m-1,n-1)-[(n/m）*(n-1)/(m-1)*...*(n-13)/(m-13)]* (m-n)/(m-14)*Px(m-15,n-14) 以上公式没有用到求组合或阶乘。

nnd

谢谢sheng_jianguo gxqcn ,象本题的这种大数计算,只涉及到自然数的乘法和加法的话,用c/c++应该不难实现,而且计算速度应该也不会太慢吧? 有空的时候试试，领略一下大数计算的妙处。

wayne

可以考虑用自然数拆分与插空排列来做