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

不动点与组合问题第一节不对号入座与全错位排列一、问题把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个写有收信人地址的信封.问：有多少种装入信笺的方法，使每一信笺与信封上的收信人都不相符？”由题意即得（种）.以上两题实际上均为著名的BernoulliEuler装错信笺问题的特殊情况.例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个学生参加一次聚会，每人带一张贺卡和一件礼物，会后每个