组合数学幻灯片33错-排-问-题课件.ppt

考虑如下问题：在一次宴会中，有n个人把他们的帽子放在衣帽间内问有多少种方法交还他们的帽子，使得没有一个人得到他们自己原来的帽子这个问题实质上是一个错排问题3.3 3.3 错错 排排 问问 题题用用1 1，2 2，n n表示表示n n位来宾第位来宾第i i位来宾位来宾的帽子是的帽子是i i号发帽方式可用下面的形式表号发帽方式可用下面的形式表示：示：客人客人1 2 1 2 i i n n 帽子帽子a a1 1a a2 2a ai ia an na a1 1a a2 2a ai ia an n是是1,2,1,2,n,n的一个排列，的一个排列，要使得没有一位客人领到自己的帽子，就要使得没有一位客人领到自己的帽子，就一定要有一定要有a ai iii,(,(i i=1,2,=1,2,n),n)这样一来，这样一来，问题就变成要求出有多少个问题就变成要求出有多少个1,2,1,2,n,n的全排列，使得对所有的的全排列，使得对所有的i i都有都有a ai iii ，我们称这种排列为我们称这种排列为错排错排用D Dn n表示错排的表示错排的个数于是有下面的关于错排计数定理于是有下面的关于错排计数定理其结论就是这个问题的解答。

其结论就是这个问题的解答证明：令S是1,2,n的所有全排列组成的集合，则S S=n!=n!又在集合S中定义性质pi为ai=i(i=1,2,n)一个排列a1a2aian，如果某个ai=i，我们就说该排列具有性质pi，又令Ai(i=1,2,n)是S中具有性质pi的排列所组成的子集合当n1时，有这样一来，这样一来，就是就是1,2,1,2,n,n的所有错排组成的集合的个数，的所有错排组成的集合的个数，因而因而有有 D Dn n=又因又因1,2,1,2,n,n的一个错排就是一个排列，的一个错排就是一个排列，并且这个排列不具有性质并且这个排列不具有性质p p1 1p p2 2p pi ip pn n中的中的任何一个性质，任何一个性质，由容斥原理容斥原理知 Dn=又又由由于于具具有有性性质质p p1 1的的排排列列一一定定在在第第一一个个位位置置上上是是1 1，故故集集合合A A1 1中中的的所所有有排排列列应应具具有有形式形式1i1i2 2i i3 3i in n，其其中中i i2 2i i3 3i in n是是集集合合2,3,2,3,n,n的的一一个全排列，个全排列，因此因此有有A A1 1=(n-1)!=(n-1)!。

同样同样有有A Ai i=(n-1)!,=(n-1)!,i i=2,=2,n,n又又由由于于具具有有性性质质p p1 1与与p p2 2的的排排列列形形式式一一定是定是12i12i3 3i in n ，其其中中i i3 3i in n是是3,4,3,4,n,n上上的的一一个个全排列，全排列，故故A A1 1AA2 2=(n-2)!=(n-2)!同样同样有有A Ai iAAj j=(=(n-2)!n-2)!(i ij;i,jj;i,j=1,2,=1,2,n n)一般地，同时具有性质p1p2pipk的排列个数为A1A2Ak=(n-k)!，其中1kn因为在集合1,2,n中取k个数的组合方式是，这样，具有k个性质的排列个数一共有(n-k)!将以上数值代入Dn的表达式即得本定理得证本定理得证错错排排问问题题的的实实质质是是：将将一一个个集集合合中中的的n n个个元元素素依依次次给给以以标标号号1 1，2 2，n n求求每每个元素都不在自己原来位置上的排列数个元素都不在自己原来位置上的排列数D6=265由公式(3.7)知，当n=5,6时有例如，例如，在1,2,1,2,9,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数。

这个问题实际上是1 1，3 3，5 5，7 7，9 9五个数的错排问题，由于由于e e-1-1可以表示成下列的无穷级数可以表示成下列的无穷级数故故于是有于是有即即 这表明，当n充分大时，Dn/n!近似等于e-1而Dn/n!是1,2,n的错排个数与它的全排列个数之比它表明我们随机地选择1,2,n的一个全排列是一个错排的概率也就是说，当n很大时，其错排的概率基本上是相当的另外错排数还具有如下的递归关系公式另外错排数还具有如下的递归关系公式证明：证明：1,2,n的错排可以分为互不相容的两种类型：(1)对于k2,3,n，令a1=k,ak=1由于a11，故选取a1的方法共有(n-1)种又由于a1=k，ak=1的值已定，故将剩下的n-2个数由2,3,k-1,k+1,n进行排列，D Dn n=(n-1)(D=(n-1)(Dn-1n-1+D+Dn-2n-2)(3.8)(3.8)故这样的排列个数为Dn-2由乘法规则知，此类型包含的错排数为(n-1)Dn-2由于 aii(i=2,3,k-1,k+1,n)(2)对于k2,3,n，令a1=k,ak1在这种情况下，选取a1的方法仍为(n-1)种但这时只有a1=k的值已定，且ak1，故将剩下的(n-1)个数由2,3,k-1,1,k+1,n作错排(这里将1看成k)，其错排数为Dn-1。

由乘法规则知，此类型的错排数为(n-1)Dn-1由于这两种类型互不相容，由由于这两种类型互不相容，由加法规则加法规则有有证毕证毕显然，显然，当当n=1n=1时，时，D D1 1=0,n=2=0,n=2时，时，D D2 2=1=1于 是对任意是对任意n n，由初值，由初值D D1 1=0,D=0,D2 2=1=1，及式，及式(3.8)(3.8)可计算出任何可计算出任何D Dn n之值解：解：从1,2,n中取r个数一共有 种方式，选定r后，其余还剩n-r个数不在原来的位置上，这相当于n-r个元素的错排，其错排数错排数为求1,2,n的全排列中，正好只有r(0rn)个元素在原来位置上的排列个数由乘法规则乘法规则知所求排列的个数为解解：显显然然，这这n n册册书书可可以以用用n!n!种种方方式式来来进进行行第第一一次次分分配配对对第第二二次次分分配配，由由题题意意知知，这这是是一一个个错错排排，其其分分配方式有配方式有D Dn n种设有n册书分给n个学生，之后又将这n册书收回重新分给这n个学生问有多少方式分配这n册书使得没有一个学生两次得到同一册书?由乘法规则乘法规则，所求的方式总数为。