假设一共N个球，每次有放回的从中取M个球，求能从中取到任意Q个球所需得最少次数是

keasc

假设一共N个球，每次有放回的从中取M个球，求能从中取到任意Q个球所需得最少次数是多少？


当每次取的球的数量为1，且求取出全部球所需次数时，就是著名的"优惠券收集者问题"，希望大家就题目能讨论下

kastin

你确认你想问的是“最少次数”？
若`M\geqslant Q`，最少次数当然就是1次了；若 `M < Q`，最少次数不就是 `\lceil Q/M \rceil` 吗？

如果指的是期望次数，可以参考这个帖子 http://bbs.emath.ac.cn/thread-9180-1-1.html 第4、5楼的回答，不过于本帖问题问法稍有不同，结果也就不一样。

keasc

kastin 发表于 2017-6-28 10:53
你确认你想问的是“最少次数”？
若`M\geqslant Q`，最少次数当然就是1次了；若 `M < Q`，最少次数不就是  ...

嗯嗯，我表达有误，就是想问期望。我看了您曾经发的帖子，解法确实很犀利。但是我想全取和取Q个（Q>M）还是有些区别，在这中间还是有些考虑不明白，希望您能再指点指点。
祝您身体健康，工作顺利！
望回复。

kastin

keasc 发表于 2017-6-28 19:51
嗯嗯，我表达有误，就是想问期望。我看了您曾经发的帖子，解法确实很犀利。但是我想全取和取Q个（Q>M）还 ...

严格来讲，问题应该是求“最少次数的期望”。

其实要取满Q个球，对于每次只取一个球来说（M=1)，结果为 `\sum_{i=1}^Q\frac{n}{n-i+1}`
每次取M个球，类似的方法可得：$$\frac{1}{M}\left[\left(\frac{n}{Q}+\frac{n-1}{Q-1}+\cdots+\frac{n-M+1}{Q-M+1}\right)+\left(\frac{n}{Q-M}+\frac{n-1}{Q-M-1}+\cdots+\frac{n-M+1}{Q-2M+1}\right)+\cdots+\left(\frac{n}{Q-\lfloor Q/M\rfloor M}+\frac{n-1}{Q-\lfloor Q/M\rfloor M-1}+\cdots+\frac{n-Q+\lfloor Q/M\rfloor M+1}{1}\right)\right]$$

keasc

kastin 发表于 2017-6-28 22:28
严格来讲，问题应该是求“最少次数的期望”。

其实要取满Q个球，对于每次只取一个球来说（M=1)，结果 ...

嗯嗯，我大体看懂这个公式了；感觉能不能在从第二个小括号开始每个小括号前加一个参数ai，当（Q-iM）>M时（最后式子不加），ai=1,；否则为0。这样式子会不会更好懂

keasc

kastin 发表于 2017-6-28 22:28
严格来讲，问题应该是求“最少次数的期望”。

其实要取满Q个球，对于每次只取一个球来说（M=1)，结果 ...

嗯，有没有更优美的表达式，这么看总是别扭。我觉得肯定有一个完美的表达，我那样表达还是麻烦，太生硬，但是我没想出来。。

kastin

keasc 发表于 2017-6-29 21:54
嗯，有没有更优美的表达式，这么看总是别扭。我觉得肯定有一个完美的表达，我那样表达还是麻烦，太生硬， ...

有规律的才优美，但失于简约；严谨的简约但往往不优美（因为要考虑到一般性）。

keasc

kastin 发表于 2017-6-29 22:06
有规律的才优美，但失于简约；严谨的简约但往往不优美（因为要考虑到一般性）。

\(\frac{1}{M}\left[\left(\frac{n}{Q}+\frac{n-1}{Q-1}+\cdots+\frac{n-M+1}{Q-M+1}\right)+a_1\left(\frac{n}{Q-M}+\frac{n-1}{Q-M-1}+\cdots+\frac{n-M+1}{Q-2M+1}\right)+a_2\left(\frac{n}{Q-2M}+\frac{n-1}{Q-2M-1}+\cdots+\frac{n-M+1}{Q-3M+1}\right)+\cdots+\left(\frac{n}{Q-\lfloor Q/M\rfloor M}+\frac{n-1}{Q-\lfloor Q/M\rfloor M-1}+\cdots+\frac{n-Q+\lfloor Q/M\rfloor M+1}{1}\right)\right]\)

\begin{equation*}ai=\begin{cases}
1, & \text{ if } (Q-iM>M)\\
0, & \text{else }
\end{cases}\end{equation*}

那这样算严谨了么

keasc

kastin 发表于 2017-6-29 22:06
有规律的才优美，但失于简约；严谨的简约但往往不优美（因为要考虑到一般性）。

佩服，真的佩服。这个表达真的好简洁好严谨，好美