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

不动点与组合问题不对号入座与全错位排列一、问题把n个编号为1,2,3,(,亚2)的球放入11个编号为1,2,3,"("2)的盒子中，要求每个盒子中只放一个球，且球的号码与盒子的编号数均不相同，试求有多少种不同的放法种数？这个问题就相当于n个自然数的全错位排列问题.不妨设这种不同的放法种数有凡种，它可以分两步完成：第一步放编号为1的球，共有-1种放法，此时不妨把编号为1的球放在编号为用工1)的盒子里，再安排第i号球的位置，有两种情况：第i号球放在第1个盒子中，剩余的-2个球要放在-2个盒子中，依然要求是号码均不相同，故种放法；第i号球不放在第1个盒子中，此时如同-1个球要放在T个盒子中，且号码均不相同，故有方法数为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!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分析此题也是错位重排但不是全部错位，我们可以部分应用错位重排来进行解题.解析分步进行：第一步，选出三个瓶子，这三个瓶子恰好贴错了，有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种投放信笺的方法，使得每份信笺和信封上的收信人都不相同.三、问题的推论与探究引理用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全错位排列的基础上，左+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)成立.因此，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个元素在原有的位置上互相全错位，这样的排列数为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得，投放种数为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=120101=109.例4有4位同学在同一天的上、下午参加“身而与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”5个项目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不测“握力”项日，下午不测“台阶”项目，其余项目上、下午都各测试一人，则不同的安排方式共有多少种？解4位同学上午测试“身窗与体重”、“立定跳远”、“肺活量”、“台阶”4个项目的方法数为A：=24种.下午测试的方法分为2类：(1)4位同学测试的项目仍然是上午的4个项目，方法数是4个元素的全错位排列数，只需将每一个全错位排列中的“握力”项目替换为“台阶”，方法数为4(4)=9；(2)若测“台阶”的同学刚好测“握力”项目，则方法数为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种不同的排法，其次，将其余-攵个元素排在-攵是个位置上，使每个元素的编号与它所在位置的号码不一致(全动)，有工("-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；项.所以4C"cc4=窘(一同！i<J<.<n显然，4c%c.c4=l,且n个元素的全排列为!.由容斥原理有：S)=!一4+4c4一ial<w+(-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个(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"=10×3!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+5×4!1+10×3!1+(1!2!3!4!51J(1!2!3!4!J1!2!3!J=44+45+20=109M=(2)+仍(3)+%(4)+/=G京3)+C&+C/(1)+1=20+10÷0+l=31或M=5!-的(0)+惚(1)=120-(44+45)=31.例2.同室4人各写1张贺年卡，先集中起来，然后每人从中拿1张别人送出的贺年卡,问：4张贺年卡有多少种不同的分配方法.解：本题即求四个元素的无不动点排列个数.l(4)=4!1+)=9.八，(1!2!3!4!j该题与一道波兰数学竞赛(I9601961年)题类似，其原题为：“某人给6个不同的收信人写了6封信，并且准备了6个写有收信人地址的信封.问：有多少种装入信笺的方法，使每一信笺与信封上的收信人都不相符？”由题意即得窗6)=6!(IW+/±+£)=265(种).以上两题实际上均为著名的BernoUni-EUler装错信笺问题的特殊情况.例3.P为集合S.=1,2,3,的一个排列，令，为SfJ的无不动点的排列个数，g“为恰好有一个动点的排列个数，证明：zf-g.=L证明：因为<=<()=疝£(-1)*：Sn=(Pn(1)=Cfe(/1-1)=W(ZZ-gA=OK,T1=!(-D*Pk0所以伉-g,J=川|(-1/£-(-1)ip1.*=0"=0,=川(-叫=卜昨L例4.设巴伏)表示n个元素中有k个不动点的所有排列的种数.求证：£>?(&)=!.4=0证明：,(3%c"i5/A=OI=O=-Jo)A二I=C,()hl=-,-1(0)<=()=L+G-)k=0rT=-i()X=O=nn-)=n定理6.编号为123,的n个元素排在编号为1,2,3,的位置上(每个位置只排一个元素).则指定某k(<k<)个元素为动点的排列个数为：/(&)=£(一1)“匕"(一加)！/M=O证明：若指定某Mi<4")个元素中的第i个元素，正好在第i个位置上，其他-1个元素放在-1个位置上，则所有的排列数为CG-1)!.而指定的某k个元素中的第i和j个元素恰好在第i和j的位置上，其他-2个元素全排列时，所有的排列数为C：(-2)!.同理，若指定的k个元素其编号都排在与其编号相同的位置上时，有&(-%)!种排法.由容斥原理得：U(AO=m-C5-l)!+C5-2)!-T(T)CS-A)!=(-rc11w-w)!W=O例5.将编号为1,2,3,，9的九个球放入编号为1,2,3,，9的九个盒内.要求每盒放一个球,且规定奇数k号的球不许放在奇数k号盒内，这样的投放方法有多少种？解：本题是求指定五个元素为动点的排列个数，利用定理6有：八=火(-1)勺(9！W=O=9!-C；8!+C；7Y6!+C；5!-C；4!=205056(种)例6.上届获得前n名的球队参加本届争夺前n名的比赛.如果不设并列名次，问：若没有一个队取得的名次恰好紧接在上届比他高一个名次的球队之后，那么比赛结果有多少种可能？解：设上届获得前n名的n个球队按名次的一个排列为(%七,6,M“)，这里不妨将球队号也按上述顺序排列，由题意可知，本届比赛出现的名次不可能有以下排列：akak+l,akak+yak+2,aia2a3,“,(A=l,2,-1).实际上就是，编号为1,2,3,的n个元素排在编号为1,2,3,的位置上(每个位置只排一个)，指定-1个元素为动点的排列个数为：Ug1)=!-以(-1)!+*(-2)!-+(-i)y=(-lC,(2-m)!m=0【强化训练01】1 .如图，一环形花坛分成AB,C,D四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为A.96B.84C.60D.48【强化训练02】2 .某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要在如图所示的6个点A、B、C、4,、BhG上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有种(用数字作答).【强化训练03】3 .如图，用四种不同颜色给图中的A,B,C,D,E,F六个点涂色，要求每个点涂一种颜色,且图中每条线段的两个端点涂不同颜色，则不同的涂色方法用A.288种B.264种C.240种D.168种【强化训练04】4.有4位同学在同一天的上、下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶''五个项目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不测“握力”项目，下午不测“台阶”项目，其余项目上、下午都各测试一人.则不同的安排方式共有种(用数字作答).【强化训练05】5.将字母a,abb,cc排成三行两列，要求每行的字母互不相同，每列的字母也互不相同，则不同的排列方法共有A.12种B.18种C.24种D.36种【强化训练06】6 .将用16编号的六张卡片，插入用16编号的六个盒子里，每只盒子插一张，求：(1)使每一卡片的号码与所在盒子号码都不同的插法总数；(2)恰好有3张卡片号码与所在盒子号码相同的插法总数.【强化训练07】7 .个学生参加一次聚会，每人带一张贺卡和一件礼物，会后每个人任取一张贺卡和一件礼物.问：发生下列情况时，有多少种可能？(1)没有任何一位学生取回他原来自己的一件物品；有人取回了他原来的物品；(3)恰好只有一人取回他原来的物品.【强化训练08】8 .从编号为1,2,3,4,5的五个元素中取出3个元素，排在编号为1,2,3的位置上(每个位置只许排一个元素).求：元素的编号与所处位置的号码不相同的排法.【强化训练09】9 .6名教师从星期一至星期六值日，若甲教师不排星期一，乙教师不排星期二，丙教师不排星期三，则不同的值日排法有多少种？参考答案：1. B【详解】解：分三类：种两种花有由种种法；种三种花有2A：种种法；种四种花有A：种种法.共有24：+4：+A：=84.故选B2. 216【详解】每种颜色的灯泡都至少用一个，即用了四种颜色的灯进行安装，分3步进行，第一步/、B.C三点选三种颜色灯泡共有种选法；第二步，在Al、81、CI中选一个装第4种颜色的灯泡，有3种情况；第三步，为剩下的两个灯选颜色，假设剩下的为81、Cl,若81与A同色，则CI只能选B点颜色；若加与C同色，则。有A.8处两种颜色可选，故为31、Cl选灯泡共有3种选法，得到剩下的两个灯有3种情况，则共有Ajx3x3=216种方法.故答案为2163. B【详解】先分步再排列先涂点E,有4种涂法，再涂点B,有两种可能：(I)B与E相同时，依次涂点F,C,D,A,涂法分别有3,2,2,2种；(2)B与E不相同时有3种涂法，再依次涂F、C、D、A点，涂F有2种涂法，涂C点时又有两种可能：(2.(1) C与E相同，有1种涂法，再涂点D,有两种可能：D与B相同，有1种涂法，最后涂A有2种涂法；D与B不相同，有2种涂法，最后涂A有1种涂法.(2.(2) C与E不相同，有1种涂法，再涂点D,有两种可能：D与B相同，有1种涂法，最后涂A有2种涂法；D与B不相同，有2种涂法，最后涂A有1种涂法.所以不同的涂色方法有4×(3×2×2×2+3×2×l×(1×2+1×2)+1×(1×2+1×1)=4×(24+42)=264.4.264【分析】法一：先安排上午的测试方法，有A/种，再安排下午的测试方式，由于上午的测试结果对下午有影响，故需要选定一位同学进行分类讨论，得出下午的测试种数，再利用分步原理计算出结果法二：假定没有限制条件，无论是上午或者下午5个项目都可以选.组合总数为：4×5×4×4=320.再考虑限制条件：上午不测“握力”项目，下午不测“台阶”项目.在总组合为320种的组合中，上午为握力的种类有32种；同样下午为台阶的组合有32种.最后还要考虑那去掉的64种中重复去掉的，如A同学的一种组合，上午握力，下午台阶（这种是被去掉了2次），4同学上午台阶，下午握力（也被去掉了2次），这样的情况还要考虑艮C.。三位，所以要回加2X4=8.进而可得答案.【详解】法一：先安排4位同学参加上午的“身高与体重”、“立定跳远”、“肺活量”、“台阶”测试,共有Aj种不同安排方式;接下来安排下午的“身高与体重”、“立定跳远”、“肺活量”、“握力”测试，假设A、8、C同学上午分别安排的是“身高与体重”、“立定跳远”、“肺活量”测试，若。同学选择“握力”测试，安排A、8、C同学分别交叉测试，有2种；若。同学选择“身高与体重”、“立定跳远”、“肺活量”测试中的1种，有种方式，安排4、B、C同学进行测试有3种；根据计数原理共有安排方式的种数为A44（2+×3）=264,故答案为264法二：假定没有这个限制条件：上午不测“握力”项目，下午不测“台阶”项目.无论是上午或者下午5个项目都可以选.上午每人有五种选法，下午每人仅有四种选法，上午的测试种数是4X5=20,下午的测试种数是4X4=16故我们可以很轻松的得出组合的总数：4×5×4×4=320.再考虑这个限制条件：上午不测“握力”项目，下午不测“台阶”项目.在总组合为320种的组合中，上午为握力的种类是总数的5，32种；同样下午为台阶的组合也是总数的金，32种.所以320-32-32=256种.但是最后还要考虑那去掉的64种中重复去掉的，好像A同学的一种组合，上午握力，下午台阶（这种是被去掉了2次），A同学上午台阶，下午握力（也被去掉了2次），这样的情况还要艮C.D三位,所以要回加2X4=8.所以最后的计算结果是4×5×4×4-32-32+8=264.答案：264.5. A【详解11思路点拨】先排第一列三个位置,再排第二列第一行上的元素,则其余元素就可以确定了.解:先排第一列,由于每列的字母互不相同,因此共有3×2×1种不同的方法;再排第二列,其中第二列第一行的字母共有2种不同的排法,第二列第二、三行的字母只有1种排法,因此共有3×2×1×2=12(种)不同的方法.6. (1)265；(2)40.【分析】(1)先求出无限制排列的总数，再利用间接法求解；(2)分两步完成，利用乘法分步原理求解.(1)解：全部无限制排列有尺=720种.如果有5个或6个卡片号码和盒子的号码对应相同，只有1种；如果有4个卡片号码和盒子的号码对应相同，首先，确定哪4个号码相同，有C：=15种，剩下的两个号码只有一种插法，所以共有15x1=15种；如果有3个卡片号码和盒子的号码对应相同，首先，确定哪3个号码相同，有=20种，剩下的三个号码有2种插法，所以共有20x2=40种；如果有2个卡片号码和盒子的号码对应相同，首先，确定哪2个号码相同，有C：=15种，剩下的4个号码有9种插法,所以共有15x9=135种；如果有1个卡片号码和盒子的号码相同，首先，确定哪1个号码相同，有C：=6种，剩下的5个号码，先选1个号码放在最前面，有4种插法，剩下的4个号码有11种插法，所以共有6x4x11=264种.所以共有720-1-15-40-135-264=265种.(2)解：先选择3张卡片号码与所在盒子号码相同，有C；种方法；再把剩下的3张卡片放在剩下的盒子里，要保证号码不同，只有2种方法，所以共有C；X2=40种方法.叫-格利1, (-i)t«(-1)*J(T)*(3M("l)!k2z7-+-A=O八LA=O'JI=O人【分析】(I)没有任何位学生取回他自己原来的一件物品分两步完成，第步没有人取回自己的贺卡，第二步没人取回自己的礼物，根据乘法原理求得答案；(2)个同学每人取回一张贺卡、一件礼物，共有的取法，减去没有人取回自己物品的取法数，即得答案；(3)分三种可能分别考虑，即取对贺卡、而拿错礼物；取错贺卡而拿对礼物；还有就是贺卡、礼物全取对了,计算取法，可得答案.(1)(1)设没有任何一位学生取回他原来自己的一件物品，可以先取贺卡，个同学均没有取回他原来的贺卡(即个元素排列有个动点)有力5)种.同理,再去取礼物,也有力5)种，由错排公式，共有力()了=加工察种.(2)(2) 个同学每人取回一张贺卡、一件礼物，共有ST种，故有人取回他原来物品的取法有(“Y-'(叫唐察)卜.(3)(3)根据例化)表示个元素有2个组合不动点的排列个数，那么用以表示个人中有一个人取回他原来的物品的可能数，因此恰好只有一人取回他原来的物品，有三种可能，即取对贺卡、而拿错礼物；取错贺卡而拿对礼物；还有就是贺卡、礼物全取对了.前二种情况各有例工()种，后一种情况有心力(-1)种，取法总数为：明(I)Z»()+外几T)(T)=例(1)24()+ZIT(I)=92£()+九(-1)=CM(-1)2£()+九(-1),/ 八 W(T) "!("T)!KA=O k'J k'A=O Jt=O8. 32【分析】根据取出的3个元素的情况进行分类讨论，即可求得所有排法.【详解】若取出的3个元素中有4,5,且从1,2,3中任取1个元素，则共有片=12种若从1,2,3中取出任意2个元素，且从4,5中任取1个元素，则共有CjG=18种，若从1,2,3中取出的3个元素，则共有2种排法.综上所述，共有32种排法.故答案为：32.9. 426【分析】利用排列组合知识计算可得不符合题意的排法，采用间接法可求得结果.【详解】甲排在星期一，乙排在星期二，丙排在星期三的可能的排法的集合依次用A8,C表示，则不符合题意的排法共有C4"(ABC)种，Card(ABC)=Card（八）+Card(B)+Card(C)-Card(A,B)-CardBC)-Card(ArC)CardABC)=3父+A；=294,二符合题意的排法共有屋-294=720-294=426种.