不动点与组合问题（学生版）.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)!(-)！，%二(TP4!-3!4!,a3q2(-1)33!2!3!%_(-D22!7T-2!将上述-1个式子累加，得：%6(-1)(-1,上JT)4,(TV(-I)?n1!n(w-l)!4!3!2!所以生=+LL+出，故q=/+LL+3/!1!

3、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.10C.12D.20分析此题也是错位重排但不是全部错位，我们可以部分应用错位重排来进行解题.解析分步进行：第一步，选出三个瓶子，这三个瓶子恰

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

5、素全错位排列的方法数,则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)成立，即k个元素片,出吗，4全错位排列的方法数的递推关系为A(R)=hA(l)+(T,贝U当=攵+1时,设全错位排列的元素为4，%,%，441.在k个元素，4全错位排列的基础上，攵+1个元素全错位排列后，它们全错位排列的方法分为2类：1与q(i=l,2,互调

6、位置，其余元素全错位排列，方法数为kA(%T);1在q(i=L2,/)的位置上，但4不在心的位置上，其余元素仍然错位排列.这样的排列，相当于将k个元素%心,%，%的每一个全错位排列中的元素置换了一遍k个元素。%，%的每一个全错位排列是k个元素，因此该类全错位fl例的方法数为&A（八）.综上所述，A(k+l)=hA(k)+A(k-l),又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()=nA(n-1)+(l),(n2).定理用

7、A()表示n个不同元素所有的全错位排列的方法数，则当=1时，A(I)=O;当2时，v72!3!4!(-1)!nv7vfn个不同元素排成一列，记下每个元素的编号，重新排列后，有以下结论：推论1某i个元素(特定)现在的编号与原编号一致，-，个元素现在的编号与原编号错位的排列方法数为推论2i个元素(不特定)现在的编号与原编号一致，-，个元素现在的编号与原编号错位的排列方法数为CA(-i)推论3某i个元素(特定)在原有的位置上互相全错位，另，7T个元素在原有的位置上互相全错位，这样的排列数为推论4i个元素(不特定)在原有的位置上互相全错位，另-i个元素在原有的位置上互相全错位,这样的排列数为CA(i)

8、A(T)例I同寝室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺卡，则4张贺卡不同的分配方式有种.解该题属于4个元素的全错位问题.由定理得A(4)=43-4+1=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(直

9、接法)至多2个号码一致，分3种情况：(1)“恰2个一致”等价于“恰3个错位，乂=CA(3)=20;(2)“恰1个一致”等价于“恰4个错位，M=屐A(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个项目的测试，每位同学上、下午各测试

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

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

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

13、4lim.mn=!一CXn-1)!+C：5-2)!-+(一1尸禽(一加!+(-1)=后(川十=O定理4.（八）=力4(n)=nJt-O-0证明：因为n个元素的全排列个数为!.另一方面考虑可分成恰好零个组合不动点，恰好一个组合不动点，恰好两个组合不动点，恰好n个组合不动点，由加法原理有：G(O)+%(l)+/(2)+%()=/(&)=！，类似地可得到(2)=！A=OA=O定理5.从编号为123,的n个元素，取出k个(1左)元素排在编号为123,次的位置上(每一个位置只允许排一个元素)，有k个动点的排列个数为：心（八）=MY肥+C比嚏-C嘿+(T)P*Z(Tync.m=0当=k时，即定理3.故定理

14、5可视为定理3的推广.例1.设有编号1,2,3,4,5的五个球和编号为1,2,3,4,5的五个盒子.现将这五个球投入这五个盒子内，要求每个盒子投放一个球，求以下几种情况的投放方法数.恰好有两个球的编号与盒子编号相同；恰好没有两个球的编号与盒子编号相同；至多有两个球的编号与盒子编号相同；至少有两个球的编号与盒子编号相同.解：M=佻(2)=CV(3)=20=103!l-+-I1!2!3!=八(2)=。(2)=10、2!(1-t+/卜10Ns=例(O)+BI)+S5(2)=C?(5)+C%(4)+C= 5!1- + -1! 2! 3! 4! 5!+0+5x4!+1! 2! 3! 4!+ 103! I

15、Ti+)=44+45+20=109M=侬(2)+83(3)+85(4)+侬(5)=C0(3)+V(2)+G0(1)+1=20+10+0l=31或N4=5!-q(0)+弘(l)=120-(44+45)=31.例2.同室4人各写1弓长贺年卡，先集中起来,然后每人从中拿I张别人送出的贺年卡，问：4张贺年卡有多少种不同的分配方法.解：本题即求四个元素的无不动点排列个数.(4)=4!l-l+l-l+=9.该题与一道波兰数学竞赛(19601961年)题类似,其原题为某人给6个不同的收信人写了6封信，并且准备了6个写有收信人地址的信封.问：有多少种装入信笺的方法，使每一信笺与信封上的收信人都不相符？”由题意

16、即得(6)=6(l-l+l-ll-ll=265(f1).以上两题实际上均为著名的Bemoulli-Euler装错信笺问题的特殊情况.例3.P为集合S.=l,2,3,的一个排列，令。为S”的无不动点的排列个数，g.为恰好有一个动点的排列个数，证明：-g,J=L证明：因为=()=E(T)XWX=OK.“一11Sn=%(1)=&0(-1)=山(-1)，(-1)七A-OK.T1=!力(T)Y*-0K-所以|力-g=卜!叁TAt-N(-1S=w!(-1)-=(-1=1.例4.设？（八）表示n个元素中有k个不动点的所有排列的种数.求证：E火匕(女)=!.=0证明：S牝=Syg(-&)Jt=O*=0=力。花

17、”(0)k-ln-I=c3h(o)*=0=C-J(I)4=0一I=T（八）A=O=(7-l)!=w!定理6.编号为1,23,的n个元素排在编号为1,2,3,的位置上(每个位置只排一个元素).则指定某k(l%)个元素为动点的排列个数为：广“(止火(-Dy)!ZM=O证明：若指定某MIWZM个元素中的第i个元素，正好在第i个位置上，其他-1个元素放在-1个位置上，则所有的排列数为C而指定的某k个元素中的第i和j个元素恰好在第i和j的位置上，其他-2个元素全排列时，所有的排列数为。晨-2)!.同理，若指定的k个元素其编号都排在与其编号相同的位置上时，有(-%)!种排法.由容斥原理得：二仅)=!_以(

18、1)!十盘(2)!+(-2)!=(-lC(w-n)!m=0例5.将编号为1,2,3,.,9的九个球放入编号为1,2,3,.,9的九个盒内.要求每盒放一个球，且规定奇数k号的球不许放在奇数k号盒内,这样的投放方法有多少种？解：本题是求指定五个元素为动点的排列个数,利用定理6有：八(5)=(-1)59-?)！ZM=O=9!-C；8!+C：7!-C；6!+C；5!-C；4!=205056(种)例6.上届获得前n名的球队参加本届争夺前n名的比赛.如果不设并列名次，问：若没有一个队取得的名次恰好紧接在上届比他高一个名次的球队之后,那么比赛结果有多少种可能？解：设上届获得前n名的n个球队按名次的一个排列为

19、(对出，/，为)，这里不妨将球队号也按上述顺序排列，由题意可知，本届比赛出现的名次不可能有以下排列：4%+IMMlX4+2，Mi4的,MZITG=I2，-1)实际上就是，编号为123,的n个元素排在编号为1,23,的位置上(每个位置只排一个),指定T个元素为动点的排列个数为：U(-)=my(,Li)!+C3(-2)!-(-r,c:,-l=Z(T)(3(-叫m=0【强化训练01】1 .如图，一环形花坛分成AB,C,。四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为【强化训练02】2 .某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要在如图所示的6个点

20、A、B、GA小B/、G上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有种(用数字作答).【强化训练03】3 .如图，用四种不同颜色给图中的AB,C,D,E,F六个点涂色，要求每个点涂一种颜色，且图中每条线段的两个端点涂不同颜色，则不同的涂色方法用A . 288 种B . 264 种【强化训练04】C . 240 种D . 168 种4 .有4位同学在同一天的上、下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”五个项目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不测“握力”项目，下午不测“台阶”项目,其余项目上、下午都各测

21、试一人.则不同的安排方式共有种（用数字作答）.【强化训练05】5 .将字母a,a,bhc,c,排成三行两歹!L要求每行的字母互不相同，每列的字母也互不相同，则不同的排列方法共有A.12种B.18种C.24种D.36种【强化训练06】6 .将用16编号的六张卡片，插入用16编号的六个盒子里，每只盒子插一张，求：使每一卡片的号码与所在盒子号码都不同的插法总数；恰好有3张卡片号码与所在盒子号码相同的插法总数.【强化训练07】7 .个学生参加一次聚会，每人带一张贺卡和T牛礼物,会后每个人任取一张贺卡和一件礼物.问：发生下列情况时，有多少种可能？没有任立学生取回他原来自己的T牛物品；（2）有人取回了他原来的物品；恰好只有一人取回他原来的物品.【强化训练08】8 .从编号为1,2,3,4,5的五个元素中取出3个元素，排在编号为1,2,3的位置上（每个位置只许排一个元素）.求：元素的编号与所处位置的号码不相同的排法.【强化训练09】9 .6名教师从星期一至星期六值日，若甲教师不排星期一，乙教师不排星期二，丙教师不排星期三，则不同的值日排法有多少种？