排列组合的新思路

Posted bySite Author

排列就是从一个Population 中有序的采样（Sample），组合就是从一个Population中 无序的采样。无论哪种采样，基本的排列组合公式 P_n^r 和 {n \choose r} 都假定Population 中的每一个对象是可以区分的。但是对于Population 中存在不可区分对象的情况(比如 Sampling with Replacement)，我们就需要新的思路。我自己对于这个关键的区别一直没有很深刻的理解，直到最近读 William Feller 老爷爷的概率书，才有了一些进展，下面来说一说。

假定一个长度为 n 的二进制字符串，其中有r (0 \le r \le n)个1的字符串有多少？

这个问题中，Population就是 0 和 1，但是它们可以重复出现在最终的采样中，因此简单的排列组合思路并不适用。解决这个问题有两种传统的思路：

  • 思路一：假定我们在这 n 个字符串中 挑选 r 个 1，然后剩下的全部是0，那么可供挑选的总共方案是：

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

  • 思路二：假定所有的0和1都是可以区分的，那么所有总共可能的方案就是 n! 种，其中有 r 个1 和 n-r 个0。如果这r个1互相可以区分，那么它们总共有 r!的不同的排列方式，相应的对于这些可以区分的0我们也有 (n-r)!种不同的排列方式。现在这些0和1都变成不可区分的了，所以这些不同的排列方式就变成了一种，那么长度为 n 的二进制字符串，其中有r (0 \le r \le n)个1的字符串就有：

(2)   \begin{equation*} \dfrac{n!}{r! \cdot (n-r)!} = { n \choose r} \end{equation*}

这正好就是思路一中的组合数公式，因此两种思路的结果是一样的。 上面的第二种思路讲述起来要比第一种长很多，但是我反而觉得更容易理解，其主要原因是因为它和组合数的公式推导的思路本身就是一致的。组合基本问题：从 n 个可以互相区分的对象中，取出r个对象的不同组合（也就是不考虑这r个对象的顺序）有多少？很明显如果我们考虑这r个对象的顺序，不同的顺序代表不同的组合的话，那么我们一共有：

(3)   \begin{equation*} n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1) \end{equation*}

种不同的方案，这是一个基本的排列问题。现在考虑 r 个不同的对象有多少种不同的排列方式，很明显这也是个基本的排列问题，答案是 r! 种。现在我们看到，如果相同的r个对象的不同排列方式只能算作同一种组合的话，那么 3 对于所有可能的组合就高估了 r! 倍，因此从 n 个可以互相区分的对象中，取出r个对象的不同组合（也就是不考虑这r个对象的顺序）就有：

(4)   \begin{equation*} \dfrac{n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1)}{r!} = \dfrac{n!}{r! \cdot (n-r)!} = { n \choose r} \end{equation*}

沿着这个新思路，我们可以解决一些新的排列组合题目，下面是一些例子。

假定有n面不同的旗帜，要挂在 r 个旗杆上，一共有多少悬挂的方法？

很明显第一面旗帜有 r 种悬挂的方法，注意到有旗帜的那个旗杆现在如果我们要在上面再挂新的旗帜的话，有上面和下面两种选择，所以第二面旗帜有 r+1种悬挂的方法，以此类推，第三面旗帜有 r+2中悬挂的方法，而所有总共的悬挂方法有：

(5)   \begin{equation*} r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1) \end{equation*}

现在假定这 n 面旗帜都是一样的（比方说都是普通的红旗），那么考虑到n 个不同的旗帜一共有 n! 种排列方法，现在这些旗帜都变成一样的了，所以上式的估计就比实际高出了 n! 倍，因此当这 n 面旗帜都是一样的时候总共的悬挂方法就有：

(6)   \begin{equation*} \dfrac{r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1)}{n!} \end{equation*}

顺便提一句，帖子 组合数学中的分配问题（二）：不能区分的对象和可以区分的组中问到的 18 个相同的文件夹在4个不同的人之间分配，每个人接收到的文件夹数量不做限制的话，就可以利用上式计算：

(7)   \begin{equation*} \dfrac{4 \times 5 \times 6 \times ... \times 21}{18!} = 1330 \end{equation*}

最后，如果我们有两种旗帜：p面红旗和q面蓝旗，很明显我们有p+q=n，那么把它们挂到r 个旗杆上的方法，按照上面的思路很容易就得到了：

(8)   \begin{equation*} \dfrac{r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1)}{p! \cdot q!} \end{equation*}

William Feller 老爷爷的思路还真是很强大。