题意: 有一根长为 \(1\) 的巧克力,已经被切了 \(m-1\) 刀被分成 \(m\) 分,接下来每次在整根长度为 \(1\) 的巧克力上均匀随机一个点切一刀,求每一小段巧克力长度均小于一个给定值 \(K\) 需要的期望次数。
引理:Irwin-Hall 分布:对于 \(n\) 个在 \([0,1]\) 内均匀分布的实数随机变量,它们的和不超过一个实数 \(z\) 的概率为:
\[I_n(z)=\sum\limits_{k=0}^{\lfloor z\rfloor} (-1)^k\binom{n}{k}\frac{(z-k)^n}{n!} \]首先令 \(f_L(n)\) 表示将长度为 \(L\) 的巧克力切 \(n\) 刀已经合法的概率。
\[\begin{aligned} f_L(n)&=n!\int\limits_{x_i\in[0,K],\sum_{i=1}^{n+1} x_i=L}\prod \mathrm{d}\frac{x_i}{L}\\ &=n!\int\limits_{x_i\in[0,K],\sum_{i=1}^{n} x_i\in[L-K,L]}\prod \mathrm{d}\frac{x_i}{L}\\ &=n!(\frac{K}{L})^n\int\limits_{x_i\in[0,1],\sum_{i=1}^{n} x_i\in[\frac{L-K}{K},\frac{L}{K}]}\prod \mathrm{d}x_i\\ &=n!(\frac{K}{L})^n(I_{n}(\frac{L}{K})-I_{n}(\frac{L}{K}-1))\\ &=n!w^n\Big(\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor} (-1)^k\binom{n}{k}\frac{(\frac{1}{w}-k)^n}{n!}-\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor-1} (-1)^k\binom{n}{k}\frac{(\frac{1}{w}-1-k)^n}{n!}\Big)\texttt{ (Let }w=\frac{K}{L}\texttt{)}\\ &=n!\Big(\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor} (-1)^k\binom{n}{k}\frac{(1-wk)^n}{n!}-\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor-1} (-1)^k\binom{n}{k}\frac{(1-w(k+1))^n}{n!}\Big)\\ &=\sum\limits_{k=1}^{{\lfloor \frac{1}{w}\rfloor}}(-1)^k(\binom{n}{k}+\binom{n}{k-1})(1-wk)^n\\ &=\sum\limits_{k=0}^{{\lfloor \frac{1}{w}\rfloor}}(-1)^k\binom{n+1}{k}(1-wk)^n\\ &=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\binom{n+1}{k}(\frac{L-Kk}{L})^n\\ \end{aligned} \]卷起来,可以得到
设 \(f(n)\) 表示总共切 \(n\) 刀合法的概率,\(F(z)\) 为 \(f(n)\) 的 EGF;令 \(F_L(z)\) 为 \(f_L(n)\) 的 EGF,那么有 \(F(n)=\prod_{i=1}^m F_{L_i}(z)\),且
其中 \(a_{k,0}=(-1)^k\frac{1}{k!}(\frac{L-Kk}{L})^k,a_{k,1}=(-1)^{k-1}\frac{1}{(k-1)!}(\frac{L-Kk}{L})^{k-1}\)。
于是将所有 \(F_{L_i}(z)\) 卷起来,可以得到
\[\begin{aligned} F(z)&=\sum\limits_{k=0}^{\frac{L}{K}}\sum\limits_{r=0}^{n}a_{k,r}z^{k-r}\mathrm{e}^{(n+\frac{K}{L}k)z}\\ &=\sum\limits_{k}\sum\limits_{r}a_{k,r}z^{k-r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}z^t\\ &=\sum\limits_{k}\sum\limits_{r}a_{k,r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}z^{t+k-r}\\ \end{aligned} \]注意 \(F(z)\) 是 \(f(z)\) 的 EGF,我们想求的是 OGF,所以令
\[F^*(z)=\sum\limits_{k}\sum\limits_{r}a_{k,r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}(t+k-r)!z^{t+k-r} \]则答案为
\[\begin{aligned} F^*(1)&=\sum\limits_{k}\sum\limits_{r}a_{k,r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}(t+k-r)!\\ &=\sum\limits_{k}\sum\limits_{r}a_{k,r}(k-r)!\sum\limits_{t\ge 0}\binom{t+k-r}{t}(n+\frac{K}{L}k)^t\\ &=\sum\limits_{k}\sum\limits_{r}\frac{a_{k,r}(k-r)!}{(1-n-\frac{K}{L}k)^{k-r+1}} \end{aligned} \]即为所求。
标签:Nezzar,lfloor,Bars,frac,limits,题解,sum,rfloor,binom From: https://www.cnblogs.com/Charlie-Vinnie/p/17367067.html