四.错位排列问题
n个不同元素排成一排，有m个元素（m?n）不排在相应位置的排列种数共有：
n1n?12n?23n?3mn?mAn?CmAn?1?CmAn?2?CmAn?3?????(?1)mCmAn?m. 0当n?m时，规定A0?0!?1，这个公式亦成立.
例7 五封标号为1～5的信放进5个编号为1～5的信笺里面，若信的编号与信笺的编号都不相同，一共有多少种不同放法.
解：这是著名的信封问题，很多著名数学家都研究过.瑞士数学家欧拉按一般情况给出了一个递推公式：
用A、B、C??表示写着n位友人名字的信封，a、b、c??表示n份相应的写好的信.把错装的总数记为f(n).假设把a错装进B里了，包含着这个错误的一切错装法分两类：
（1）b错装进A里，这时每种错装的其余部分都与a、b、A、B无关，应有f(n?2)种错装法.
（2）b错装进A、B之外的信封，这时的装信工作实际是把（除a之外的）信纸b、
c??装入（除B之外的）n?1个信封A、C??，显然这种错装方法有f(n?1)种.
错装的其余部分都与a、b、A、B无关，应有f(n?2)种错装法. 总之在a错装入B的错误之下，共有错装法f(n?1)?f(n?2)种. 装入D??的n?2种错误之下，同样都有f(n?1)?f(n?2)种错装法. 因此f(n)?(n?1)[f(n?1)?f(n?2)]，显然f(1)?0，f(2)?1. 由此可得f(5)?44.
注意：用容斥原理亦可解决此题. 普遍结论为错排公式1：f(n)?n![1?1111???????(?1)n]. 1!2!3!n!错排递推公式2： f(n)?(n?1)[f(n?1)?f(n?2)]
错排公式3：An?CmAn?1?CmAn?2?CmAn?3?????(?1)CmAn?m
例8 有5个人站成一排，其中A不站第一位，B不站第二位，C不站第三位，D不站
n1n?12n?23n?3mmn?m第四位，E不站第五位，共有多少种不同的站法.
解析：上面两例实际上可以看成n个不同元素中有m（m?n）错位排列的问题. 而这个问题是其特殊情况，即全错位排列问题.
514233241500共有A5?C5A4?C5A3?C5A2?C5A1?C5A0?44种（注意A0?0!?1）
例9 同室四人各写一张贺年卡，先集中起来.然后每人从中拿一张别人送出的贺年卡.则四张贺年卡不同的分配方式有
A.6种 B.9种 C.11种 D.23种 解析：由上面公式得：
413223140A4?C4A3?C4A2?C4A1?C4A0?9种，∴选择B答案.
因此可得到全错位排列的公式：
n个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，??，第n个元素不在第n位的排列数为：
n1n?12n?23n?3n0An?CnAn?1?CnAn?2?CnAn?3?????(?1)nCnA0
nn?12n?23n?3mn?m这实际上是公式An?C1(?1)mCmAn?m的特殊情况.这mAn?1?CmAn?2?CmAn?3?????个公式很有用，只要有特殊元素不站特殊位置的问题，都可以用这个公式很快得到解决，希望这个公式对大家有所帮助.
五. 圆桌排列
从n个不同元素中不重复的取出m（1?m?n）个元素排在一个圆周上，叫做这n个不同元素的圆排列.如果一个m-圆排列旋转可以得到另一个m-圆排列，则认为这两个圆排列是相同的.
特别的，当m?n时，n个不同元素作成的圆排列总数为(n?1)!.
证明：在圆周上任选一个位置排a1有n种排法，再选一个位置排a2有n?1种排法，?，最后一个位置排an有1种排法.而这n个人顺时针（或逆时针）挪动n次位置都是同一种排列.所以共有
n!?(n?1)!种排法. n例10 有5对夫妇参加一场婚宴，他们被安排在一张10个座位的圆桌就餐，但是婚礼操办者并不知道他们彼此之间的关系，只是随机安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少？( )
A. 在1‰到5‰之间 B. 在5‰到1%之间 C. 超过1% D. 不超过1‰
解：5对夫妇相邻而座，可以看做是五个大元素为桌而坐，所以有4!种坐法，而夫妇间又可以换位置，所以共有
4!?2?2?2?2?22??0.002. 故选：A.
9!945例11 博杰学习网竞赛小组“先进人物评比”最终圈定了n个人，需要确定最终的三个“先进人物”人选.方法是：这n个人排成一行，从第一名开始，1至3循环报数，凡报出3的就退出，余下的向前靠拢，按此规律重复进行.直到第p次报数后，只剩下3个人为止.试问：这剩下的三个人，分别在队伍最初的什么位置？
解：设n个人的编号依次为1,2，?，n.最后剩下的三个人中，第三人的编号为bn.
nn个人，还剩n?个人.bn向前移33b3b?rnn动了bn?bk（k?n?）个人，前面淘汰了n?bn?rn（rn?1,2）个人.故bn?k.
3321其中当bk为奇数时，rn?1；否则，rn?2，每报一次号，人数减少（除不尽时取整）.
3因bn未被淘汰，故不是3的倍数.第一次报数后淘汰了
计算bn逐步归纳为减小的数列，最终划归到小情况.例如n?1000时，第三个人的初始位置是712.
例12 将圆分成n（n?2）个扇形，现用m（m?2）种颜色给这些扇形染色，每个扇形恰染一种颜色且要求相邻的扇形不同色.问有多少种不同的染色方法？
解：设染色方法数为an.
（1）求初始值.当n?2时，给S1染色有m种方法，给S2染色有m?1种方法. 所以a2?m(m?1)；
（2）求递推关系. 给S1染色有m种方法，给S2染色有m?1种方法，给S3染色有m?1种方法，??，给Sn染色有m?1种方法.共有m(m?1)这种情况可以分为两类
一类是Sn与S1不同色，此时的染色方法种数是an；另一类是Sn与S1同色，Sn与S1可以合并为一个扇形，Sn?1与S1不同色，染色方法种数为an?1.由加法原理，得到
n?1种方法.
an?an?1?m(m?1)n?1（n?2）.
（3）求an.构造等比数列.结论：共有an?(m?1)?(?1)(m?1)种染色方法.
nn六.转化命题
对于一些较难的排列组合问题，通常采用转化命题的方法来解决.比如圆内弦的交点个数可转化为圆内接四边形的个数；异面直线的对数可转化为3倍的四面体的个数等.
例13 圆周上共有15个不同的点，过其中任意两点连一弦，这些弦在圆内的交点最多有多少个？
分析：若两弦有交点，则两弦应是圆内接四边形的对角线，即一个四边形对应一个交点.
4所以共有C15?1365个交点.
小结：
1.“在”与“不在”可以相互转化.解决某些元素在某些位置上用“定位法”，解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解.
2.排列组合应用题极易出现“重”、“漏”现象，而“重”、“漏”错误常发生在该不该分类、有无顺序的问题上.为了更好地防“重”堵“漏”，在做题时需认真分析自己做题思路，也可改变解题角度，利用一题多解核对答案.
【作业】
1.今有8个人坐圆桌，有多少种坐法？
2.有5个男孩，3个女孩围成一圆，其中3个女孩不相邻，有多少种站法？
3.一圆型餐桌依次有A、B、C、D、E、F六个座位，现让3个大人和3个孩子入座进餐，要求任何两个小孩都不能坐在一起，则不同的作法总数为 72 .
第三课时排列组合问题的解题方法（三）
教学目标：
掌握几类特殊的排列问题的解决技巧.
教学重点：掌握“容斥原理”、“错位排列”、“圆桌排列”等问题的解题技巧. 教学难点：如何应用“技巧”解题． 教学过程： 【例析技巧】
七. 用容斥原理解排列问题
有些排列组合问题可转化为求集合的元素的个数来求.充分应用容斥原理：
n(A?B)?n(A)?n(B)?n(A?B)
n(A?B?C)?n(A)?n(B)?n(C)?n(A?B)?n(B?C)?n(A?B)?n(A?B?C).
例14 五人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法. 解：这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑
5445个有的全排列，有A5种不同的排法，然后除去甲排第一（有A4种）与乙排第二（也有A4种），但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：
543A5?2A4?A3?78种.
例15 有5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法.
5432仿上分析可得：A5?3A4?3A3?A2?64种.
八.均匀分组问题．
mmmC?C???Cmnmn?mm一般地：将mn个不同元素均匀分成n组（每组m个元素），共有种nAn方法．
例16 有6本不同的书，按下列要求各有多少种不同的选法： （1）分给甲、乙、丙三人，每人2本； （2）分为三份，每份2本；
（3）分为三份，一份1本，一份2本，一份3本；
（4）分给甲、乙、丙三人，一人1本，一人2本，一人3本； （5）分给甲、乙、丙三人，每人至少1本.
222解：（1）根据分步计数原理得到：C6C4C2?90种；
222（2）分给甲、乙、丙三人，每人两本有C6C4C2种方法，这个过程可以分两步完成：
第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙、丙三名同学有
A33种方法．根据分步计数原理可得：
CCC?xC26242233，所以
222C6C4C2x??15．因此，3A3分为三份，每份两本一共有15种方法．
（3）这是“不均匀分组”问题，一共有C6C5C3?60种方法．
（4）在（3）的基础上再进行全排列，所以一共有C6C5C3A3?360种方法．
1233123
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一课时 排列组合问题的解题方法（一）(2)在线全文阅读。
相关推荐：