排列组合问题经典题型(排列组合问题)

导读 大家好,我是小曜,我来为大家解答以上问题。排列组合问题经典题型,排列组合问题很多人还不知道,现在让我们一起来看看吧!排列组合应用问...

大家好,我是小曜,我来为大家解答以上问题。排列组合问题经典题型,排列组合问题很多人还不知道,现在让我们一起来看看吧!

排列组合应用问题,题型繁多,解法独特,但经仔细分析研究,还是有一定规律可循。关键是掌握两个计数原理及排列组合的定义,了解一些基本题型及其解法,掌握基本的一些分析问题的方法。

一、基本题型及其解法

(1)纯排列问题

“从几个不同元素中取出m个元素的排列”是最简单的纯排列问题,但是它有三种题型变化,下面分别用例题予以说明。

例1 现有九位同学排成一行,试问:

①如果其中甲、乙两位同学必须排在两端,那么一共有多少种排法?

②如果甲不能排在最左端,乙不能排在最右端,那么一共有多少种排法?

本例是属于“某些元素‘在’或‘不在’某几个位置上”的一种排列题型。“在”,一般用直接法解,即先取出这几个元素并让它们落在指定的位置上,然后再考虑其它元素;“不在”,一般用间接法,转化为“在”来求解。

例2 现有五位男同学,四位女同学排成一行,试问:

① 如果男女同学各自排在一起,那么一共有多少种排法?

② 如果男女同学相间地排,那么一共有多少种排法?

本例是属于“某些元素‘相邻’或‘不相邻’的一种排列题型。“相邻”则将这要求“相邻”的m个元素捆绑起来看成一个整体(一个大元素)与另外(n-m)个元素进行全排列,再乘以这m个元素自身的全排列数即 种排法;“不相邻”,一般用插空法来解,即先将另外p(P≥m-1)个元素排好,留出(p+1)个空挡,再让这不能相邻的m个元素插进去,共有排法 (种)。

例3 现有五位男同学,四位女同学排成一行,试问:

① 如果其中甲、乙、丙三人次序一定,那么一共有多少种排法?

② 如果男同学次序一定,女同学次序也一定,那么一共有多少种排法?

本例是属于“某几个元素“次序一定”的一种排列题型。它的解法是先将n(n>m)个元素全排列有 种,就其中m个元素而言有 种排法,但由于要求这m个元素次序一定,因此只能取 中的某一种排法,故共有排法 / 种,即顺序固定问题用除法。

(2)纯组合问题

“从几个不同元素中取出m个元素的组合”是最简单的纯组合问题,但是它有两种题型变化,下面分别用例题予以说明。

例4 现从五位男同学,四位女同学中选出5名代表,试问其中:

① 男甲、女A都必须当选,有几种选法?

② 男甲必须当选,女A不能当选,有几种选法?

本例是属于“‘含有’或‘不含有’某些元素”的一种组合题型。“含”则先将这些元素取出,再由另外元素补足;“不含”则先将这些元素剔除,再从留下的元素中去取。

例5 现从五位男同学,四位女同学中选出5名代表,试问其中:

① 至少有一个女同学当选,有几种选法?

② 最多有三个女同学当选,有几种选法?

本例是属于“‘至少’或‘最多’含有几个元素”的一种组合题型。用分类法或排杂法解都可以,但是解这类题必须十分重视“至少”与“最多”这两个关键词的含义,要保证分类合理,排杂准确,谨防漏解与重复。

(3)排列组合混合题

这类问题有两群之间的排列题和分配(分组)问题两类题型。

例6 ①用1,2,3,4,5,6,7这七个数字组成没有重复数字的五位数中,由两个偶数数字和三个奇数数字组成的有多少个?

②从n个不同元素里取出的m个元素的排列中,试问其中含有a1,a2,……,ap(n>m>p)这p个元素且这p个元素排在一起的排列有多少种?

本例是典型的“两群之间的排列问题”,它的解法是根据公式 得来的,即从n个元素中取出m个元素的排列,可以分成两步来完成:取出( )—排好( )。

例7 、6本不同的书,按照以下要求处理,各有几种分法?

① 平均分给甲、乙、丙三人。

② 甲得一本,乙得两本,丙得三本。

③ 一人得一本,一人得两本,一人得三本。

④ 平均分成三堆(组)。

