不动点与组合问题(解析版).docx

上传人:王** 文档编号:903596 上传时间:2024-02-26 格式:DOCX 页数:15 大小:75.32KB
下载 相关 举报
不动点与组合问题(解析版).docx_第1页
第1页 / 共15页
不动点与组合问题(解析版).docx_第2页
第2页 / 共15页
不动点与组合问题(解析版).docx_第3页
第3页 / 共15页
不动点与组合问题(解析版).docx_第4页
第4页 / 共15页
不动点与组合问题(解析版).docx_第5页
第5页 / 共15页
不动点与组合问题(解析版).docx_第6页
第6页 / 共15页
不动点与组合问题(解析版).docx_第7页
第7页 / 共15页
不动点与组合问题(解析版).docx_第8页
第8页 / 共15页
不动点与组合问题(解析版).docx_第9页
第9页 / 共15页
不动点与组合问题(解析版).docx_第10页
第10页 / 共15页
亲,该文档总共15页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《不动点与组合问题(解析版).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!a3a2(-1)33T273;出4二(一1)22!Ti2!将上述-1个式子累加,得:q(T)”(T产(-1)4(-1)3(-1)2= !/+, 1! 2! 3!=-111n1!n(-1)!4

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

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

5、不相同.三、问题的推论与探究引理用A()表示n个不同元素全错位排列的方法数,则n个不同元素全错位排列的方法数满足Ae)=hA(w-1)+(-1)11(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)+(T)4=9,式(1)成立.(2)假设M43)时,式(1)成立,即k个元素4,/吗,4全错位排列的方法数的递推关系为A(k)=RA(女_1)+(1)人,则当=女+1时,设全错位排列的元素为4吗,/,&,4+1.在女个元素4,出,%,4全错位

6、排列的基础上,左+1个元素全错位排列后,它们全错位排列的方法分为2类:4讨与4(i=l,2,互调位置,其余元素全错位排列,方法数为hA(Z-l);4讨在q(i=12,2)的位置上,但可不在可句的位置上,其余元素仍然错位排列.这样的排列,相当于+1将卜个元素4,4,%,%的每一个全错位排列中的元素置换了一遍k个元素对出,生,%的每一个全错位排列是k个元素,因此该类全错位排列的方法数为AA(八).综上所述,4(2+l)=hA(八)+%A(Z-I),又A(L)=hA(1)+(T)A,A(+1)=A(Zc)+A(-1)=A()+A()-(-1)a=(+l)A()+(-l+,.即当=A+1时,式(1)成

7、立.因此,n个元素全错位排列的方法数的递推关系为A(z)=wA(-1)+(-1),(112).定理用A()表示n个不同元素所有的全错位排列的方法数,则当=1时,A(I)=O5当2时,+(+(!+g+9=(w(一1)(注1).J2!3!4!(-1)!n,v7v)个不同元素排成一列,记下每个元素的编号,重新排列后,有以下结论:推论1某i个元素(特定)现在的编号与原编号一致,-,个元素现在的编号与原编号错位的排列方法数为推论2i个元素(不特定)现在的编号与原编号一致,-i个元素现在的编号与原编号错位的排列方法数为CA().推论3某i个元素(特定)在原有的位置上互相全错位,另T个元素在原有的位置上互相

8、全错位,这样的排列数为A(i)A(-i).推论4i个元素(不特定)在原有的位置上互相全错位,另T个元素在原有的位置上互相全错位,这样的排列数为CA(i)4(-i)例1同寝室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺卡,则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得,投放种数为

9、GA(3)=10(37)=20例3编号为1,2,3,4,5的5个人,分别坐在编号为1,2,3,4,5的座位上,则至多2个号码一致的坐法有多少种?解法1(直接法)至多2个号码一致,分3种情况:“恰2个一致”等价于“恰3个错位,N=GA(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=1201

10、01=109.例4有4位同学在同一天的上、下午参加“身而与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”5个项目的测试,每位同学上、下午各测试一个项目,且不重复.若上午不测“握力”项日,下午不测“台阶”项目,其余项目上、下午都各测试一人,则不同的安排方式共有多少种?解4位同学上午测试“身窗与体重”、“立定跳远”、“肺活量”、“台阶”4个项目的方法数为A:=24种.下午测试的方法分为2类:(1)4位同学测试的项目仍然是上午的4个项目,方法数是4个元素的全错位排列数,只需将每一个全错位排列中的“握力”项目替换为“台阶”,方法数为4(4)=9;(2)若测“台阶”的同学刚好测“握力”项目,则方法

11、数为A(3)=2.故下午测试的方法数共有9+2=11种.从而上、下午不同的安排方式共有24(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种不同

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

13、=l,且n个元素的全排列为!.由容斥原理有:S)=!一4+4c4一ialw+(-i),Z4c4cc4+.+(-1)”4c4c.c4lim.an=n!-Cxnn-1)!+Cqnn-2)!-+(-1)(/?勿)!+(-1),1111(-l)w(T)”1!2!3!mnJ1=!(T)*A=Ok定理4.%”(Z)=XZ1()=!A=OA=O证明:因为n个元素的全排列个数为!.另一方面考虑可分成恰好零个组合不动点,恰好一个组合不动点,恰好两个组合不动点,恰好n个组合不动点,由加法原理有:n+/+%(2)+n=(&)=!,类似地可得到Sfn(k)=nA=O=0定理5.从编号为1,2,3,的n个元素,取出k个

14、(Ik)元素排在编号为1,2,3,k的位置上(每一个位置只允许排一个元素),有k个动点的排列个数为:f(k)=E-以用+CiEEW-c:P+TW=t(yncgm=0当=左时,即定理3.故定理5可视为定理3的推广.例1.设有编号1,2,3,4,5的五个球和编号为1,2,3,4,5的五个盒子.现将这五个球投入这五个盒子内,要求每个盒子投放一个球,求以下几种情况的投放方法数.恰好有两个球的编号与盒子编号相同;恰好没有两个球的编号与盒子编号相同:至多有两个球的编号与盒子编号相同:至少有两个球的编号与盒子编号相同.解:N=%(2)=C=103!1|=20(1!2!31JNz=A(2)=C=10x2!(l*S=l乂=科(0)+。5(1)+%(2)=以(5)+(4)+73)ct(t11111、=/1111、,八o,111A=5!1+54!1+103!1+(1!2!3!4!51J(1!2!3!4!J1!2!3!J=44+45+20=109M=(2

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 高等教育 > 理学

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!