加载中…放错信笺问题（错位排列含容斥原理）
(2011-08-01 22:21:44)
标签：
文化教育组合 |
分类： 数学 |
有3封信和3个信封，当然每个信封里只能装一封信，求每封信都不装在自己信封里的排列数。
方法很简单，就是
Card（A∪B∪C）=Card（A）＋Card（B）＋Card（C）－Card（A∩B）－Card（B∩C）－Card（A∩C）+Card（A∩B∩C）
所谓的容斥原理，如下图
当然两个集合更容易计算，即
Card（A∪B）=Card（A）＋Card（B）－Card（A∩B）
那四个集合呢？
四个集合的图是这样的
http://s9/bmiddle/5e432757ga96e4ce81578&690
看着比较乱， 考虑到比三个集合多一个，可以用Card（A∪B∪C）加上Card（D－A∪B∪C）就可以了，因为新插入一个集合，这样与D相关的集合就有了A∩D、B∩D、C∩D，由容斥原理，这三个集合的并集元素个数为
看着比较乱， 考虑到比三个集合多一个，可以用Card（A∪B∪C）加上Card（D－A∪B∪C）就可以了，因为新插入一个集合，这样与D相关的集合就有了A∩D、B∩D、C∩D，由容斥原理，这三个集合的并集元素个数为
Card（(A∩D)∪(B∩D
所以
Card（D－A∪B∪C）=Card（D）－Card（(A∩D)∪(B∩D
=Card（D）－Card（A∩D）－Card（B∩D）－Card（C∩D）
＋Card（A∩B∩D）＋Card（A∩C∩D）＋Card（B∩C∩D）－Card（A∩B∩C∩D）
又因为
Card（A∪B∪C）=Card（A）＋Card（B）＋Card（C）－Card（A∩B）－Card（B∩C）－Card（A∩C）＋Card（A∩B∩C）
所以
Card（A∪B∪C∪D）=Card（A∪B∪C）＋Card（D－A∪B∪C）
=Card（A）＋Card（B）＋Card（C）＋Card（D）
－Card（A∩B）－Card（A∩C）－Card（A∩D）－Card（B∩C）－Card（B∩D）－Card（C∩D）
＋Card（B∩C∩D）＋Card（A∩C∩D）＋Card（A∩B∩D）＋Card（A∩B∩C）
－Card（A∩B∩C∩D）
通过2集合到4集合的容斥原理，可以发现容斥原理的规律
如果给定n个集合A(1)，A(2)，…，A(n)，那么
Card（∪A(i)）=∑Card（A(i)）－∑Card（A(i)∩A(j)）＋∑Card（A(i)∩A(j)∩A(k)）－
，…，
－(-1)^n*Card(∩A(i))
****这里i＜j＜k****
可以用数学归纳法证明，由于符号不容易写，而且写出来也很难理解，就不再赘述了，具体证法可以参照四个集合容斥原理的计算。
设集合A(i)为第i封信装对的情况，那么
Card（A(i)）=(n－1)!
（i=1,2,…，n)
同理，如果再给定一个信笺的序号j，那么集合A(i)∩A(j)表示第i、j封信都装对的情况，那么有
Card（A(i)∩A(j)）=(n－2)!
（1≤i＜j≤n)
同理，如果再给定一个信笺的序号k，那么集合A(i)∩A(j)∩A(k)表示第i、j、k封信都装对的情况，那么有
Card（A(i)∩A(j)∩A(k)）=(n－3)!
（1≤i＜j＜k≤n)
……
我们知道A(1)∪A(2)∪A(3)…∪A(n)表示第一封装对或第二封装对或第三封装对……或第n封装对的情况，即存在装对信笺的情况，根据容斥原理，有
Card(A(1)∪A(2)∪A(3)…∪A(n))=∑Card（A(i)）－∑Card（A(i)∩A(j)）＋∑Card（A(i)∩A(j)∩A(k)）－
，…，
－(-1)^n*Card(∩A(i))
=n(n－1)!－C{2，n}(n－2)!＋C{3，n}(n－3)!－，…，－(-1)^i*C{i，n}(n－i)!－，…，－(-1)^n*C{n，n}0!
=A{n－1，n}－A{n－2，n}＋A{n－3，n}－，…，－(-1)^i*A{n－i，n}－，…，－(-1)^n*A{0，n}
那么全放错的情况就是排除有信件放对的情况，又因为所有装信的情况为排列数n!，所以n封信都放错的排列数为
n!－Card(A(1)∪A(2)∪A(3)…∪A(n))
=n!－A{n－1，n}＋A{n－2，n}－A{n－3，n}＋，…，＋(-1)^i*A{n－i，n}＋，…，＋(-1)^n*A{0，n}
=A{n－2，n}－A{n－3，n}＋，…，＋(-1)^i*A{n－i，n}＋，…，＋(-1)^n*A{0，n}
观察这个式子，可以将它写成如下形式：
[(-1)^0/0!＋(-1)^1/1!＋(-1)^2/2!＋(-1)^3/3!＋，…，＋(-1)^n/n!]*n!
这与e^x的泰勒级数非常像，当x=-1时，展开成级数的形式两边再乘以n!，有
n!/e=[(-1)^0/0!＋(-1)^1/1!＋(-1)^2/2!＋(-1)^3/3!＋，…，＋(-1)^k/k!+…]*n!
可见n!/e与其非常相近，如果手边有计算器的话，可以直接计算n!/e保留到整数来计算排列数。
A(1)∪A(2)∪A(3)…∪A(m)会表示什么呢？（m＜n）有人会不耐烦，考虑那么多干什么呢？如果不去认真分析，半途而废的话，将错过比较重要的错位问题的推广，这才让我们意识到“子不学，断机杼”的故事有多么重要。
A(i1)∪A(i2)∪A(i3)…∪A(im)表示信件序号为i1或i2或i3或……或im放对的情况，我们应该知道
Card(A(1)∪A(2)∪A(3)…∪A(m)）=Card(A(i1)∪A(i2)∪A(i3)…∪A(im)）
因为一共有m个集合，那么其的并集的元素个数为
Card(A(i1)∪A(i2)∪A(i3)…∪A(im)）
=∑Card（A(ij)）－∑Card（A(ij)∩A(ik)）＋∑Card（A(ij)∩A(jk)∩A(il)）－，…，－(-1)^m*Card(∩A(ij))
=m(n－1)!－C{2，m}(n－2)!＋C{3，m}(n－3)!－，
…，－(-1)^p*C{p，m}(n－p)!－，…，
－(-1)^m*C{m，m}(n－m)!
（当然，这里的ij=1，2，3，…，n）所以我们有，至少m封信放错的不同组合数为
n!－m(n－1)!＋C{2，m}(n－2)!－C{3，m}(n－3)!＋，
…，＋(-1)^p*C{p，m}(n－p)!＋，…，＋(-1)^m*C{m，m}(n－m)!
=n![1－C{1，m}/A{1，n}＋C{2，m}/A{2，n}－C{3，m}/A{3，n}＋，
…，＋(-1)^p*C{p，m}/A{p，n}＋，
…，＋(-1)^m*C{m，m}/A{m，n}]
首先，我们的题目是：一共有n封信和n个信封，且每个信封里只能装一封信，若求每封信都不装在自己信封里的排列数。
我们的公式是：
A{n－2，n}－A{n－3，n}＋，…，＋(-1)^i*A{n－i，n}＋，…，＋(-1)^n*A{0，n}
写成求和符号的形式：
∑{p=2，n}(-1)^p*A{n－p，n}
对于这道题的推广，若求至少有m封信放错的排列数，我们的公式是：
n![1－C{1，m}/A{1，n}＋C{2，m}/A{2，n}－C{3，m}/A{3，n}＋，
…，＋(-1)^p*C{p，m}/A{p，n}＋，
…，＋(-1)^m*C{m，m}/A{m，n}]
写成求和符号的形式：
∑{p=0，m}(-1)^p*C{p，m}/A{p，n}
本文用到的符号解释：
C{m，n}=n!/m!(n－m)!
A{m，n}=n!/(n－m)!
注意集合A(i)与A{m，n}不同
∑{k=0，n}a(k)=a(0)＋a(1)＋a(2)＋，…，＋a(n)
喜欢
0
赠金笔
前一篇：原创球面三角形面积公式推导