四川分校

地址:成都市武侯区领事馆路7号保利中心南塔19楼电话:028-86755760 18010526561

地址:郫县红光镇徐独路626附236号(1958广场2楼)电话:02864144727 18080402102

地址:自贡市汇东新区丹桂大街九鼎汇东大厦12楼电话:0813-8207581 13378329177

地址:泸州市江阳区滨江路一段佳乐大厦10楼(沱江一桥肯德基楼上)电话:0830-2288946 13982442674

地址:内江市市中区玉溪路新尚数码广场3楼(俊麟大厦麦当劳楼上)电话:0832-2499118、18081757159、18010531261

地址:宜宾市翠屏区上走马街28号4楼(南门桥头戎康大药房4楼)电话:0831-8256411 18016192014

地址:四川省资阳市雁江区建设北路达高国际商业广场报喜鸟楼上三楼电话:18190320569

地址:西昌市塑像星光商业广场9楼华图教育(达达百货旁) 电话:18981579923;15984971166;0834-2504678

地址:马尔康县马江街06号政法大楼2楼电话:18728209955 18180373595 0837-2828595

地址:甘孜州康定县沿河东路7-9号水井广场14层B号电话:18942835107 0836-2825589

地址:攀枝花市少年宫(竹园巷1号)培训部电话:18981579923;18080771611

地址:绵阳市涪城区临园路东段54号临园商务大厦27层7-9号 (王者通讯楼上)电话:0816-2234867 18009053423

地址:顺庆区模范步行街(果州酒店背后)电话:0817-2255750 15808172035 18010531259

地址:达州市通川区凉水井街88号(通川桥下100米)瑞丰国际大厦六楼电话:18011236701 0818-2123110 15348261723

地址:乐山市中区嘉定中路570号嘉州国际商业中心11楼1101电话:0833-2307075 18228365038

地址:遂宁中路广来福宾馆(北极星店)大厅电话:18910735973 15680000389

地址:广安市紫金街216号步云书屋(市人社局对面)电话:18010526701

地址:广元市利州区文化路357号三层电话:0839-3282378 13340730583

地址:巴中市巴州区西外街97号巴秦宾馆电话:0827-2223302 18095004228

地址:雅安市雨城区城后路14号(川农大老校区后门濆江桥头)电话:18202809379 0835-2868791

地址:眉山市东坡区裴城路69号财富中心B栋503 电话:028-38230903 18090087057

地址:德阳市旌阳区屏山街锦虹佳苑后门一楼华图教育(警校旁,申通快递隔壁)电话:0838-2503077(24小时)、18016148607

面授课程网校课程图书教材|直播问答砖题库师资|招考报考职位库快讯真题|微信微博微社区

红领培优

您当前位置:公务员考试网 > 南充人事考试网 > 考试快讯 > 排列组合—错位重排问题

排列组合—错位重排问题

2016-09-02 14:34 四川人事考试 http://sc.huatu.com/ 文章来源:未知

排列组合—错位重排问题
                                               华图教育四川分校  何彦锋

