排列组合的新思路

排列就是从一个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 老爷爷的思路还真是很强大。