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

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

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