排列组合问题的求解策略

2019-08-20 15:10

解答排列组合问题,首先必须认真审题,明确是属于排列问题还是组合问题,或者属于排列与组合的混合问题,其次要抓住问题的本质特征,灵活运用基本原理和公式进行分析解答。同时还要注意讲究一些策略和方法技巧,使一些看似复杂的问题迎刃而解。下面介绍几种常用的解题方法和策略。

一、合理分类与准确分步法

解含有约束条件的排列组合问题,应按元素性质进行分类,按事情发生的连续过程分步,保证每步独立,达到分类标准明确,分步层次清楚,不重不漏。

例 1 、五个人排成一排,其中甲不在排头,乙不在排尾,不同的排法有 ( )

A . 120 种 B . 96 种 C . 78 种 D . 72 种

分析:由题意可先安排甲,并按其分类讨论: 1 )若甲在末尾,剩下四人可自由排,有 种排法; 2 )若甲在第二,三,四位上,则有 种排法,由分类计数原理,排法共有 种,选 C 。

解排列与组合并存的问题时,一般采用先选(组合)后排(排列)的方法解答。

例 2 、 4 个不同小球放入编号为 1 , 2 , 3 , 4 的四个盒中,恰有一空盒的方法有多少种?

分析: 因恰有一空盒,故必有一盒子放两球。 1 )选:从四个球中选 2 个有 种,从 4 个盒中选 3 个盒有 种; 2 )排:把选出的 2 个球看作一个元素与其余 2 球共 3 个元素,对选出的 3 盒作全排列有 种,故所求放法有 种。

二、元素分析与位置分析法

对于有附加条件的排列组合问题,一般采用:先考虑满足特殊的元素和位置,再考虑其它元素和位置。

例 3 、 用 0 , 2 , 3 , 4 , 5 ,五个数字,组成没有重复数字的三位数,其中偶数共有( )。

• 24 个 B 。 30 个 C 。 40 个 D 。 60 个

[ 分析 ] 由于该三位数为偶数,故末尾数字必为偶数,又因为 0 不能排首位,故 0 就是其中的“特殊”元素,应该优先安排,按 0 排在末尾和 0 不排在末尾分两类: 1 ) 0 排末尾时,有 个, 2 ) 0 不排在末尾时,则有 个,由分数计数原理,共有偶数 =30 个,选 B 。

例 4 、 马路上有 8 只路灯,为节约用电又不影响正常的照明,可把其中的三只灯关掉,但不能同时关掉相邻的两只或三只,也不能关掉两端的灯,那么满足条件的关灯方法共有多少种?

分析:表面上看关掉第 1 只灯的方法有 6 种,关第二只,第三只时需分类讨论,十分复杂。若从反面入手考虑,每一种关灯的方法对应着一种满足题设条件的亮灯与关灯的排列,于是问题转化为“在 5 只亮灯的 4 个空中插入 3 只暗灯”的问题。故关灯方法种数为

三、插空法、捆绑法

对于某几个元素不相邻的排列问题,可先将其他元素排好,再将不相邻元素在已排好的元素之间及两端空隙中插入即可。

例 5 、 7 人站成一排照相, 若要求甲、乙、丙不相邻,则有多少种不同的排法?

分析: 先将其余四人排好有 种排法,再在这人之间及两端的 5 个“空”中选三个位置让甲乙丙插入,则有 种方法,这样共有 种不同排法。

对于局部“小整体”的排列问题,可先将局部元素捆绑在一起看作一个元,与其余元素一同排列,然后在进行局部排列。

例 6 、 7 人站成一排照相,甲、乙、丙三人相邻,有多少种不同排法?

分析: 把甲、乙、丙三人看作一个“元”,与其余 4 人共 5 个元作全排列,有 种排法,而甲乙、丙、之间又有 种排法,故共有 种排法。

四、总体淘汰法

对于含有否定字眼的问题,可以从总体中把不符合要求的除去,此时需注意不能多减,也不能少减。

例如在例 3 中,也可用此法解答:五个数字组成三位数的全排列有 个,排好后发现 0 不能排首位,而且数字 3 , 5 也不能排末位,这两种排法要除去,故有 个偶数。

五、顺序固定问题用“除法”

对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一同排列,然后用总排列数除以这几个元素的全排列数。

例 7 、 6 个人排队,甲、乙、丙三人按“甲 --- 乙 --- 丙”顺序排的排队方法有多少种?

分析: 不考虑附加条件,排队方法有 种,而其中甲、乙、丙的 种排法中只有一种符合条件。故符合条件的排法有 种。

六、构造模型 “隔板法”

对于较复杂的排列问题,可通过设计另一情景,构造一个隔板模型来解决问题。

例 8 、 方程 a+b+c+d=12 有多少组正整数解?

分析:建立隔板模型:将 12 个完全相同的球排成一列,在它们之间形成的 11 个间隙中任意插入 3 块隔板,把球分成 4 堆,每一种分法所得 4 堆球的各堆球的数目,对应为 a 、 b 、 c 、 d 的一组正整解,故原方程的正整数解的组数共有

又如方程 a+b+c+d=12 非负整数解的个数;三项式 , 四项式 等展开式的项数,经过转化后都可用此法解。

七、分排问题“直排法”

把几个元素排成前后若干排的排列问题,若没有其它的特殊要求,可采取统一排成一排的方法来处理。

例 9 、 7 个人坐两排座位,第一排 3 个人,第二排坐 4 个人,则不同的坐法有多少种?

分析: 7 个人可以在前两排随意就坐,再无其它条件,故两排可看作一排来处理,不同的坐法共有 种。

八、表格法

有些较复杂的问题可以通过列图表使其直观化。

例 10 、 9 人组成篮球队,其中 7 人善打前锋, 3 人善打后卫,现从中选 5 人(两卫三锋,且锋分左、中、右,卫分左右)组队出场,有多少种不同的组队方法?

分析:由题设知,其中有 1 人既可打锋,又可打卫,则只会锋的有 6 人,只会卫的有 2 人。列表如下:

人数