3.几个经典问题

实用的组合公式

\[(1) \quad C_{n}^{r}=C_{n-1}^{r-1}+C_{n-1}^{r}\]

\[(2) \quad C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+...+C_{n}^{n}=2^{n}\]

\[(3) \quad C_{n}^{1}+2 C_{n}^{2}+3 C_{n}^{3}+...+n C_{n}^{n}=n2^{n-1}\]

\[(4) \quad C_{a}^{0}C_{b}^{n}+C_{a}^{1}C_{b}^{n-1}+ C_{a}^{2}C_{b}^{n-2}+...+C_{a}^{n}C_{b}^{0}=C_{a+b}^{n} \quad a=min\{a,b\}\]

\[ (5)\quad (C_{n}^{0})^{2}+(C_{n}^{1})^{2}+(C_{n}^{2})^{2}+...+(C_{n}^{n})^{2}=C_{2n}^{n}\]

\[(6)C_{-n}^{r} = (-1)^r C_{n+r-1}^{r}\]

可重复组合

在李贤平著的《概率论基础》中对可重复组合的描述是：“从n个不同的元素中有重复的抽取r个，不计顺序。”我们举例来说明，假如有编号为1,2的两个小球(n=2)，从中有放回(有重复)的抽取两次(r=2)，则不同的情况有多少种？

这个题的关键在于我们是不管小球抽取的顺序的，我们只在乎我们最后抽取的结果。经过简单的列举我们可以知道所有的情况有：抽到两个编号为1的小球，抽到两个编号为2的小球，抽到一个编号为1的小球和一个编号为2的小球共三种。我们引入可重复组合公式记为\(H\)：

\[H_{n}^{r}=C_{n+r-1}^{r}\]

带入得\(H_{2}^{2}=C_{2+2-1}^{2}=3\)。

分球入盒

将n个完全相同的球(这时也称球是不可辨的)随机地放入N个盒子中，试问某个指定的盒子中恰有k个球的情况，某个指定的盒子中恰有k个球的概率。

这里抽象成可重复组合应该把盒子理解为我们之前举例的“球”，每个盒子是各不相同的，而放入完全相同小球的过程就是抽取盒子的过程。“翻译”成可重复组合的语言那就是：从编号为1,2,······,N的小球中有放回的抽取n次，则某个指定的小球被抽取k次的情况。我们利用可重复组合的公式，知道该题的意思是在剩余的(N-1)个小球中抽取(n-k)次，容易列出所有的情况为：

\[H_{N-1}^{n-k}=C_{N+n-k-2}^{n-k}\]

第二个问有一个误区在于，我们知道从N个小球中有放回的抽取n次的事件总数为\(H_{N}^{n}=C_{N+n-1}^{n}\)，所以某个第二问的答案容易写成二者的比。但其实问题是用可重复组合得到的情况发生的概率不一定相同，也就是说这并不是古典概型。从我们之前在可重复组合里叙述的例子可以知道，抽到两个编号为1的小球概率为 \(\frac{1}{4}\)，同样抽到两个编号为2的小球概率也为 \(\frac{1}{4}\)，抽到一个编号为1一个编号为2的小球的概率是\(\frac{1}{2}\)。如过当做古典概型来计算概率，那么每个事件发生的概率都是\(\frac{1}{3}\)，这显然不对。所以这一问的答案应该是

\[C_{n}^{k}(\frac{1}{N})^{k}(1-\frac{1}{N})^{n-k}\]

这里计算概率时实际上把球看成是可辨的，我们知道在计算概率时小球可辨与否并不影响最后的答案。总的来说，我们要学会抽象可重复组合模型，同时在计算概率时要小心：可重复组合里的事件并不一定是等概率的！