不动点与组合问题 （解析版）.docx

《不动点与组合问题 （解析版）.docx》由会员分享，可在线阅读，更多相关《不动点与组合问题 （解析版）.docx（15页珍藏版）》请在第一文库网上搜索。

1、不动点与组合问题不对号入座与全错位排列一、问题把n个编号为1,2,3, ,(,亚2)的球放入11个编号为1,2,3, (2)的盒子中，要求每 个盒子中只放一个球，且球的号码与盒子的编号数均不相同，试求有多少种不同的放法 种数？这个问题就相当于n个自然数的全错位排列问题.不妨设这种不同的放法种数有凡种， 它可以分两步完成：第一步放编号为1的球，共有-1种放法，此时不妨把编号为1的 球放在编号为用工1)的盒子里，再安排第i号球的位置，有两种情况：第i号球放在第1个盒子中，剩余的-2个球要放在-2个盒子中，依然要求是号码 均不相同，故种放法；第i号球不放在第1个盒子中，此时如同-1个球要放在T个盒子

2、中，且号码均不相同，故有方法数为4种.所以，一般地，我们得到递推公式Qn = ( 一 l)(4-2 + % )( 之 3),其中 4 =0,2 =1.利用这个公式，我们可以解决这类错位排列问题.二、探求通项公式由递推公式及4=0，/=1吗=2,可得：4 -叫T = -% -(T)* = =(T)13 -34)=(-l)2 = (-1),上式两边同乘以乙得：凡 二(T)“！ (n-l)!！于是可得：%* . (T)R(-l)! (-2)! (-l)!,包 生 二(一1。4!-3! 4!a3 a2 (-1)33T27 3;出 4 二(一 1)22!Ti 2!将上述-1个式子累加，得：q(T)”(T

3、 产(-1)4(-1)3(-1)2= ！/+， 1! 2! 3!= - 1 n 1! n(-1)!4!3!2!所以M = JI+_LJ_+. +1!21,故凡 n 1! 2! 3!“！评注由递推公式得到递推公式是求解的关键，这也是处理复杂递推数列问题的难 点所在.例1同室四人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺年卡，则四张贺年卡不同的分配方式有()A.6 种. B.9 种. C.11 种. D.23 种.分析 此题是全错位排列问题，我们可以应用公式来进行解题.解析 由递推公式及=1R =2,可得=3(+%) = 3(l + 2) = 9.故选B.例2五个瓶子都贴了标签，其

4、中恰好贴错了三个，贴错的可能情况共有()种.A.6B.10C.12D.20分析此题也是错位重排但不是全部错位，我们可以部分应用错位重排来进行解题.解析 分步进行：第一步，选出三个瓶子，这三个瓶子恰好贴错了，有C； = 10种；第二步，这三个瓶子满足错位重排，所以对应的公式数据应该是2.最后根据乘法原理，共 有10x2 = 20种.故选D.例3某人给6个不同的人写了6封信，每人一份，并准备了6个写有收信人地址的信 封，问有多少种投放信笺的方法，使得每份信笺和信封上的收信人都不相同？ 分析：此题是全错位排列问题，我们可以应用公式来进行解题.解析 由递推公式及出=L%=2,可得:a4 =3(/ +j

5、)=3(l+2)=9,5 =4(d3 +4 ) = 4(2+9) = 44 ,Ci6 =5(4 +0i) = 5(9 + 44) = 265.故共有265种投放信笺的方法，使得每份信笺和信封上的收信人都不相同.三、问题的推论与探究引理 用A()表示n个不同元素全错位排列的方法数，则n个不同元素全错位排列的方法数满足 Ae) = hA(w-1) + (-1)(i2).(1)下面用第二数学归纳法给出引理的一般性证明.证明 (1)易知当 =2时，A= LAG) = 2,满足A= 3A(2)+(T)3=2,式(1)成立；当 =3时，A(3) = 2,A(4) = 9,满足A(4) = 44(3) +