⑤ 一堆一本,一堆两本,一堆三本。

本例的①、②、③是属于“分配问题”,它有两种情况:一种是平均分配或者按某一种确定的分配方案分配(如②),那么只要一个一个地按要求去取,然后再将这些组合数乘起来即得;另一种是分配方案不确定的(如③),那么还要乘以分配人数的全排列数。

本例的④、⑤是属于“分堆(组)”问题,它有两种情况:一是平均分组,如有kn不同元素平均分成k组,那么分法有 种。另一种不是平均分组,那么其解法与分配问题的前一种情况相同。

二、解排列组合应用问题的一些分析方法

对于解比较复杂的排列组合应用题,往往比较困难,会有无从下手的感觉。为了提高分析问题和解决问题的能力,这里根据问题的不同特点,介绍五种分析方法。

(一)特征分析法

例8 从1,2,3,……,100这一百个数中,任取两个不同的数相乘,其中积能被5整除的有多少个?能被5整除但不能被5n(n≥2,n∈N)整除的有多少个?

解:两数中只要有一个是5的倍数,那么它们的积就能被5整除,而1到100中共有20个5的倍数的数,故共有取法 种;能被5整除而不能被5n(n≥2,n∈N)整除,那就是说这20个5的倍数的数中,不能取两个相乘;同时还不能取这20个数中本已含有52因数的数25,50,75,100,因此符合题意的积共有 (种)

例9 用1,2,3,4,5,6,7这七个数字组成没有重复数字的五位数,试问其中能被3整除的有多少?

分析:能被3整除的数的特征是各位数字之和是3的倍数,由1+2+3+4+5+6+7=28,又组成的是五位数,因此应从28中减去两个数字使其差为3的倍数,再由大到小依次考虑,便得到下面四种情况:

解①28-1-2=24,由2,4,5,6,7五个数字,可组成 个五位数。

②28-1-6=21或28-2-5=21或28-3-4=21,一共可组成 个五位数。

③28-3-7=18或28-4-6=18可组成 个五位数。

④28-6-7=15可组成 个五位数。

根据分类计数原理:可得能被3整除的五位数共有 =840(个)。

上面两例是抓住了能被5整除与能被3整除的数的特征,再进行有条理有次序(特别是例2)的分析而得出解答的。因此在解应用题时,必须十分注意题意的内含特征以及解题的条理性。

(二)排阵分析法

例10 从1到9这九个自然数中,每次取出不同的两个分别作为对数的底数与真数,问一共可以得到多少个不同的对数值?

分析:由于底数不能取1,因此底数可以从2到9这八个数字中任取一个;真数可以从留下的八个数字中任取一个,故有 个对数。但本题是问“有几个不同的对数值?”,显然 是相同的,只能算一个。那么另外有没有相同的对数值呢?那就要费一番周折了,而且一个一个地找很容易造成遗漏,再考虑到底数取法只有八种情况,当取某一值为底时,真数依次排上的次序性很强(如 等等),而且在排时若遇相同的值立即舍去,“重复取”的情况也就避免了,因此还是直接排出要方便些,可靠些。分别以2,3,4,……,9为底直接排出,可得共有53个不同的对数值

例11 现在将准备从七个学校选出12人组成区篮球队,要求每校至少有一人参加,向各校分配到的队员人数,可能有几种不同情况?

解:由于每校至少要有一人参加,因此这一个名额不妨先分配下去,还余下五个名额,因为没有其他的分配要求,因此这5个名额分配时,可能有如下六种情况。

(注:记号“11111”表示将5个名额分成5个“1”,分配到七个学校中去,每校1人,其余类推)

①分成“11111”有 种分配法。

②分成“2111”有 种分配法。

③分成“221”有 种分配法。

④分成“311”有 种分配法。

⑤分成“23”有 种分配法。

⑥分成“41”有 种分配法。

⑦分成“5”有 种分配法。

因此共有 种分配法。

通过上述两例的分析,可以看出“排阵分析法”主要有三个优点:①解题方法直观,易被接受;②条理性强,便于思考分析;③取舍明确,可避免漏解或重复。

(三)元素、位置分析法

例12 3封不同的信,投入4个不同的信箱,共有多少种不同的投信方法?

解法一:元素分析法(以信为主)

