高中数学不动点与组合问题

试卷第=page11页，共=sectionpages33页试卷第=page11页，共=sectionpages33页不动点与组合问题第一节不对号入座与全错位排列一、问题把n个编号为的球放入n个编号为的盒子中，要求每个盒子中只放一个球，且球的号码与盒子的编号数均不相同，试求有多少种不同的放法种数？这个问题就相当于n个自然数的全错位排列问题.不妨设这种不同的放法种数有种，它可以分两步完成：第一步放编号为1的球，共有种放法，此时不妨把编号为1的球放在编号为的盒子里，再安排第i号球的位置，有两种情况：①第i号球放在第1个盒子中，剩余的个球要放在个盒子中，依然要求是号码均不相同，故种放法；②第i号球不放在第1个盒子中，此时如同个球要放在个盒子中，且号码均不相同，故有方法数为种.所以，一般地，我们得到递推公式，①其中.利用这个公式，我们可以解决这类错位排列问题.二、探求通项公式由递推公式①及，可得：，上式两边同乘以得：②于是可得：，，，，将上述个式子累加，得：所以，故.评注由递推公式①得到递推公式②是求解的关键，这也是处理复杂递推数列问题的难点所在.例1同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡不同的分配方式有（）A.6种.B.9种.C.11种.D.23种.分析此题是全错位排列问题，我们可以应用公式来进行解题.解析由递推公式①及，可得.故选B.例2五个瓶子都贴了标签，其中恰好贴错了三个，贴错的可能情况共有（）种.A.6B.10C.12D.20分析此题也是错位重排但不是全部错位，我们可以部分应用错位重排来进行解题.解析分步进行：第一步，选出三个瓶子，这三个瓶子恰好贴错了，有种；第二步，这三个瓶子满足错位重排，所以对应的公式数据应该是2.最后根据乘法原理，共有种.故选D.例3某人给6个不同的人写了6封信，每人一份，并准备了6个写有收信人地址的信封，问有多少种投放信笺的方法，使得每份信笺和信封上的收信人都不相同？分析：此题是全错位排列问题，我们可以应用公式来进行解题.解析由递推公式①及，可得：，，.故共有265种投放信笺的方法，使得每份信笺和信封上的收信人都不相同.三、问题的推论与探究引理用表示n个不同元素全错位排列的方法数，则n个不同元素全错位排列的方法数满足.（1）下面用第二数学归纳法给出引理的一般性证明.证明（1）易知当时，，满足，式（1）成立；当时，，满足，式（1）成立.（2）假设时，式（1）成立，即k个元素全错位排列的方法数的递推关系为，则当时，设全错位排列的元素为.在k个元素全错位排列的基础上，个元素全错位排列后，它们全错位排列的方法分为2类：①与互调位置，其余元素全错位排列，方法数为；②在的位置上，但不在的位置上，其余元素仍然错位排列.这样的排列，相当于将k个元素的每一个全错位排列中的元素置换了一遍.k个元素的每一个全错位排列是k个元素，因此该类全错位排列的方法数为.综上所述，，又，故.即当时，式（1）成立.因此，n个元素全错位排列的方法数的递推关系为.定理用表示n个不同元素所有的全错位排列的方法数，则当时，；当时，.n个不同元素排成一列，记下每个元素的编号，重新排列后，有以下结论：推论1某i个元素（特定）现在的编号与原编号一致，个元素现在的编号与原编号错位的排列方法数为.推论2i个元素（不特定）现在的编号与原编号一致，个元素现在的编号与原编号错位的排列方法数为.推论3某i个元素（特定）在原有的位置上互相全错位，另个元素在原有的位置上互相全错位，这样的排列数为.推论4i个元素（不特定）在原有的位置上互相全错位，另个元素在原有的位置上互相全错位，这样的排列数为.例1同寝室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺卡，则4张贺卡不同的分配方式有_________种.解该题属于4个元素的全错位问题.由定理得，故分配方式有9种.例2设编号为1，2，3，4，5的5个球及编号为1，2，3，4，5的5个盒子，一个盒子内放一球，恰有2个球的编号与盒子编号相同，则投放种数有多少？解“恰有2个球的编号与盒子编号相同”等价于“恰有3个球的编号与盒子编号不同”.由推论2得，投放种数为.例3编号为1，2，3，4，5的5个人，分别坐在编号为1，2，3，4，5的座位上，则至多2个号码一致的坐法有多少种？解法1（直接法）至多2个号码一致，分3种情况：（1）“恰2个一致”等价于“恰3个错位”，；（2）“恰1个一致”等价于“恰4个错位”，；（3）没有一致”等价于“5个全错位”，.从而.解法2（间接法）无任何限制条件时，.“恰有3个号码一致”等价于“恰有2个错位”，；“恰有4个号码一致”与“恰有5个号码一致”的坐法属同一种情况，故.从而.例4有4位同学在同一天的上、下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”5个项目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不测“握力”项日，下午不测“台阶”项目，其余项目上、下午都各测试一人，则不同的安排方式共有多少种？解4位同学上午测试“身高与体重”、“立定跳远”、“肺活量”、“台阶”4个项目的方法数为种.下午测试的方法分为2类：（1）4位同学测试的项目仍然是上午的4个项目，方法数是4个元素的全错位排列数，只需将每一个全错位排列中的“握力”项目替换为“台阶”，方法数为；（2）若测“台阶”的同学刚好测“握力”项目，则方法数为.故下午测试的方法数共有种.从而上、下午不同的安排方式共有种.第二节组合不动点组合不动点问题的反面提法是“扰排问题”定义：设集合是集合的一个排列，若，则称k为变换F的一个组合不动点，我们用表示n个元素有k个组合不动点的排列个数，表示有k个动点的排列个数.显然有，.定理1..证明：所有的排列数问题可分二步思考.首先，从n个元素中选出k个元素排在k个位置上，使每个元素的编号与它所在位置的号码一致（不动），共有种不同的排法，其次，将其余个元素排在是个位置上，使每个元素的编号与它所在位置的号码不一致（全动），有种排法，由乘法原理，故原命题得证.定理2..证明：.定理3..证明：考虑第k号元素正好放在第k号位置上，显然，其余个元素放在个位置上的所有排列数为，且和式共有项，所以而的排列数为，和式共有项.所以同理，的排列数为，和式共有项.所以显然，，且n个元素的全排列为.由容斥原理有：定理4.证明：因为n个元素的全排列个数为.另一方面考虑可分成恰好零个组合不动点，恰好一个组合不动点，恰好两个组合不动点，…，恰好n个组合不动点，由加法原理有：，类似地可得到定理5.从编号为的n个元素，取出k个（）元素排在编号为的位置上（每一个位置只允许排一个元素），有k个动点的排列个数为：.当时，即定理3.故定理5可视为定理3的推广.例1.设有编号1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子.现将这五个球投入这五个盒子内，要求每个盒子投放一个球，求以下几种情况的投放方法数.①恰好有两个球的编号与盒子编号相同；②恰好没有两个球的编号与盒子编号相同；③至多有两个球的编号与盒子编号相同；④至少有两个球的编号与盒子编号相同.解：①②③④或.例2.同室4人各写1张贺年卡，先集中起来，然后每人从中拿1张别人送出的贺年卡，问：4张贺年卡有多少种不同的分配方法.解：本题即求四个元素的无不动点排列个数..该题与一道波兰数学竞赛（1960～1961年）题类似，其原题为：“某人给6个不同的收信人写了6封信，并且准备了6个写有收信人地址的信封.问：有多少种装入信笺的方法，使每一信笺与信封上的收信人都不相符？”由题意即得（种）.以上两题实际上均为著名的Bernoulli-Euler装错信笺问题的特殊情况.例3.P为集合的一个排列，令为的无不动点的排列个数，为恰好有一个动点的排列个数，证明：.证明：因为所以.例4.设表示n个元素中有k个不动点的所有排列的种数.求证：.证明：定理6.编号为的n个元素排在编号为的位置上（每个位置只排一个元素）.则指定某个元素为动点的排列个数为：证明：若指定某个元素中的第i个元素，正好在第i个位置上，其他个元素放在个位置上，则所有的排列数为.而指定的某k个元素中的第i和j个元素恰好在第i和j的位置上，其他个元素全排列时，所有的排列数为.同理，若指定的k个元素其编号都排在与其编号相同的位置上时，有种排法.由容斥原理得：例5.将编号为1，2，3，…，9的九个球放入编号为1，2，3，…，9的九个盒内.要求每盒放一个球，且规定奇数k号的球不许放在奇数k号盒内，这样的投放方法有多少种？解：本题是求指定五个元素为动点的排列个数，利用定理6有：（种）例6.上届获得前n名的球队参加本届争夺前n名的比赛.如果不设并列名次，问：若没有一个队取得的名次恰好紧接在上届比他高一个名次的球队之后，那么比赛结果有多少种可能？解：设上届获得前n名的n个球队按名次的一个排列为，这里不妨将球队号也按上述顺序排列，由题意可知，本届比赛出现的名次不可能有以下排列：.实际上就是，编号为的n个元素排在编号为的位置上（每个位置只排一个），指定个元素为动点的排列个数为：【强化训练01】1．如图，一环形花坛分成四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为A．96 B．84 C．60 D．48【强化训练02】2．某人有4种颜色的灯泡（每种颜色的灯泡足够多），要在如图所示的6个点A、B、C、A1、、B1、C1上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有种（用数字作答）.【强化训练03】3．如图，用四种不同颜色给图中的A,B,C,D,E,F六个点涂色，要求每个点涂一种颜色，且图中每条线段的两个端点涂不同颜色，则不同的涂色方法用A．288种 B．264种 C．240种 D．168种【强化训练04】4．有4位同学在同一天的上、下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”五个项目的测试，每位同学上、下午各测试一个项目，且不重复.若上午不测“握力”项目，下午不测“台阶”项目，其余项目上、下午都各测试一人.则不同的安排方式共有______________种（用数字作答）.【强化训练05】5．将字母a,a,b,b,c,c,排成三行两列，要求每行的字母互不相同，每列的字母也互不相同，则不同的排列方法共有A．12种 B．18种 C．24种 D．36种【强化训练06】6．将用1～6编号的六张卡片，插入用1～6编号的六个盒子里，每只盒子插一张，求：(1)使每一卡片的号码与所在盒子号码都不同的插法总数；(2)恰好有3张卡片号码与所在盒子号码相同的插法总数.【强化训练07】7．n个学生参加一次聚会，每人带一张贺卡和一件礼物，会后每个人任取一张贺卡和一件礼物.问：发生下列情况时，有多少种可能？(1)没有任何一位学生取回他原来自己的一件物品；(2)有人取回了他原来的物品；(3)恰好只有一人取回他原来的物品.【强化训练08】8．从编号为1，2，3，4，5的五个元素中取出3个元素，排在编号为1，2，3的位置上（每个位置只许排一个元素）.求：元素的编号与所处位置的号码不相同的排法.【强化训练09】9．名教师从星期一至星期六值日，若甲教师不排星期一，乙教师不排星期二，丙教师不排星期三，则不同的值日排法有多少种？答案第=page11页，共=sectionpages22页答案第=page11页，共=sectionpages22页参考答案：1．B【详解】解：分三类：种两种花有种种法；种三种花有2种种法；种四种花有种种法．共有2++=84．故选B2．216【详解】每种颜色的灯泡都至少用一个，即用了四种颜色的灯进行安装，分

