组合数学中的采样(Sample)问题 (二):一个人被选中的概率

很多排列组合的题目都需要一个合适的思路用来描述选择的过程,一旦这个过程确定下来,又容易用基本的排列组合方式去描述,那么解决题目就容易的多了。下面就是一个典型的例子:反向思考要比正向思考容易很多。

假定我们要从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是多少呢?

上一个帖子中我们已经讲到过基本采样问题的计算方法,这里的问题需要更进一步从反向去思考,如果我们需要的这个排列不包含A的话,那么总共可供挑选的人数就是 n-1,从中选出r人的总共可能的排列就是:

(1)   \begin{equation*} P_{n-1}^{r} \end{equation*}

而从 n 个中选出 r 个人编为一个排列的总共可能性是:

(2)   \begin{equation*} P_{n}^{r} \end{equation*}

所以从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(3)   \begin{equation*} \dfrac{P_{n-1}^{r}}{P_{n}^{r}} \end{equation*}

那么相应的,从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率就是1减去上面的概率:

(4)   \begin{equation*} 1 - \dfrac{P_{n-1}^{r}}{P_{n}^{r}} = \dfrac{r}{n} \end{equation*}

如果正向去思考,过程要麻烦一些,可以参考下面的思路:假定我们第一个人就选取A,然后剩下的r-1个人从剩下的n-1个人中选取,总共可能的排列是:

(5)   \begin{equation*} P_{n-1}^{r-1} \end{equation*}

同理,如果我们第二个人选取A,然后剩下的r-1个人从剩下的n-1个人中选取,总共可能的排列也是 P_{n-1}^{r-1}。考虑到我们一共需要选取 r 个人,所以总共包含A 的可能的排列就是:

(6)   \begin{equation*} P_{n-1}^{r-1} \cdot r \end{equation*}

那么相应的,从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(7)   \begin{equation*} \dfrac{P_{n-1}^{r-1} \cdot r}{P_{n}^{r}} = \dfrac{r}{n} \end{equation*}

上面的过程是针对选择对象不能重复(No replacement)的情况,所以正向和反向的分析复杂程度差不太多,如果是对象可以重复(With Replacement),反向分析的思路还是差不多:

n 个人中选取 r 个人的总共排列是:

(8)   \begin{equation*} n^r \end{equation*}

如果排除某个固定的人 A,从剩下的 n-1 个人中选取 r 个人的总共排列是:

(9)   \begin{equation*} (n-1)^r \end{equation*}

所以从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(10)   \begin{equation*} 1 - \dfrac{(n-1)^r}{n^r} \end{equation*}

但是如果我们从正向考虑,第一个人就选取A,然后剩下的r-1个人从n个人中随便选取(注意因为每个元素可以选取多次,所以这里是 n 而不是 n-1),总共可能的排列是:

(11)   \begin{equation*} n ^ {r -1 } \end{equation*}

那么以同样的方式考虑第二个、第三个一直到第 r 个人,我们会得出所有包含 A 的排列总数是:

(12)   \begin{equation*} n ^ {r -1 } \cdot r \end{equation*}

这样我们就会得出结论:从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(13)   \begin{equation*} \dfrac{n ^ {r -1 } \cdot r}{n^r} = \dfrac{r}{n} \end{equation*}

反向思考得出的 10 和 正向思考得出的 13 很明显不同。那么哪个是正确的呢?在这里反向思考的结果 10 依然是正确的,而正向思考过高的估计了概率,因为第一个人固定为 A, 然后剩下的人随便选 和 第二个人固定为 A,然后剩下的人随便选,选出来的排列有可能完全相同,我们必须把这些完全相同的排列去掉才能正确的计算排列的总数。