不动点与组合问题（学生版）.docx

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

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

2、中目号码均不相同， 故有方法数为。“一种.所以，一般地，我们得到递推公式 =(z2-1)(-2-i)(3),其中 4 =0,% =L利用这个公式，我们可以解决这类错位排列问题.二、探求通项公式由递推公式及4 =0，% = 1吗=2 ,可得：g-(TMT= =(-1尸3-3)=(T)I =(-1)”，上式两边同乘以!得：殳_u-=1121n (-1)!于是可得：% k (T 产(w-l)! (w-2)! ( -)！，% % 二(TP 4!-3! 4!,a3 q2 (-1)3 3!2! 3!%_ (-D22!7T- 2!将上述-1个式子累加，得：% 6 (-1) (-1,上 JT)4 ,(TV (

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

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

5、) = 4(2+9) = 44 ,6=5(4+4) = 5(9+44) = 265.故共有265种投放信笺的方法,使得每份信翔口信封上的收信人都不相同.三、问题的推论与探究引理 用A()表示n个不同元素全错位排列的方法数,则n个不同元素全错位排列的方法 数满足A() = AeT)+ (T)52).( 1 )下面用第二数学归纳法给出引理的一般性证明.证明(1 )易知当 =2时,A(2) = 1,A(3) = 2 ,满足A=3A+(-N =2 ,式(1 )成立;当 =3时，A= 2,A(4)=9 ,满足4)= 4沟3) + (-1)4=9 ,式(1 )成立(2 )假设A(Z3)时，式(1 )成立，

6、即k个元素片,出吗，4全错位排列的方法数的 递推关系为A(R) = hA(l) + (T ,贝U当=攵+ 1时,设全错位排列的元素为4，%,%，441 .在k个元素，4全错位 排列的基础上，攵+ 1个元素全错位排列后，它们全错位排列的方法分为2类：1与q(i = l,2, ,互调位置，其余元素全错位排列，方法数为kA(%T);1在q(i = L2, /)的位置上，但4不在心的位置上，其余元素仍然错位排列.这样的 排列，相当于将k个元素%心,%，%的每一个全错位排列中的元素置换了一遍k个元 素。%，%的每一个全错位排列是k个元素，因此该类全错位fl例的方法数为& A(A). 综上所述，A(k+l

7、) = hA(k)+A(k-l),又 A(A) = ZA(A7) + (T)故 A(Z+ 1) = ZA(4)+女A(4-l) = ZA(Z) + A(k)-(-iy=(k + l)A(Z)+(-iyz.即当“ = A + 1时，式(1 )成立.因此,n个元素全错位排列的方法数的递推关系为4() = n A(n -1) + (l),(n2).定理 用A()表示n个不同元素所有的全错位排列的方法数，则当 =1 时，A(I) = O ;当 2时，v 72!3!4!(-1)! n v 7 v fn个不同元素排成一列，记下每个元素的编号，重新排列后，有以下结论：推论1某i个元素(特定)现在的编号与原编

8、号一致，-，个元素现在的编号与原编号错位的排列方法数为推论2 i个元素(不特定)现在的编号与原编号一致，-，个元素现在的编号与原编号错 位的排列方法数为CA( -i)推论3某i个元素(特定)在原有的位置上互相全错位，另，7 T个元素在原有的位置上互 相全错位，这样的排列数为推论4 i个元素(不特定)在原有的位置上互相全错位，另-i个元素在原有的位置上互 相全错位,这样的排列数为CA(i)A(T)例I同寝室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺卡，则4张贺卡不同的分配方式有 种.解 该题属于4个元素的全错位问题.由定理得A(4) = 43-4+1=9 ,故分配方式有9种.

9、例2设编号为1 , 2,3,4,5的5个球及编号为1 , 2,3,4,5的5个盒子，一个盒子内放一球，恰有2个球的编号与盒子编号相同，则投放种数有多少？解“恰有2个球的编号与盒子编号相同”等价于“恰有3个球的编号与盒子编号不同”.由推论2得，投放种数为C1A(3) = 10(37) = 20例3编号为1 ,2, 3,4,5的5个人，分别坐在编号为1 ,2, 3,4,5的座位上，则至多 2个号码一致的坐法有多少种？解法1 (直接法)至多2个号码一致，分3种情况：(1 ) “恰2个一致”等价于“恰3个错位，乂 = C A(3) = 20 ;(2 ) “恰1个一致”等价于“恰4个错位，M =屐 A(

10、4)=45 ;(3 )没有一致”等价于“5个全错位“，M=A(5)= 44.从而 N = N+m + m=109.解法2 (间接法)无任何限制条件时，M = 120.“恰有3个号码一致”等价于“恰有2个错 位 N =A(2) = 10 :怡有4个号码一致”与“恰有5个号码一致”的坐法属同一种情况， 故 M =1.从而N = M-M-N2 =120 - 10-1 = 109.例4有4位同学在同一天的上、下午参加“身高与体重:“立定跳远”、“肺活量:“握力”、 “台阶”5个项目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不测“握力” 项日，下午不测“台阶”项目，其余项目上、下午都各测试

11、一人，则不同的安排方式共有多少 种？解4位同学上午测试“身高与体重”、“立定佻远”、“肺活量:”台阶”4个项目的方法数为 4： =24 种.下午测试的方法分为2类：(1 ) 4位同学测试的项目仍然是上午的4个项目，方法数是4个 元素的全错位H例数，只需将每一个全错位排列中的“握力”项目替换为“台阶”，方法数为 A(4) = 9 ;(2)若测“台阶”的同学冈财测“握力”项目，贝历法数为A(3) = 2.故下午测试的方 法数共有9 + 2 = 11种.从而上、下午不同的安排方式共有24(9 + 2) = 264种.第二节 组合不动点组合不动点问题的反面提法是“扰排问题定义：设集合仍(I)I/，/(

12、)是集合123, ,的一个排列，若/=攵化=1,2,3,)，则称k为变换F的一个组合不动点，我们用(Z)表示n个元素有k个组合不动点的排列个数， (A)表示有k个动点的排列个 数显然有，?=力(- A)例6)=1.定理 1 (Z)=UzlG-A).证明：所有G (A)的排列数问题可分二步思考.首先，从个元素中选出k个元素排在k个位 置上，使每个元素的编号与它所在位置的号码一致(不动)，共有C种不同的排法，其次, 将其余-攵个元素排在-攵是个位置上使每个元素的编号与它所在位置的号码不一致(全 动)，有44(A)种排法，由乘法原理,故原命题得证.定理 2/候)= CZk(A).证明：，(女)=由5

13、-%) =。；/-5-k) = c(A)定理 ”()= ! (T)* % =0H -证明：考虑第k号元素正好放在第k号位置上，显然，其余 -1个元素放在-1个位置上的所有排列数4为( -1)!,且和式Z 4共有C：项，所以 4 =(”1)! 1lkn而A 一汽的排列数为( -2)! z和式. 4 c 4共有C：项. 12IT所以 4 + 4 =，；(_ 2)!同理，4 C4c.c4的排列数为(-加！，和式 4c4 Cc4共有 1j. .xv?C：项.所以 4 C 4 C . c 4 = C： S -勿)！ ly. .an显然，4 c4c.c4 = 1 ,且n个元素的全排列为 !.由容斥原理有：

