摇奖出现连号的概率
计算一般情况：m个号码抽n个，出现k连号或者更长的连号的概率。补一个总是不被抽中的第m+1号，每种抽法都把m+1个号码分成m-n+1段，每段以一串被抽中的连续号码开始，一个没被抽中的号码结束。于是每种抽法与方程\sum_{i=1}^{m-n+1}X_i=m+1的一个正整数解构成自然的一一对应。特别地，方程\sum_{i=1}^{b-a+1}X_i=b+1有C_b^{a}个正整数解。
令A_i=满足X_i>k的解集（也就是第i段出现k或者更长的连号），i=1..m-n+1。则出现k连号或者更多连号的抽法数等于所有A_i的并集的元素个数。根据容斥原理，|\bigcup_{i=1}^{m-n+1}A_i|=\sum_{i=1}^{m-n+1}|A_i|-\sum_{1\leq i<j\leq m-n+1}|A_i\bigcap A_j|+\sum_{1\leq i<j<k\leq m-n+1}|A_i\bigcap A_j\bigcap A_k|-...
这里的|S|表示集合S的元素个数，每项都对所有的可能情况求和。于是现在的任务就变成求t个不同的A_{i_s}的交集大小|\bigcap_{s=1}^{t}A_{i_s}|，而很显然t个不同集合A_{i_s}的交集\bigcap_{s=1}^{t}A_{i_s}=方程\sum_{i=1}^{m-n+1}X_i=m+1的满足X_{i_s}>k的正整数解集，令Y_{i_s}=X_{i_s}-k，s=1..t。其余的Y_i=X_i，可见方程\sum_{i=1}^{m-n+1}Y_i=m-tk+1的正整数解Y_i和方程\sum_{i=1}^{m-n+1}X_i=m+1的满足X_{i_s}>k的正整数解构成一一对应，都有C_{m-tk}^{n-tk}个，于是|\bigcap_{s=1}^{t}A_{i_s}|=C_{m-tk}^{n-tk}，m-n+1个集合A_i中挑出t个有C_{m-n+1}^{t}种方法，最后得到|\bigcup_{i=1}^{m-n+1}A_i|=\sum_{t=1}^{n/k}(-1)^(t-1)C_{m-n+1}^t C_{m-tk}^{n-tk}，除以总的抽法数C_m^n就是概率。
精彩！
m=786，n=203，
k=3， p=0.9999960517309451....
k=4， p=0.9369895037693703....
k=5， p=0.4867202655497829....
k=6， p=0.1527331410687272....
k=7， p=0.0407103486326307....
k=8， p=0.0103776629815789....
k=9， p=0.0026092023669399....
k=10，p=0.0006519388269146....
页:
[1]