排列组合问题一直是广大考生备考行测数量关系部分的一个难点,而其中的错位排列问题是更是一个非常古老非常棘手的问题,贝努利、欧拉等数学家都曾经研究过。错位排列问题虽然有难度,但是也有快速解决之道。需要总结规律,熟记结论,才能在临考时,快速准确抓住解题突破口。为帮助广大考生攻克这一难关,下面笔者为大家详细解读错位排列问题。
一、问题导入
根据需要进行错位排列的元素是否用完,可将错位排列问题分为:全错位排列问题部分错位排列问题。下面先给出两道生活中的错位排列题目,让广大考生有一个直观感觉:
【例1】有4名同学各写了一张贺卡,先全部收集起来,然后每人从中拿出一张贺卡,要求每个人都不拿自己的贺卡,则四张贺卡的不同分配方式共有      种。
【例2】将编号为1,2,3,4的四个小球分别放入编号为1,2,3,4的四个盒子中,要求每个盒子放一个小球,且小球的编号与盒子的编号不能相同(即1不放1,2不放2,3不放3,4不放4,也就是说4个全部放错),则共有      种不同的放法。
上面这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题,我们把这种限制条件的排列问题叫做全错位排列问题。
再看下面的这题目:
【例3】五位同学坐在一排,现让五位同学重新坐,至多有两位同学坐自己原来的位置,则不同的坐法有       种。
这道题可以分类解决:第一类,所有同学都不坐自己原来的位置;第二类,恰有一位同学坐自己原来的位置;第三类,恰有两位同学坐自己原来的位置。
对于第一类,就是上面讲的全错位排列问题;对于第二、第三类有部分元素还占有原来的位置,其余元素可以归结为全错位排列问题,我们称这种排列问题为部分错位排列问题。
设n个元素全错位排列的排列数为Dn,则对于题三,第一类排列数为D5,第二类先确定一个排在原来位置的同学有5种可能,其余四个同学全错位排列,所以第二类的排列数为5D4,第三类先确定两个排在原位的同学,有=10种,所以第三类的排列数为10D3,因此题三的答案为:D5+5D4+10D3
可见,生活中类似于这样的问题非常多,而且“部分错位排列问题”也需要转化为“全错位排列问题”来求解,所以我们有必要研究一下关于“全错位排列问题”的解决方法。
二、递推关系式
1. 递推关系式
一般地,设n个编号为1、2、3、… 、i、…、j、…、n的不同元素a1、a2、a3、…、ai、…、aj、…、an,排在一排,且每个元素均不排在与其编号相同的位置,这样的全错位排列数为Dn,则D1=0,D2=1,D3=2,Dn=(n-1)(Dn-1+Dn-2)(n≥3)。
2. 递推关系式的证明
显然对于n=1、2时,有D1=0,D2=1。
当n≥3时,在n个不同元素中任取一个元素ai不排在与其编号相对应的i位,必排在剩下n-1个位置之一,所以ai有n-1种排法。
对ai每一种排法,如ai排在j位,对应j位的元素aj的排位共有两种情况:
第一种情况:aj恰好排在i位上,此时,ai排在j位,aj排在i位,元素ai,aj排位已定,还剩n-2个元素,它们的排位问题就转化为n-2个元素全错位排列数,应有Dn-2种;
第二种情况:aj不排在i位上,此时,ai仍排在j位,aj不排在i位,即此时aj有一个不能排的位置,也就是说,除了ai外,还有n-1个元素,每个元素均有一个不能排的位置,问题就可转化为n-1个元素得全错位排列,排列数为Dn-1,由乘法原理和加法原理可得:Dn=(n-1)(Dn-1+Dn-2)(n≥3)。
由此递推关系,可得:D4=9,D5=44,D6=265……
知识补充
1. 全错位排列数的一个通项公式:
Dn=(n≥2)
==(n≥2)
2. 全错位排列数的另一个递推关系式:
由D1=0,D2=1,D3=2,D4=9,D5=44,D6=265可得:
D2=2D1+1;
D3=3D2-1;
D4=4D3+1;
D5=5D4-1;
D6=6D5+1;
……
Dn=nDn-1+
题分析
【例1】(2014-北京)相邻的4个车位中停放了4辆不同的车,现将所有车开出后再重新停入这4个车位,要求所有车都不得停在原来的车位中,则一共有多少中不同的停放方式?(    )
A. 9B. 12
C. 14D. 16
【答案】A
【解析】全错位排列问题。D1=0,D2=1,D3=2,D4=9,……,Dn=nDn-1+,所以,4辆车一共有D4=9种停放方式。因此,本题答案选择A选项。
【例2】(2011-浙江)四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜,但不能尝自己做的那道菜。问共有几种不同的尝法?(    )
A. 6种B. 9种
C. 12种D. 15种
【答案】B
【解析】全错位排列问题。记住数字:D1=0,D2=1,D3=2,D4=9,……,Dn=nDn-1+。可知,4个元素对应的全错位排列数为D4=9。因此,本题答案选择B选项。
【例3】(2015-四川-泸州)a、b、c、d四台电脑摆放一排,从左往右数,如果a不摆在第一个位置上,b不摆在第二个位置上,c不摆在第三个位置上,d不摆在第四个位置上,那么不同的摆法共有(    )种。
A. 9B. 10
C. 11D. 12
【答案】A
【解析】全错位排列问题。记住数字:D1=0,D2=1,D3=2,D4=9,……,Dn=nDn-1+。可知,4个元素对应的全错位排列数为D4=9。因此,本题答案选择A选项。
【例4】五位同学坐在一排,现让五位同学重新坐,至多有两位同学坐自己原来的位置,则不同的坐法有       种。
【答案】109.
【解析】部分错位排列问题。本题可分三类求解:第一类,所有同学都不坐自己原来的位置,即5个元素的全错位排列,排列数为D5=44;第二类,恰有一位同学坐自己原来的位置,其余4个同学进行全错位排列,排列数为5D4=5×9=45;第三类,恰有两位同学坐自己原来的位置,其余3个同学进行全错位排列,排列数为×D3=10×D3=10×2=20。所以本题答案为:D5+5D4+10D3=44+45+20=109种。
综上,对于全错位或部分错位排列问题,当元素不是很多时,我们可以通过分类讨论的方案,对问题进行讨论求解,但当元素较多时讨论起来非常麻烦,所以熟悉全错位排列数的通项公式和递推关系式,对我们解决这一类问题能带来很大的方便。同时,建议广大考生记住下面这几个数字:0,1,2,9,44,265,这也是一个有规律的数字推理题,递推关系式为:①Dn=(n-1)(Dn-1+Dn-2)(n≥3);②Dn=nDn-1+(n≥2)。
 
 


(编辑:华图教育)

上一篇:2016年四川政法干警考试时间

下一篇:没有了

掌上华图客户端下载



红领培优,一次考上

今日直播

1356289人正在这里听课换一批

四川公务员考试免费辅导

公务员直播  时间:每周一

每周一公务员免费直播课
四川事业单位考试免费辅导课

事业单位  时间:每周二

每周二公务员免费直播课
四川教师公招免费辅导课

教师公招  时间:每周三

每周三教师公招免费直播课
四川银行金融农信社考试免费辅导课

银行金融  时间:每周四

每周四银行金融免费直播课
公务员事业单位教师备考活动
京ICP备11028696号-11 京ICP证130150号 京公网安备11010802021470号
-->
客服咨询 极速版 联系我们 返回顶部

Copyright© 2014 华图教育版权所有