14、f ()= J 4 + 4 c 4 一 1XV149+ (-i) Z 4 c4 cc4 + + (-1)”4 c% c. c4 lim. .mn=!一 CXn - 1)!+ C：5 -2)!-+ (一1尸禽( 一加!+ + (-1)=后(川十=O 定理 4.(A) =力4 (n) = nJt-O-0证明：因为n个元素的全排列个数为!.另一方面考虑可分成恰好零个组合不动点，恰好一个组合不动点，恰好两个组合不动点，恰好n个组合不动点，由加法原理有：G(O)+ %(l) + /(2)+ +%()= /(&) = ！，类似地可得到(2) = ！ A=OA=O定理5.从编号为123,的n个元素，取出k个(1左)元素排在编号为123,次的位置上(每一个位置只允许排一个元素)，有k个动点的排列个数为：心(A)=M Y 肥+C比嚏-C嘿+ +(T)P*Z(Tync.m=0当 =k时，即定理3.故定理5可视为定理3的推广.例1 .设有编号1,2,3,4,5的五个球和编号为1,2,3,4,5的五个盒子.现将这五个球 投入这五个盒子内，要求每个盒子投放一个球，求以下几种情况的投放方法数.恰好有两个球的编号与盒子编号相同；恰好没有两个球的编号与盒子编号相同；至多 有两个球的编号与盒子编号相同；至少有两个球的