摇奖出现连号的概率

Buffalo

计算一般情况：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....