《隔板法在排列组合中的应用.pdf》由会员分享，可在线阅读，更多相关《隔板法在排列组合中的应用.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、在排列组合中，对于将不可分辨的球装入到可以分辨的盒子中而求装入方法数的问题，常用隔板法。例 1.求方程 X+Y+Z=10 的正整数解的个数。分析将 10 个球排成一排，球与球之间形成 9 个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为 x、y、z 之值（如以下图）。则隔法与解的个数之间建立了一一对立关系，故解的个数为 C9=36（个）。实际运用隔板法解题时，在确定球数、如何插隔板等问题上形成了一些技巧。下面举例说明。技巧一：添加球数用隔板法。技巧一：添加球数用隔板法。例 2.求方程 X+Y+Z=10 的非负整数解的个数。分析注意到x、y、z
2、 可以为零，故上题解法中的限定“每空至多插一块隔板”就不成立了，怎么办呢？只要添加三个球，给x、y、z 各一个球。这样原问题就转化为求 X+Y+Z=13 的正整数解的个数了，故解的个数为 C12=66（个）。点评 本例通过添加球数，将问题转化为如例 1 中的典型隔板法问题。技巧二：减少球数用隔板法：技巧二：减少球数用隔板法：例 3.将 20 个相同的小球放入编号分别为1，2，3，4 的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。解法 1：先在编号 1，2，3，4 的四个盒子分别放 0，1，2，3 个球，剩下 14 个球，有 1 种方法；再把剩下的球分成 4 组，每组至少 1
3、个，由1/522例 1 知方法有 C13=286（种）。解法 2：第一步先在编号 1，2，3，4 的四个盒子分别放 1，2，3，4 个球，剩下10 个球，有1 种方法；第二步把剩下的10 个相同的球放入编号为 1，2，3，4 的盒子里，由例 2 知方法有 C13=286（种）。点评两种解法均通过减少球数将问题转化为例1、例 2 中的典型问题。技巧三：先后插入用隔板法。例 4.为宣传党的十六大会议精神，一文艺团体下基层宣传演出，准备的节目表中原有 4 个歌舞节目，如果保持这些节目的相对顺序不变，拟再添两个小品节目，则不同的排列方法有多少种？分析记两个小品节目分别为 A、B。先排 A 节目。根据
4、A 节目前后的歌舞节目数目考虑方法数，相当于把 4 个球分成两堆，由例 2 知有 C5种方法。这一步完成后就有 5 个节目了。再考虑需加入的 B 节目前后的节目数，同理知有 C6种方法。故由分步计数原理知，方法共有C5*C6(种)。点评对此题所需插入的两个隔板采取先后依次插入的方法，使问题得到巧妙解决。解答排列组合问题，首先必须认真审题，明确是属于排列问题还是组合问题，或者属于排列与组合的混合问题，其次要抓住问题的本质特征，灵活运用基本原理和公式进行分析，同时还要注意讲究一些策略和方法技巧。下面介绍几种常用的解题方法和策略。2/5111133解决排列组合问题有几种相对比较特殊的方法。下面通过例
5、题逐个掌握：一、相邻问题一、相邻问题-捆绑法捆绑法 不邻问题不邻问题-插空法插空法对于某几个元素不相邻的排列问题，可先将其他元素排好，再将不相邻元素在已排好的元素之间与两端空隙中插入即可。例题 1一节目表上原有 3 个节目，如果保持这 3 个节目的相对顺序不变，再添进去 2 个新节目，有多少种安排方法?A.20 B.12 C.6 D.4答案A。解析首先，从题中之3 个节目固定，固有四个空。所以一、两个新节目相邻的的时候：把它们捆在一起，看成一个节目，此时注意：捆在一起的这两个节目本身也有顺序，所以有：C(4，1)2=42=8 种方法。二、两个节目不相邻的时候：此时将两个节目直接插空有：A(4，
6、2)=12 种方法。综上所述，共有 12+8=20 种。二、插板法二、插板法一般解决相同元素分配问题，而且对被分成的元素限制很弱(一般只要求不等于零)，只对分成的份数有要求。例题 2把 20 台电脑分给 18 个村，要求每村至少分一台，共有多少种分配方法?A.190 B.171 C.153 D.19答案B。解析此题的想法即是插板思想：在 20 电脑部所形成的 19 个空中3/5任意插入 17 个板，这样即把其分成 18 份，那么共有：C(19，17)=C(19，2)=171 种。三、特殊位置和特殊元素优先法三、特殊位置和特殊元素优先法对有限制的排列组合问题中的特殊元素或特殊位置优先考虑。例题
7、2从 6 名运动员中选 4 人参加 4100 米接力，甲不跑第一棒和第四棒的参赛方案各有多少种?A.120 B.240 C.180 D.60答案B。解析方法一：特殊位置优先法：首先填充第一棒，第一棒共有5个元素可供选择，其次第 4 棒则有 4 个元素可以选择;然后第 2 棒则有 4个元素可以选择，第3棒则有3个元素可以选择。则共有5443=240种。方法二：特殊元素优先法：首先考虑甲元素的位置第一类，甲不参赛有 A(5,4)=120 种排法;第二类，甲参赛，因只有两个位置可供选择，故有 2 种排法;其余 5人占 3 个位置有 A(5,3)=60 种占法，故有 260=120 种方案。所以有 1
8、20+120=240 种参赛方案。四、逆向考虑法四、逆向考虑法对于直接从正面算比较复杂的排列、组合题，我们就要学会间接的方法。正方体 8 个顶点中取出 4 个，可组成多少个四面体?A.70 B.64 C.61 D.584/5答案D。解析所求问题的方法数=任意选四点的组合数-共面四点的方法数，共 C(8，4)-12=70-12=58 个。五、分类法五、分类法解含有约束条件的排列组合问题，应按元素性质进行分类，按事情发生的连续过程分步，保证每步独立，达到分类标准明确，分步层次清楚，不重不漏。例题 3五个人排成一排，其中甲不在排头，乙不在排尾，不同的排法有A.120 种 B.96 种 C.78 种 D.72 种答案C。解析由题意可先安排甲，并按其分类讨论：1)若甲在末尾，剩下四人可自由排，有 A(4，4)=24 种排法;2)若甲在第二，三，四位上，则有 33321=54 种排法，由分类计数原理，排法共有24+54=78种，选 C5/5