6、(T)4 =9,式(1)成立.(2)假设M43)时，式(1)成立，即k个元素4，/吗，4全错位排列的方法 数的递推关系为A(k) = RA(女 _1) + (1)人，则当=女+1时,设全错位排列的元素为4吗，/，&，4+1.在女个元素4，出，%，4全 错位排列的基础上，左+ 1个元素全错位排列后，它们全错位排列的方法分为2类： 4讨与4(i = l,2,互调位置，其余元素全错位排列，方法数为hA(Z-l);4讨在q(i = 12 ,2)的位置上，但可不在可句的位置上，其余元素仍然错位排列.这样的排列，相当于+1将卜个元素4，4，%，%的每一个全错位排列中的元素置换了一 遍k个元素对出，生，%的

7、每一个全错位排列是k个元素，因此该类全错位排列的方法 数为AA(A).综上所述，4(2 + l) = hA(A)+%A(Z-I),又 A(L) = h A(1)+(T)A,A( + 1) = A(Zc) + A(-1) = A()+A()-(-1)a =( + l)A()+(-l+,.即当 = A + 1时，式(1)成立.因此，n个元素全错位排列的方法数的递推关系为A(z) = w A(-1)+(-1),(2).定理 用A()表示n个不同元素所有的全错位排列的方法数，则当 =1 时，A(I) = O5当 2时，+(+(!+ +g+9=(w(一1)(注1). J 2!3!4!(-1)! n ,

8、v 7 v )个不同元素排成一列，记下每个元素的编号，重新排列后，有以下结论: 推论1某i个元素(特定)现在的编号与原编号一致，-，个元素现在的编号与原编 号错位的排列方法数为推论2 i个元素(不特定)现在的编号与原编号一致，-i个元素现在的编号与原编 号错位的排列方法数为C A().推论3某i个元素(特定)在原有的位置上互相全错位，另T个元素在原有的位置 上互相全错位，这样的排列数为A(i)A(-i).推论4 i个元素(不特定)在原有的位置上互相全错位，另T个元素在原有的位置上互相全错位，这样的排列数为CA(i)4(-i)例1同寝室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的

9、贺卡，则4张贺卡不同的分配方式有 种.解 该题属于4个元素的全错位问题.由定理得4(4) = 4x3-4+l=9,故分配方式有9种.例2设编号为1, 2, 3, 4, 5的5个球及编号为1, 2, 3, 4, 5的5个盒子，一个盒 子内放一球，恰有2个球的编号与盒子编号相同，则投放种数有多少？解“恰有2个球的编号与盒子编号相同”等价于“恰有3个球的编号与盒子编号不同”.由推论2得，投放种数为GA(3) = 10(37) = 20例3编号为1, 2, 3, 4, 5的5个人，分别坐在编号为1, 2, 3, 4, 5的座位上，则 至多2个号码一致的坐法有多少种？解法1 (直接法)至多2个号码一致，

10、分3种情况：“恰2个一致”等价于“恰3个错位，N= G A(3) = 20 ；(2) “恰1个一致”等价于“恰4个错位”,M=/A(4) = 45;(3)没有一致”等价于“5个全错位”,M = A(5) = 44.从而 N = M+ N2 + M = 109.解法2 (间接法)无任何限制条件时，6 =120.“恰有3个号码一致”等价于“恰有2个错位，M= C；xA(2)= 10； ”恰有4个号码一致”与“恰有5个号码一致”的坐法属同一种情况，故M=I.从而N =120 10 1 = 109.例4有4位同学在同一天的上、下午参加“身而与体重”、“立定跳远”、“肺活量”、“握 力”、“台阶”5个项

11、目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不 测“握力”项日，下午不测“台阶”项目，其余项目上、下午都各测试一人，则不同的安排 方式共有多少种？解4位同学上午测试“身窗与体重”、“立定跳远”、“肺活量”、“台阶”4个项目的方法数 为A： =24种.下午测试的方法分为2类：(1) 4位同学测试的项目仍然是上午的4个项目，方法数是 4个元素的全错位排列数，只需将每一个全错位排列中的“握力”项目替换为“台阶”，方 法数为4(4)=9； (2)若测“台阶”的同学刚好测“握力”项目，则方法数为A(3) = 2.故下 午测试的方法数共有9+2 = 11种.从而上、下午不同的安排方式共有24

12、(9 + 2) = 264种.第二节组合不动点组合不动点问题的反面提法是“扰排问题”定义：设集合尸1(2),尸(3),尸是集合1,2,3, M的一个排列，若F(k) = k(k = 1,2,3, ,)，则称k为变换F的一个组合不动点，我们用外年)表示n个元素有k个组合不动点的排列个数，ZI(R)表示有k个动点的排列个数.显然有，n(k) = fn(n-k)9(n) = l.定理 LeQ) = C证明：所有外(Q的排列数问题可分二步思考.首先，从n个元素中选出k个元素排在k 个位置上，使每个元素的编号与它所在位置的号码一致(不动)，共有G种不同的排法， 其次，将其余-攵个元素排在-攵是个位置上，

13、使每个元素的编号与它所在位置的号 码不一致(全动)，有工(-A)种排法，由乘法原理，故原命题得证.定理 2(Z) = C(Z).证明：工0) = 4G) = C%h)一( j) = C(k)定理3 () = ! W(Ty A=O 证明：考虑第k号元素正好放在第k号位置上，显然，其余-1个元素放在-1个位置 上的所有排列数4为(-1)!,且和式 4共有C：项，所以 4 =Cs -1)!*kn而4门4的排列数为(-2)!,和式 4 C 4共有项.所以 4 + 4 = (-2)!Ja同理，4 C 4 CC 4的排列数为(”加！，和式C 4c C 4共有C；项.所以 4 C cc4 =窘(一同！ iJ

14、. .n显然，4c%c.c4 = l,且n个元素的全排列为 !.由容斥原理有：S) = !一 4 + 4 c 4 一 ialw+ (-i), Z 4 c 4 c c 4 + . + (-1)” 4 c 4 c. c 4 lim. .an=n!- Cxnn - 1)!+ Cqnn -2)!-+ (-1)(/?勿)!+ (-1),1 111(-l)w(T)”1! 2! 3!m n J1=!(T)*A=O k 定理 4.%”(Z) = XZ1 ()= ！ A=OA=O证明：因为n个元素的全排列个数为!.另一方面考虑可分成恰好零个组合不动点，恰 好一个组合不动点，恰好两个组合不动点，恰好n个组合不动点，由加法原理有: n +/ + %(2) + +n =(&) = !，类似地可得到 Sfn (k) = nA=O=0定理5.从编号为1,2,3,的n个元素，取出k个(Ik)元素排在编号为1,2,3, ,k 的位置上(每一个位置只允许排一个元素)，有k个动点的排列个数为：f(k)=E -以用+CiEEW -c： P+ +TW=t(yncgm=0当=左时，即定理3.故定理5可视为定理3的推广.