3

步进行，第一步

,A

、B.

C

三点选三种颜色灯泡共有

种选法；第二步

,

在

A1

、

B1

、

C1

中选一个装第

4

种颜色的灯泡，有

3

种情况；第三步

,

为剩下的两个灯选颜色

,

假设剩下的为

B1

、

C1,

若

B1

与

A

同色

,

则

C1

只能选

B

点颜色；若

B1

与

C

同色

,

则

C1

有A.

B

处两种颜色可选,故为

B1

、

C1

选灯泡共有

3

种选法，得到剩下的两个灯有

3

种情况，则共有

×3×3=216

种方法．故答案为

2163．B【详解】先分步再排列先涂点E，有4种涂法，再涂点B，有两种可能：(1)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×[1×(1×2+1×2)+1×(1×2+1×1)]}=4×(24+42)=264．4．264【分析】法一：先安排上午的测试方法，有A44种，再安排下午的测试方式，由于上午的测试结果对下午有影响，故需要选定一位同学进行分类讨论，得出下午的测试种数，再利用分步原理计算出结果法二：假定没有限制条件，无论是上午或者下午5个项目都可以选．组合总数为：4×5×4×4＝320．再考虑限制条件：上午不测“握力”项目，下午不测“台阶”项目．在总组合为320种的组合中，上午为握力的种类有32种；同样下午为台阶的组合有32种．最后还要考虑那去掉的64种中重复去掉的，如A同学的一种组合，上午握力，下午台阶（这种是被去掉了2次），A同学上午台阶，下午握力（也被去掉了2次），这样的情况还要考虑B．C．D三位，所以要回加2×4＝8．进而可得答案．【详解】法一：先安排4位同学参加上午的“身高与体重”、“立定跳远”、“肺活量”、“台阶”测试，共有A44种不同安排方式；接下来安排下午的“身高与体重”、“立定跳远”、“肺活量”、“握力”测试，假设A、B、C同学上午分别安排的是“身高与体重”、“立定跳远”、“肺活量”测试，若D同学选择“握力”测试，安排A、B、C同学分别交叉测试，有2种；若D同学选择“身高与体重”、“立定跳远”、“肺活量”测试中的1种，有A31种方式，安排A、B、C同学进行测试有3种；根据计数原理共有安排方式的种数为A44（2+A31×3）＝264，故答案为264法二：假定没有这个限制条件：上午不测“握力”项目，下午不测“台阶”项目．无论是上午或者下午5个项目都可以选．上午每人有五种选法，下午每人仅有四种选法，上午的测试种数是4×5＝20，下午的测试种数是4×4＝16故我们可以很轻松的得出组合的总数：4×5×4×4＝320．再考虑这个限制条件：上午不测“握力”项目，下午不测“台阶”项目．在总组合为320种的组合中，上午为握力的种类是总数的，32种；同样下午为台阶的组合也是总数的，32种．所以320﹣32﹣32＝256种．但是最后还要考虑那去掉的64种中重复去掉的，好像A同学的一种组合，上午握力，下午台阶（这种是被去掉了2次），A同学上午台阶，下午握力（也被去掉了2次），这样的情况还要B．C．D三位，所以要回加2×4＝8．所以最后的计算结果是4×5×4×4﹣32﹣32+8＝264．答案：264．5．A【详解】【思路点拨】先排第一列三个位置,再排第二列第一行上的元素,则其余元素就可以确定了.解:先排第一列,由于每列的字母互不相同,因此共有3×2×1种不同的方法;再排第二列,其中第二列第一行的字母共有2种不同的排法,第二列第二、三行的字母只有1种排法,因此共有3×2×1×2=12(种)不同的方法.6．(1)265；(2)40.【分析】（1）先求出无限制排列的总数，再利用间接法求解；（2）分两步完成，利用乘法分步原理求解.(1)解：全部无限制排列有种.如果有5个或6个卡片号码和盒子的号码对应相同，只有1种；如果有4个卡片号码和盒子的号码对应相同，首先，确定哪4个号码相同，有种，剩下的两个号码只有一种插法，所以共有种；如果有3个卡片号码和盒子的号码对应相同，首先，确定哪3个号码相同，有种，剩下的三个号码有2种插法，所以共有种；如果有2个卡片号码和盒子的号码对应相同，首先，确定哪2个号码相同，有种，剩下的4个号码有9种插法，所以共有种；如果有1个卡片号码和盒子的号码相同，首先，确定哪1个号码相同，有种，剩下的5个号码，先选1个号码放在最前面，有4种插法，剩下的4个号