第一封信有四种不同的投法,不论把它投入哪一个信箱里,第二封信还有四种投法,同理第三封信也有四种投法,根据分步计数原理,故共有投法4x4x4=64(种)

解法二:位置分析法(以信箱为主)

四个信箱中某一个信箱收到3封信的有 ;四个信箱中某一个信箱收到2封信的有 ;四个信箱中某三个信箱各收到1封信的,收信方法有 。因此收信方法 (种)

元素分析法(即以元素为主考虑各种可能性)与位置分析法(即以位置为主考虑多种可能性)是解排列组合应用题的两种常用方法,它的优点是研究对象清楚单一易于分析各种情况。

例13 三位教师分配到六个班里,各人数不同的班级,若每人都教两个班,有几种分配方法?

解法一(以教师为主)

这是一个分配问题,第一位教师可从六个班中选二个有 ,第二位教师可从四个班中选二个有 ,第三位教师教余下的二班有 ,因此共有 种不同的分法。

解法二(以班级为主)

将六个班分成三组,每组两个班,共有 分组法,再将每种方法中的三组分配给三位教师有 种,因此共有 种方法。

(四)图形分析法

例14 用0,1,2,3,4,5组成没有重复数字的数,试问能组成多少个大于401325的自然数?

解:大于401325的数,必须是六位数;当最高位数字为5时,形如5xxxxx的数一定大于401325有 个;再看最高位是4时,形如下面的数也必须大于401325:

①41xxxx;42xxxx;43xxxx;45xxxx。共有 个。

②402xxx;403xxx;405xxx共有 个。

③4015xx共有 个。

④401352共有1个。

综上得大于401325的自然数共有 个。

例15 一直线和圆相离,这条直线上有六个点,圆上有四个点,通过其中任意两点作直线,试问:

①最多可作几条直线?②最少可作几条直线?

解:①显然除了A1、A2、A3,……A6 这六点共线外,其余无三点共线时,那以任取其中两点作直线必最多,共有 (条)

如图,由于B1,B2,B3,B4 在圆上,故四点

中任意三点均不共线,因此当过B1,B2,B3,B4

中任意两点的直线(共有 条)正好分

别通过A1、A2、A3,……A6 这六个点时,则直线条数最少,共有 (条)。(如图B2 B4 A1 三点,原来过其中任意两点可作三条直线,而现在只能作一条,减少了两条)

从上两例可以看出,有时结合图形来分析比较直观,易于发现规律。

(五)减元分析法

例16 我们把元素和它的排列完全相同的行列式看成是相同的,否则就是不同的,用三个“1”和六个“0”作三阶行列式,试问能作成多少个不同的行列式?

分析:本题情况比较复杂,因此不妨先减元来分析一下,如两个“1”与两个“0”,作成二阶行列式有:

在排的过程中发现,当两个“1”排好位置以后,那两个“0”只能进入留下的空挡,因此实际上只要排好两个“1”的位置即可,而四个空挡中排两个“1”的方法共有 种,这与实际排出也是一致的,由此减元分析可得原题三阶行列式的个数是 个。

例17 ①将四个“十”号,六个“一”号排成“一十一一十十一十一一”时,符号改变了几次?

②将八个“十”号,六个“一”号排成一列时使符号改变5次的排法共有多少种?

解:①从左往右依次点算,可得符号共改变了6次。

②通过对①的仔细观察分析可以发现:

(a)“十”号旁边排上一个或几个“一”号将使符号改变(“一”号旁边排上“十”号也同样)

(b)两个“十”号之间插入一个或几个“一”号,将使符号改变2次。

(c)最左端那一个“十”号的左边加上一个或几个“一”号,使符号改变一次(最右端那个“十”号的右边加上一个或几个“一”号也同样)

由上述三点发现,再考虑到符号改变5次的要求,我们不妨先让八个“十”号排成一列,留出首尾空位和中间七个空挡,只要在中间的七个空挡中取出两个,各插入一个或几个“一”号,使符号改变4次;再在首或尾空位中放上留下的一个或几个“一”号使符号改变1次,那么问题的要求就满足了。

具体计算过程从略,符号改变5次的排法,共有 (种)

减元分析法是用在一时看不出眉目,或无从下手的排列组合应用题。这时不妨先减元排出,然后仔细观察,分析归纳,找出解题规律。

本文到此讲解完毕了,希望对大家有帮助。

最新文章