排列就是从一个Population 中有序的采样(Sample),组合就是从一个Population中 无序的采样。无论哪种采样,基本的排列组合公式 和
都假定Population 中的每一个对象是可以区分的。但是对于Population 中存在不可区分对象的情况(比如 Sampling with Replacement),我们就需要新的思路。我自己对于这个关键的区别一直没有很深刻的理解,直到最近读 William Feller 老爷爷的概率书,才有了一些进展,下面来说一说。
假定一个长度为 的二进制字符串,其中有
个1的字符串有多少?
这个问题中,Population就是 0 和 1,但是它们可以重复出现在最终的采样中,因此简单的排列组合思路并不适用。解决这个问题有两种传统的思路:
- 思路一:假定我们在这
个字符串中 挑选
个 1,然后剩下的全部是0,那么可供挑选的总共方案是:
(1)
- 思路二:假定所有的0和1都是可以区分的,那么所有总共可能的方案就是
种,其中有
个1 和
个0。如果这
个1互相可以区分,那么它们总共有
的不同的排列方式,相应的对于这些可以区分的0我们也有
种不同的排列方式。现在这些0和1都变成不可区分的了,所以这些不同的排列方式就变成了一种,那么长度为
的二进制字符串,其中有
个1的字符串就有:
(2)
这正好就是思路一中的组合数公式,因此两种思路的结果是一样的。 上面的第二种思路讲述起来要比第一种长很多,但是我反而觉得更容易理解,其主要原因是因为它和组合数的公式推导的思路本身就是一致的。组合基本问题:从 个可以互相区分的对象中,取出
个对象的不同组合(也就是不考虑这
个对象的顺序)有多少?很明显如果我们考虑这
个对象的顺序,不同的顺序代表不同的组合的话,那么我们一共有:
(3)
种不同的方案,这是一个基本的排列问题。现在考虑 个不同的对象有多少种不同的排列方式,很明显这也是个基本的排列问题,答案是
种。现在我们看到,如果相同的
个对象的不同排列方式只能算作同一种组合的话,那么 3 对于所有可能的组合就高估了
倍,因此从
个可以互相区分的对象中,取出
个对象的不同组合(也就是不考虑这
个对象的顺序)就有:
(4)
沿着这个新思路,我们可以解决一些新的排列组合题目,下面是一些例子。
假定有面不同的旗帜,要挂在
个旗杆上,一共有多少悬挂的方法?
很明显第一面旗帜有 种悬挂的方法,注意到有旗帜的那个旗杆现在如果我们要在上面再挂新的旗帜的话,有上面和下面两种选择,所以第二面旗帜有
种悬挂的方法,以此类推,第三面旗帜有
中悬挂的方法,而所有总共的悬挂方法有:
(5)
现在假定这 面旗帜都是一样的(比方说都是普通的红旗),那么考虑到
个不同的旗帜一共有
种排列方法,现在这些旗帜都变成一样的了,所以上式的估计就比实际高出了
倍,因此当这
面旗帜都是一样的时候总共的悬挂方法就有:
(6)
顺便提一句,帖子 组合数学中的分配问题(二):不能区分的对象和可以区分的组中问到的 18 个相同的文件夹在4个不同的人之间分配,每个人接收到的文件夹数量不做限制的话,就可以利用上式计算:
(7)
最后,如果我们有两种旗帜:面红旗和
面蓝旗,很明显我们有
,那么把它们挂到
个旗杆上的方法,按照上面的思路很容易就得到了:
(8)
William Feller 老爷爷的思路还真是很强大。