乱点鸳鸯谱
By drkevin | 3月 16, 2009
下面这篇是一九九五年九月在ACT上有人提问，题目是：A、B两个集合各有n个元素，本来有个一一对应的，但是如果随机配对，所有的配对都配错的概率是多少？(原题的描述要有趣一些，但是我不记得了)
乱点鸳鸯谱 (Re: 问题求解)
这个问题有点意思，通俗地讲讲吧。
话说月老给ｎ对少男少女牵红线。谁知这位月老是个马大哈，
闭着眼睛乱拴一气，到头来不知多少痴男怨女被错配鸳鸯，有情无
缘。只不知道他老人家糊涂到什么程度，哪怕只拴对了一对儿也好
嘛。下面就来算算连一对儿都拴不对的可能性有多大。
因为总共有ｎ对男女，一男一女之间拴红线，所有不同的拴法
总数是ｎ！（ｎ的阶乘），所以只要数清一对儿都拴不对有多少种
拴法，再除以ｎ！就可以得出概率。这是一个计数的问题。
一对儿都拴不对的拴法并不好数，我们可以先数至少拴对了一
对儿的拴法，再从总数ｎ！中减掉就行了。至少拴对了一对儿，怎
么数呢？先从ｎ对中任选一对作为拴对了的，这有C(n,1)种选
择（C(n,1)是ｎ中选１的组合数）；其他红线就随便牵，共有
（ｎ－１）！种方法，由此得到一个结果：
S(1) = C(n,1) * (n-1)!
您如果细心，就会发现这个结果其实是不对的，因为假如某种
拴法拴对了两对儿，那么它在Ｓ（１）中就被数了两次。所以需要
把这些数过两次的算法减掉一次才对。至少拴对了两对儿，有多少
种拴法呢？从ｎ对中选出２对，有C(n,2)种选择；其余的红线
随便牵，共（ｎ－２）！种方法，于是：
S(2) = C(n,2) * (n-2)!
要算的总数是： S(1) - S(2)
细心人会发现，类似的问题又来了：假如某种拴法拴对了三对
儿，那么它在Ｓ（１）中被数了３次，在Ｓ（２）中也被数了３次，
两数一减就没了，因此我们比须再把它加回来。用和前面同样的办
法算出：
S(3) = C(n,3) * (n-3)!
要算的总数是： S(1) - S(2) + S(3)
下面再考虑拴对了四对儿的拴法。仔细数数（也是用组合数来
数），它在上面的Ｓ（１）中数了４次，Ｓ（２）中数了６次，而
Ｓ（３）中又数了４次，加加减减之后还剩下２次，这多出的一次
还是要减掉，所以：
S(4) = C(n,4) * (n-4)!
要算的总数是： S(1) - S(2) + S(3) - S(4)
依此类推，最后算到ｎ对儿全拴对的拴法数：
S(n) = C(n,n) * 0!
那么至少拴对了一对儿的拴法数目就是：
S(1) - S(2) + S(3) - S(4) + … + (-1)^(n-1) * S(n)
我们要数的是所有的红线都拴错了的拴法数，记为Ｄ（ｎ），
应该等于ｎ！减去上面算出的这个数，就得出下列公式：
D(n) = n! - S(1) + S(2) - S(3) + S(4) - … + (-1)^n S(n)
= n! - C(n,1)*(n-1)! + C(n,2)*(n-2)! - …
… + (-1)^n * C(n,n)*0!
= n! * (1 - 1/1! + 1/2! - … + (-1)^n * 1/n!)
这个数除以ｎ！，就得到连一对儿都没有配上的概率：
P(n) = 1 - 1/1! + 1/2! - … + (-1)^n * 1/n!
正象一位网友指出的，这实际上是ｅ＾（－１）的泰勒展式的
前ｎ＋１项之和。当 n 趋于无穷大，结果就是ｅ＾（－１），
即 36.79% 。
上面只是一般的解释，不能算严格的推导。对数学有兴趣的朋
友可以试试严格的数学推导。一种方法是先推出下面这个递推公式：
D(n) = (n-1) * [ D(n-2) + D(n-1) ]
然后由此导出下面的公式：
D(n) = n * D(n-1) + (-1)^n
最后解出Ｄ（ｎ）就不难了。细节不讲了吧。
Topics: ACT旧帖 |