赠券半收集

Aster GameのDay, 理宅异闻录 Leave a Comment

Question:

假设有n种赠券,每种赠券获取机率相同,而且赠券亦无限供应。若取赠券k张,能集齐其中m种赠券的机率多少


恰好在第 $k$ 次试验得到指定 $m$ 张不同赠券的试验次数是 $ m! \mathcal{S}_2(k - 1, m - 1)$.

从 $n$ 张不同的赠券中收集 $m$ 张共有 $\mathcal{C}(n,m)$ 种方法.

最后总方法数仍是 $n^k$.

综上所述, 恰好在第 $n$ 次试验完成收集全部 $k$ 张不同的赠券的概率是:

$$P(n)=m! \mathcal{S}_2(k - 1, m - 1)\mathcal{C}(n,m)/n^k$$

Read More

经典赠券收集

Aster GameのDay, 理宅异闻录 Leave a Comment

Question:

假设有n种赠券,每种赠券获取机率相同,而且赠券亦无限供应。若取赠券k张,能集齐n种赠券的机率多少?

在第 $k$ 次试验后恰好第一次完成全部收集,则在前 $k - 1$次试验收集了 $n - 1$ 张不同的赠券.前 $k - 1$ 次试验相当于将 $k - 1$ 个元素的集合划分成有序的 $n - 1$ 个非空子集的个数.即 $(n - 1)! \mathcal{S}_2(k - 1, n - 1)$ 个,其中$\mathcal{S}_2 (k, n )$ 是第二类Stirling 数.

从 $n$ 张不同的赠券中收集到 $n - 1$ 张有 $\mathcal{C}(n,n-1)$ 种组合, 其中$\mathcal{C}(n,k)$ 为二项式系数.

最后除以总方法数,也就是将 $k$ 个元素的集合划分成 $n$ 个子集的方式,共 $n^k$ 种.

综上所述,恰好在第 $k$ 次试验完成收集全部 $n$ 张不同的赠券的试验的概率是:

$$\begin{aligned}
P(n)=&(n - 1)! \mathcal{S}_2(k - 1, n - 1)\mathcal{C}(n,n-1)/ n^k\\
=&\frac{n!}{n^k} \mathcal{S}_2(k - 1, n - 1)\\
\end{aligned}$$

Read More