解排列组合题的若干方法

原载博杰学习网解排列组合题的若干方法石家庄二中李博杰一、捆绑法捆绑法，即将若干个在排列组合时可看为一体或必须看为一体的物体看成一个整体.捆绑法，方案总数=“捆绑物”内部组合方案数*各“捆绑物”之间组合方案数.例18个女孩，25个男孩围成一个圆圈，每两个女孩之间至少站有两个男孩，共有多少种不同的排列方法？（只要圆旋转一下就重合的方法认为是相同的）解令每个女孩“带着”两个男孩（女孩在前，男孩在后）参加排队.(1)一个女孩、两个男孩组成一组，共有8组，还有9个“单独”的男孩.选择并排列这16个“跟着女孩的”男孩共有P1625=25!/9!种方式.(2)一共17个“相互独立”的物体，他们之间共有17！种排列方式.(3)围成一个圆圈,共有17种可能，要除以17，以排除旋转重合的问题.运用乘法原理,这些人共有16!*25!/9!种排列方式.小结运用“捆绑法”，要注意避免重复排列.这种思想方法类似“程序法”，即将排列组合的过程分解成一个个相互独立的步骤，分别计算其方案数，再相乘.例2七人排成一排，甲、乙两人必须相邻，且甲、乙都不与丙相邻，则不同的排法有（）种(A)960种（B）840种（C）720种（D）600种答案A小结本题涉及一类重要问题：问题中既有元素的限制，又有排列的问题，一般是先元素（即组合）后排列。例3设a1,a2,a3为三个整数，且满足0a1a2a315,a2-a12,a3-a22.求满足上述条件的有序数组{a1,a2,a3}的个数.解应用捆绑法.将a1及其后面的两个“空格”看为一个整体，a2及其后面的两个“空格”看为一个整体.如此形成10个“新元素”，从中任意选择3个，共C310种方法.原载博杰学习网二、插空法“相邻”用“捆绑”，“不邻”就“插空”.以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”；以某些元素不能相邻为附加条件的,可采用“插空法”。“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定.例48人排成一队，A、B、C三人互不相邻，D、E两人也互不相邻的排法共有多少种？解先把除了ABC以外的5个人排列好是P（5，5)然后就有了6个空挡，用插入排列法：6个空挡里面插入3个人于是为P(6，3),所以ABC不在一起的总数为P（5，5)*P(6，3)但是这样有重复的，因为DE可能在一起了，于是要扣除ABC不在一起但是DE在一起的，也是利用先捆绑DE和剩下三人就是4个全排列然后插入ABC三个人用插空排列法：2*P（4，4）*P（5，3）总的答案为：P（5，5)*P(6，3)-2*P（4，4）*P（5，3）＝11520种。点评此题用到分类讨论，扣除法，插空排列，捆绑排列，排列数公式，组合数公式，加法原理.......小结以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”；以某些元素不能相邻为附加条件的,可采用“插空法”.“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定.例5从6个学校中选出30名学生参加数学竞赛,每校至少有1人,这样有几种选法?解问题相当于把个30相同球放入6个不同盒子(盒子不能空的)有几种放法?这类问题可用“隔板法”处理.采用“隔板法”得:C529=4095.小结把n个相同元素分成m份每份,至少1个元素,问有多少种不同原载博杰学习网分法的问题可以采用“隔板法”得出共有多少种.三、递推法例6N*为全体正整数的集合,是否存在一一映射φ:N*N*满足条件：对一切kN*,都有k|(φ(1)+φ(2)+……+φ(k))?证明你的结论.注:映射φ:AB称为一一映射,如果对任意bB,有且只有一个aA使得φ(a)=b.题中“|”为整除符号.解存在.对n归纳定义φ(2n－1)及φ(2n)如下：令φ(1)=1,φ(2)=3.设已定义出不同的正整数值φ(k)(1≤k≤2n)满足整除条件且包含1,2,…,n,设v=minN*\{φ(1),…,φ(2n)},由于2n+1与2n+2互素,根据孙子定理,存在不同于v及φ(k)(1≤k≤2n)的正整数u满足同余式组u－S2n(mod2n+1)－S2n－v(mod2n+2).定义φ(2n+1)=u,φ(2n+2)=v.则正整数φ(k)(1≤k≤2n+2)也互不相同,满足整除条件,且包含1,2,…,n+1.根据数学归纳法原理,已经得到符合要求的一一映射.φ：N*N*.例7（错位排列）五封标号为1~5的信放进5个编号为1~5的信笺里面，全错位排列（即1不放1，2不放2，依次类推）一共有多少种放法.解这是著名的信封问题,很多著名的数学家都研究过。瑞士数学家欧拉按一般情况给出了一个递推公式：用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的错误之下，共有错装法f(n-2)+f(n-1)种。a装入C，装入D……的n－2种错误之下，同样都有f(n-2)+f(n-1)种错装法，因此:f(n)=(n-1){f(n-1)+f(n-2)}这是递推公式，令n＝1、2、3、4、5逐个推算就能解答此问题。f(1)=0f(2)=1f(3)=2f(4)=9f(5)=44答案是44种。小结用容斥原理亦可解决此题。普遍结论为错排公式：f(n)=n!(1–1/1!+1/2!-1/3!+…+(-1)n/n!).例8在n*m的网格中，从(0,0)点到(n,m)点,只能沿网格的边向x轴正方向或y轴正方向前进.问共有多少种不同的前进路线?解对任意一个非x轴、y轴上的点(x,y)，可以从点(x,y-1)走来，也可以从点(x-1,y)走来.因此,设(x,y)处的路线条数为f(x,y),则有递推公式:f(x,y)=f(x,y-1)+f(x-1,y).下面的推理很重要：根据上述递推公式,可得f(x,y)=C(x+y,x).即从x+y件物品中选出无顺序的x件（或y件）的总方案数.即f(x,y)=(x+y)!/(x!y!).小结上述问题中把每个f(x,y)指标在对应的坐标点处，再将坐标系顺时针旋转135。，你发现了什么？这是杨晖三角，f(x,y)=C(x+y,x).而我们知道，C(x,y)=C(x-1,y)+C(x,y-1).这就是通项公式的来源.以上问题还可以推广.例9有甲乙两队，各有7名队员，分别编号1-7，首先两队编号为1的队员对抗比赛，负者被淘汰，胜者与负方的2号队员比赛，以此类推.直到某队全部被淘汰为止.问最后有多少种不同比赛方式？解设f(x,y)表示甲乙两队分别由x,y名队员组成时的比赛方式数.由于上次可能是甲、乙两队中某个被淘汰，故通项公式为f(x,y)=f(x-1,y)+f(x,y-1).转化到与上题相同的数学模型.即f(x,y)=(x+y)!/(x!y!).小结上述问题是一个二元递推函数，与递推函数通项公式的处理有关，有兴趣的同学可以继续深入学习有关内容.求排列组合递推问题时，一定要注意以下几个方面：（1）初始条件（2）递推关系中+1，原载博杰学习网的问题（3）递推终止条件.递推的高级形式是动态规划,以上就是一个最简单的动态规划范例.例10甲乙两人参加竞选，甲得m张选票，乙得n张选票，mn.问：在m+n张选票逐一唱完的过程中，甲得的票数一直领先的概率是多少？解这是组合分析中重要的选择问题.采用折线法。是甲的选票，取ak=1;是乙的选票，ak=-1.得到m+n-1届的折线，甲的票数一直领先。由折线法公式，得：C(m+n-1,m-1)-C(m+n-1,m)=(m-n)C(m+n,m)/(m+n).概率为领先数/总可能数.P=C(m+n,m)(m-n)/C(m+n-1,m-1)(m+n).小结本题采用了一种重要的思想方法，将实际问题转化成折线树木的问题解决.这种方法适合“互相追逐”的问题，即每步或+1，或-1，不得超过某个极限，适合折线法.如：排队买票问题等.关于概率，分类时应特别注意“等可能性”，才能保证计算的准确.例如这样的题目：有一个n面完全相同的骰子，各面上标有整数1-n，连续投掷m次，将所得面点数相加，则所得和为p的概率是多少？在这个问题中，可能性的分类十分重要，极易因“想当然”而使分类不等可能，或使问题难以思考计算.例11高一“反虚”小组将召开代表大会，但没有人愿意致开幕词。为了选出最后的人员，决定通过“上台阶”的方式。每个人都可以用任意多次登上这些台阶，每次可以跨上任意多级台阶。如果一个人上n级台阶时没有与他人不完全相同的方式，则此人立即被选出。则问小组内的第几个人将被选出？解答案：2n-1+1.用简单的方法考虑：每一级台阶的中间可以停留，可以不停留；一共n-1个间隔，每个“间隔”有2个不同选择，运用乘法原理，共2n-1个选择；第2n-1+1个人将没有其他选择，必然被选出。小结f(n)=fn(n).令f(0)=1，而f(1)=1.每次至多跳一个f1(n)=f1(n-1);每次至多跳两个f2(n)=f2(n-1)+f2(n-2);„„每次至多跳n个fn(n)=fn(n-1)+fn(n-2)+„+fn(0);原载博杰学习网结论：2n-1=(2n-2+2n-3+„+2+1)+1.奇妙的数列！这些数列之间有什么关系？四、项链排列例12用绳子将5粒珠子串成一副项链.今有3种颜色的珠子可供选用,问共可串成多少种不同的项链?解N5={1,2,3,4,5},m=3,N5上的置换群为G={P1=I,P2,P3,„,P10},其中P1,P2,„P5与例1相同，而P6=(1)(2,5)(3,4),关于过圆心及1的直线轴对称，P7=(2)(1,3)(4,5),关于过圆心及2的直线轴对称，P8=(3)(2,4)(1,5),关于过圆心及3的直线轴对称，P9=(4)(3,5)(1,2),关于过圆心及4的直线轴对称，P10=(5)(1,4)(2,3),关于过圆心及5的直线轴对称，于是，由Polya计数定理得，不同的项链数为M=1/10*(35+3+3+3+3+33+33+33+33+33)=39.小结对有关置换问题，找清置换群,分类讨论是关键.关于置换群和Polya计数定理，可以解决诸如正方体染色等问题.例如：给定正方体，每面只染一种颜色，共m种颜色可用，共多少种不同方法？这个问题,请你自行思考.这里给出结论：M=m2(m4+3m2+12m+8)/24.例13设有n种不同颜色的颜料，分别用于染色m个形状不同的珠子（n=m），每个珠子至少用一种颜色，每种颜色恰好用于染色一个珠子。并用这m个珠子组成一条项链，问共有多少种不同的项链颜色形状组成方式（设任意k种颜料混合后的颜色均不相同,颜色形状中任意一个不相同即视为不同）？解这是经典的“放球问题”与“项链问题”的结合.放球问题设符合条件的方法数为f.我们先考虑把n个球放入m个盒子后,都作直线排列.（1）将n个球放入k个盒子中，有f种方法.(2)将k1个盒子中的每个盒内p1个球做排列,有(p1!)k1种方法.(3)将k2个盒子中的每个盒内p2个球做排列,有(p2!)k2种方法.„(m+1)将km个盒子中的每个盒内pm个球做排列,有(pm!)km种方法.由乘法原理得：n!=f(p1!)k1(p2!)k2...(pm!)km种方法.f=n!/((p1!)k1(p2!)k2...(pm!)km).应用容斥原理，得：f(n,r)=rn