「0eptvtc解排列组合题的若干方法」

、.～我们‖打〈败〉了敌人。　②我们‖〔把敌人〕打〈败〉了。解排列组合题的若干方法石家庄二中李博杰捆绑法捆绑法，即将若干个在排列组合时可看为一体或必须看为一体的物体看成一个整体.捆绑法，总数=“捆绑物”内部组合方案数＊各“捆绑物”之间组合方案数.8个女孩，２５个男孩围成一个圆圈，每两个女孩之间至少站有两个男孩,共有多少种不同的排列方法?（只要圆旋转一下就重合的方法认为是相同的)解令每个女孩“带着”两个男孩（女孩在前，男孩在后）参加排队．(1)一个女孩、两个男孩组成一组,共有8组,还有9个“单独”的男孩.选择并排列这１６个“跟着女孩的”男孩共有P162５=25!/9!种方式.(2)一共17个“相互独立”的物体,他们之间共有17!种排列方式.　(３)围成一个圆圈，共有17种可能，要除以17,以排除旋转重合的问题.运用乘法原理,这些人共有1６!＊25!/9!种排列方式.小结　运用“捆绑法”，要注意避免重复排列.这种思想方法类似“程序法”,即将排列组合的过程分解成一个个相互独立的步骤，分别计算其方案数，再相乘.七人排成一排,甲、乙两人必须相邻,且甲、乙都不与丙相邻,则不同的排法有(）种(Ａ)960种（B)840种(C)7２0种(Ｄ)600种答案Ａ小结本题涉及一类重要问题:问题中既有元素的限制，又有排列的问题,一般是先元素（即组合）后排列。设a1，a２,ａ3为三个整数，且满足0<　a1<ａ22,ａ３-ａ２>2．求满足上述条件的有序数组{　a1,a2,a3}的个数.解应用捆绑法.将ａ1及其后面的两个“空格”看为一个整体，a2及其后面的两个“空格”看为一个整体.如此形成1０个“新元素”，从中任意选择3个，共C3１０种方法.插空法“相邻”用“捆绑”，“不邻”就“插空”.以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”；以某些元素不能相邻为附加条件的,可采用“插空法”。“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定.8人排成一队,Ａ、B、C三人互不相邻，Ｄ、Ｅ两人也互不相邻的排法共有多少种？解　先把除了ABＣ以外的5个人排列好是P(5，5)ﻫ然后就有了６个空挡，用插入排列法：6个空挡里面插入3个人于是为P(6，3)，ﻫ所以AＢC不在一起的总数为P（5，5)*P(6，3）但是这样有重复的，因为ＤE可能在一起了,于是要扣除ＡBＣ不在一起但是ＤE在一起的,也是利用先捆绑ＤＥ和剩下三人就是4个全排列然后插入ABC三个人用插空排列法：2＊Ｐ（4,4)*P（５,３）总的答案为：P(５，5)＊P(６，３)-2＊Ｐ(4,4）*P(５，3）=1１520种。点评此题用到分类讨论,扣除法，插空排列,捆绑排列,排列数公式，组合数公式,加法原理.......小结以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”;以某些元素不能相邻为附加条件的,可采用“插空法”.“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定.从６个学校中选出30名学生参加数学竞赛,每校至少有1人,这样有几种选法?解问题相当于把个30相同球放入6个不同盒子（盒子不能空的）有几种放法?　这类问题可用“隔板法”处理.采用“隔板法”得：Ｃ５2９＝4０９５.小结把ｎ个相同元素分成m份每份,至少1个元素,问有多少种不同分法的问题可以采用“隔板法”得出共有多少种.递推法N*为全体正整数的集合,是否存在一一映射φ:Ｎ＊　N＊　满足条件:对一切kN*，都有k　|（φ(1）+φ(2)+……+φ（k）)？证明你的结论．注:　映射φ:AB称为一一映射,如果对任意bＢ,有且只有一个　ａA使得φ（ａ)＝ｂ．　题中“|”为整除符号.解存在.对n归纳定义φ(２n-1)及φ(2n)如下:　　　　　　　令φ（1)=1,φ(2)＝3.设已定义出不同的正整数值φ(k)(1≤k≤2n)满足整除条件且包含　１,2,…,n,设ｖ=miｎ　Ｎ＊\{φ（1),…,　φ(2n）｝,由于２n+1与２ｎ+2互素，根据孙子定理,存在不同于v及φ(k)（1≤k≤2n)的正整数u满足同余式组u-S2ｎ(mod2n＋1）－Ｓ２n－v(ｍod2n+2)．　　定义φ(2n+1)=u,φ(2n＋2)=ｖ　.则正整数φ(k）(1≤k≤2n＋2）也互不相同,满足整除条件,且包含1,２,…,n+１.根据数学归纳法原理,已经得到符合要求的一一映射.φ：N*Ｎ*．　　　　（错位排列）五封标号为1~5的信放进5个编号为1~５的信笺里面，全错位排列（即1不放1,2不放２,依次类推）一共有多少种放法．解这是著名的信封问题,很多著名的数学家都研究过。瑞士数学家欧拉按一般情况给出了一个递推公式：用Ａ、B、C……表示写着n位友人名字的信封，ａ、b、c……表示ｎ份相应的写好的信纸。把错装的总数为记作ｆ(n)。假设把a错装进Ｂ里了,包含着这个错误的一切错装法分两类:（1)ｂ装入A里，这时每种错装的其余部分都与Ａ、B、a、ｂ无关，应有ｆ(n－2）种错装法。(2）b装入Ａ、B之外的一个信封,这时的装信工作实际是把（除ａ之外的)份信纸b、c……装入（除B以外的)n－1个信封Ａ、C……,显然这时装错的方法有f（n-1)种。　ﻫ总之在a装入B的错误之下,共有错装法f（n－2)+f(ｎ-1)种。ａ装入C，装入D……的n-2种错误之下，同样都有ｆ(ｎ-2）+f（n-1)种错装法，因此:f（n)＝(ｎ-1）{f(n-1)+ｆ(n-2）｝　这是递推公式,令ｎ=1、2、3、4、5逐个推算就能解答此问题。ﻫf（1）=０　f(2)=1f(3)=2ｆ(4)=９f(5）＝44ﻫ答案是44种。小结　用容斥原理亦可解决此题。普遍结论为错排公式:f(n)=n!(1–1/１!+1/2！-1/３!　+…＋(-1)ｎ/n!)．在n*m的网格中,从(０,０）点到(n,m)点,只能沿网格的边向x轴正方向或ｙ轴正方向前进.问共有多少种不同的前进路线?解对任意一个非x轴、y轴上的点(ｘ,y),可以从点(x，y－1)走来,也可以从点(x－1,y)走来.因此，设(x，y)处的路线条数为f(x，ｙ）,则有递推公式:　f(ｘ,y)＝f(x，ｙ-1)+ｆ(x-1,ｙ).下面的推理很重要：根据上述递推公式，可得f(ｘ,y)=C(ｘ+ｙ,x).即从ｘ+ｙ件物品中选出无顺序的ｘ件(或y件）的总方案数.即f(x，ｙ）=(ｘ+ｙ)！／(x!y!).小结上述问题中把每个f(x,y)指标在对应的坐标点处，再将坐标系顺时针旋转13５。,你发现了什么？这是杨晖三角,f(ｘ，y)=C(x+ｙ,x)．而我们知道,C（x,y）=C(x-1,ｙ)+Ｃ(x，y-1).这就是通项公式的来源．以上问题还可以推广.有甲乙两队,各有７名队员，分别编号１－7，首先两队编号为1的队员对抗比赛，负者被淘汰，胜者与负方的2号队员比赛,以此类推．直到某队全部被淘汰为止.问最后有多少种不同比赛方式?解设f(x,ｙ)表示甲乙两队分别由x,y名队员组成时的比赛方式数.　由于上次可能是甲、乙两队中某个被淘汰，故通项公式为f(x,ｙ)=f(x－1,y）+f(x,y－１).转化到与上题相同的数学模型.即f(x,y)=（x+y）!/(ｘ！y!）.小结上述问题是一个二元递推函数,与递推函数通项公式的处理有关,有兴趣的同学可以继续深入学习有关

内容

财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容

.　求排列组合递推问题时，一定要注意以下几个方面:(1)初始条件(2)递推关系中+1，-１的问题（３)递推终止条件．递推的高级形式是动态规划,以上就是一个最简单的动态规划范例．甲乙两人参加竞选,甲得m张选票,乙得ｎ张选票，m＞n．问:在m＋n张选票逐一唱完的过程中,甲得的票数一直领先的概率是多少？解这是组合分析中重要的选择问题.采用折线法。是甲的选票,取ａk=1;是乙的选票，ak=－1.得到m+n－1届的折线,甲的票数一直领先。由折线法公式，得：Ｃ（m＋n-1,m-1)-Ｃ(m+n－1,m)＝(ｍ-n）C(m+n,m）/（m+ｎ).概率为领先数/总可能数.P=C(m＋n，m)（ｍ-n）/Ｃ(m+n-１,m-1)(m+n)．小结本题采用了一种重要的思想方法，将实际问题转化成折线树木的问题解决.这种方法适合“互相追逐”的问题，即每步或＋1,或-1，不得超过某个极限，适合折线法.如:排队买票问题等.关于概率，分类时应特别注意“等可能性”，才能保证计算的准确.例如这样的题目:有一个n面完全相同的骰子，各面上标有整数1-ｎ，连续投掷m次，将所得面点数相加,则所得和为p的概率是多少?在这个问题中，可能性的分类十分重要，极易因“想当然”而使分类不等可能,或使问题难以思考计算.高一“反虚”小组将召开代表大会，但没有人愿意致开幕词。为了选出最后的人员,决定通过“上台阶”的方式。每个人都可以用任意多次登上这些台阶,每次可以跨上任意多级台阶。如果一个人上ｎ级台阶时没有与他人不完全相同的方式,则此人立即被选出。则问小组内的第几个人将被选出？解答案：2n-１＋1．用简单的方法考虑:每一级台阶的中间可以停留，可以不停留;一共n-1个间隔,每个“间隔”有2个不同选择,运用乘法原理,共2n-１个选择;第2n-1+１个人将没有其他选择,必然被选出。小结f(n)=　fn(ｎ).令f(0)=1,而ｆ(1)=１．　每次至多跳一个ｆ1(n)＝f1（ｎ-1);　每次至多跳两个f2（n)=ｆ2(n-１)+f2（n-2);　　　……　　每次至多跳n个fn(ｎ)=fn(ｎ-1)+fn(n-2)+…+fn(0);结论：2ｎ－１＝(2n-2+2n－3+…＋２+１)+１.奇妙的数列！这些数列之间有什么关系?项链排列用绳子将5粒珠子串成一副项链.今有3种颜色的珠子可供选用，问共可串成多少种不同的项链？解　N5=｛１，2，３,4,5},m=3,N５上的置换群为G={　P１=I,Ｐ２,P3,…，P1０｝,其中P1,P２，…P5与例1相同，而P６＝（1)(2，5)(３,４），关于过圆心及1的直线轴对称，P7=(2)(1,3)（4,5),关于过圆心及2的直线轴对称,P８=(3)(2，4)(1，5)，关于过圆心及３的直线轴对称,P９=(4)(3，5)(1，2),关于过圆心及4的直线轴对称，P10=(5)(1,4)(2,3),关于过圆心及5的直线轴对称，于是，　由Polyａ计数定理得，不同的项链数为Ｍ=1／10*(３５＋3+３+３+3+33+３3+33＋33+３3)=39.小结　对有关置换问题,找清置换群，分类讨论是关键.关于置换群和Polyａ计数定理,可以解决诸如正方体染色等问题.例如:给定正方体,每面只染一种颜色，共m种颜色可用,共多少种不同方法?这个问题,请你自行思考.这里给出结论：Ｍ=m2(ｍ４+３ｍ2+1２m+8）/２４.设有n种不同颜色的颜料，分别用于染色m个形状不同的珠子(n＞＝m),每个珠子至少用一种颜色,每种颜色恰好用于染色一个珠子。并用这m个珠子组成一条项链,问共有多少种不同的项链颜色形状组成方式（设任意k种颜料混合后的颜色均不相同,颜色形状中任意一个不相同即视为不同)?解　这是经典的“放球问题”与“项链问题”的结合.放球问题设符合条件的方法数为f.我们先考虑把n个球放入ｍ个盒子后，都作直线排列.（1)将ｎ个球放入k个盒子中，有f种方法.(2)将k1个盒子中的每个盒内p1个球做排列，有(p1!)k1种方法.(3)将k２个盒子中的每个盒内p２个球做排列,有(p2!)ｋ2种方法.…（m+1)　将km个盒子中的每个盒内pｍ个球做排列,有（pm!)kｍ种方法．由乘法原理得:n!=ｆ(p１！)k1(p2！)k2...（pm!)kｍ种方法．f=n！／(　(p１!)k１（p2！)k2...(pm！）ｋm).应用容斥原理，得：　f(n,r)　=ｒn－C1r(ｒ－1)!＋　C2ｒ（r－2）!-C3r(r-3)!+…　+(-１）ｒ－1Crr－1.（n个不同的球,r个盒子可辨、无空盒)注:放球问题还有许多不同形式（盒子是否不同,球是否不同，是否允许有空盒等），请自行研究.项链问题对每一个固定的ｎ元素的圆排列，在任意两个元素之间剪开，得到ｎ个直线排列.圆排列数Pｎn/n=(ｎ－1)!.若将n个不同的珍珠,用线穿项链的方法数为D,D＝（n-1)！／2．两个顺逆不同的圆排列是同一个项链排列.源问题我们思考原来的问题.先放球,后项链排列．运用乘法原理:方案数为(m-1)!*f(n,ｍ)／2.在讨论过程中,不重不漏是关键．小结　　n个元素排列成m组的问题,有很多变种,是很有趣的。例如:设有n粒不同颜色的珠子组成ｍ条项链(ｎ>=m），问共有多少种不同的项链组成方式？这个问题，请你自行思考。圆排列从n个不同元素中不重复地取出m（1≤ｍ≤ｎ）个元素在一个圆周上,叫做这n个不同元素的圆排列。如果一个m-圆排列旋转可以得到另一个m-圆排列，则认为这两个圆排列相同。ﻫ特别地，当m=n时,n个不同元素作成的圆排列总数为（ｎ-１)!。  博杰学习网竞赛小组“先进人物评比”最终圈定了N个人，需要决定最终的三个“先进人物”人选。方法是:这Ｎ个人排成一行，从第一名开始，１至3循环报数,凡报到３的就退出,余下的向前靠拢，按此规则重复进行。直到第p次报数后,只剩下3个人为止。试问：这剩下的三个人,分别在队伍最初的什么位置?解设N个人的编号依次为1,2,…Ｎ。最后剩下的三个人中,第三人的编号为bN,因bN未被淘汰，故不是3的倍数。第一次报数后淘汰了[N/3］个人,还剩N-［Ｎ/3]个人。ｂＮ向前移动了bN-ｂＮ-［n/3]个人,前面淘汰了［bN]／3＝(bＮ-rN)（rN=1，2)个人。故ｂN=（3bN-[n／３］　-rN)/2.其中当ｂN-[ｎ/3]为奇数时，rＮ=1；否则,ｒN=2,每报一次号,人数减少1/3（除不尽时取整).计算ｂN逐步归纳为减小的数列，最终化归到小情况.　例如Ｎ=１000时,第三个人的初始位置是712．将圆分成n(2≤ｎ）个扇形，现用m（2≤m）种颜色给这些扇形染色，每个扇形恰染一种颜色且要求相邻的扇形颜色互不相同.问有多少种不同的染色方法？解设染色方法数为an．求初始值．当n＝２时,给Ｓ1染色有m种方法,给S2染色有ｍ－1种方法，所以a2=ｍ(ｍ-1)．求递推关系.给S１染色有m种方法,给Ｓ2…Sｎ染色有m-1种方法,共有m(m－１)ｎ-１种方法．分为两类：一类是Sn与Ｓ1不同色,此时染色方法有ａn种。另一类是Sｎ与S１同色，Sn与Ｓ１可合并为一个扇形,Sn－1与S1不同色，染色方法有ａn-1种。由加法原理,得:an+ａn-1=m（m-1)n-1(n>=2).(3)求ａn.构造等比数列。结论:共有an=(m－1）n+(-1)ｎ（m－1)种染色方法。小结：１、“在”与“不在”可以相互转化.解决某些元素在某些位置上用“定位法”,解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解.2、排列组合应用题极易出现“重”、“漏”现象，而“重”、“漏”错误常发生在该不该分类、有无次序的问题上.为了更好地防“重”堵“漏”,在做题时需认真分析自己做题思路,也可改变解题角度，利用一题多解核对答案．