上一课我们解决了排列组合最基础、也是最容易出错的一个问题什么时候使用 “加法” 什么时候使用 “乘法” 本课就在此基础上继续学习排列组合中的特殊限制问题重点是捆绑法、插空法以及“特殊位置”问题。本课非常适合CSP-J初赛因为很多题目并不要求孩子真的计算一个特别复杂的组合数而是考查学生能不能读懂条件、拆分问题、选择正确的方法。第四十一课排列组合解题技巧②——捆绑法、插空法与特殊位置一、先复习上一课的“四个问题”做排列组合题之前先问自己① 是分类还是分步或者 → 加法 然后 → 乘法② 顺序重要吗顺序重要 → 排列 顺序不重要 → 组合③ 能不能重复能重复 → 每个位置的选择数可能不变 不能重复 → 后面的选择数减少④ 有没有特殊条件例如必须相邻不能相邻必须在一起某个人必须站在某个位置某几个元素不能在一起本课主要解决第四类问题。二、第一种魔法捆绑法我们先看一道非常经典的问题。例题15个人A B C D E排成一排。要求A和B必须站在一起。有多少种排法第一步不要把A、B分开考虑因为题目说A和B必须相邻。所以我们把他们“绑起来”。[A B]于是A B C D E变成[AB] C D E现在一共有4个“东西”[AB] C D E第二步先排列4个整体4个元素排队4!第三步AB内部还可以交换因为AB和BA都满足“相邻”。所以内部有2!种。第四步相乘4! × 2 24×2 48三、捆绑法到底在做什么孩子可以把它理解成先把必须在一起的人捆成一个“小团队”先安排团队的位置再安排团队内部的人。例如A B C D E变成┌─────┐ │ A B │ C D E └─────┘ ↑ 一个整体所以整体排列×内部排列四、如果有3个人必须站在一起呢例题26个人A B C D E F排成一排。要求A、B、C三个人必须连续站在一起。怎么办第一步捆起来[ABC] D E F原来6个人现在变成[ABC] D E F一共4个整体。所以外部排列4!第二步ABC内部排列三个人可以3!种排列。所以4! × 3! 24×6 144五、一个非常重要的规律如果n个人排队其中k个人必须连续在一起。可以先把这k个人捆成一个整体。那么外部有n-k1个整体外部排列(n−k1)!内部排列k!因此当然这个公式大家不要机械背。CSP-J初赛更重要的是理解为什么要减掉 k-1 个位置因为A B C三个独立的人A B C占3个位置。捆起来以后[ABC]只占1个位置。所以整体数量减少3−1 2六、第二种魔法插空法现在换一种完全不同的限制。例题3有3个男生A B C和2个女生X Y5个人排成一排要求两个女生不能相邻。怎么做七、先排谁这时候我们不要先排女生。先排男生。A B C有3!种排列。假设某一次排成A B C现在看看男生之间和两边有什么位置_ A _ B _ C _一共有4个“空”。八、为什么是4个空仔细数① A前面 ② A和B之间 ③ B和C之间 ④ C后面也就是_ A _ B _ C _ ↑ ↑ ↑ ↑ 1 2 3 4一共314个空。九、为什么女生要插空因为题目要求两个女生不能相邻。如果我们把女生分别插入不同的空中就天然不会相邻。例如X A Y B C女生X Y不相邻。但是A X Y B C两个女生就在一起了。所以不能相邻 → 尝试把它们插入不同的空。这就是插空法十、继续计算男生排列3!4个空中选择2个两个女生自己还可以交换2!因此计算所以答案是72十一、插空法的核心思想记住这一幅图A B C ↓ ↓ ↓ _ A _ B _ C _先把“不受限制的那一类”排好。然后把受到“不相邻”限制的元素插入空隙。十二、为什么“不能相邻”适合插空因为如果_ A _ B _ C _每个元素都放到不同的空里X A Y B C或者A X B C Y女生自然不会相邻。所以插空法的本质就是用“空隙”主动制造“不相邻”。十三、捆绑法和插空法的对比这是本课最重要的比较。条件常用方法思路必须相邻捆绑法把它们绑起来必须连续捆绑法看成一个整体不能相邻插空法插进不同空隙至少相邻一次常结合分类/补集分情况可以给大家一句非常形象的话相邻就“绑起来”不相邻就“插开来”。十四、再看一道“特殊位置”问题例题45个人A B C D E站成一排。要求A必须站在最左边。有多少种排法A的位置已经确定A _ _ _ _所以剩下4个人随便排列4!答案24十五、为什么不是5!因为A已经不能选择位置了。普通情况下5!表示5个人都可以自由选择位置。但现在A → 第1个位置已经固定。所以只剩4!十六、特殊位置的核心思想遇到某个人必须在第一个位置就固定他 ↓ 剩下的人自由排列遇到某个人必须在最后一个位置同样固定他 ↓ 剩下的人自由排列十七、如果A必须站在中间呢5个人_ _ _ _ _中间位置是第3个_ _ A _ _A已经固定。剩下4!所以24十八、两个特殊位置同时固定6个人A B C D E F要求A站最左边B站最右边。那么A _ _ _ _ B中间还有4个人。所以4!答案24十九、特殊位置的另一种情况必须在某几个位置之一例如5个人排队A必须站在第1个或第5个位置。A有2种位置选择。剩下4个人4!所以这里又回到了上一课分类 分步A的位置第1个 或者 第5个是分类。所以2种。确定位置以后再排列剩下的人。所以2 × 4!二十、一个非常重要的初赛思维排列组合题不要一看到“必须”就套捆绑法。例如A必须站在第1位。这是固定位置。不是捆绑。例如A、B必须相邻。这是捆绑法。例如A、B不能相邻。这是插空法或者补集法。二十一、“至少”怎么办这也是CSP-J初赛非常喜欢考的地方。例如5个人排队要求A、B至少有一个条件满足……看到至少不要马上计算。首先想到总数−不满足的情况这就是补集思想这一部分我们会在后面的课程中重点讲。今天先让大家认识“至少”经常可以从反面考虑。二十二、综合题捆绑 特殊位置例题56个人A B C D E F排成一排。要求A、B必须相邻而且A必须在B的左边。有多少种首先AB必须相邻。所以可以把[A B]看成一个整体。再加C D E F一共5个整体。所以5!但是注意A必须在B左边。所以内部不再有BA这种情况。因此内部只有AB一种。所以答案5!120二十三、这里有一个非常容易错的地方如果题目只说A、B必须相邻。答案5! × 2!因为AB BA都可以。但是如果说A、B必须相邻而且A必须在B左边。那么AB唯一。所以是5!二十四、再看一个插空综合题4个男生A B C D3个女生X Y Z排成一排要求女生之间不能相邻。先排男生4!男生形成_ A _ B _ C _ D _共有5个空。3个女生必须占不同的空。选择3个空女生内部排列3!所以二十五、同学们一定要理解“为什么先排男生”有人可能会问为什么不先排女生当然也可以尝试但女生数量少时先排男生会自然产生5个空然后把女生插进去。因此有一个经验遇到“某一类元素不能相邻”通常先把另一类排好再利用空隙。尤其当被限制的元素数量比较少时插空法非常漂亮。二十六、捆绑法 VS 插空法我们用两个动画来理解。必须相邻A B ↓ [AB]叫捆绑不能相邻A B C ↓ _ A _ B _ C _把其他元素之间制造出空隙X A Y B Z C叫插空二十七、把本课内容整理成一张表题目条件思考方法A、B必须相邻捆绑A、B、C必须连续捆绑A、B不能相邻插空 / 补集A必须第一位固定位置A必须最后一位固定位置A必须在中间固定位置A只能在第1或第5位分类A、B相邻且A在B左边捆绑但内部只有1种至少满足一个条件常考虑补集至多……常分类或补集二十八、CSP-J初赛的“解题流程”以后遇到排列组合题建议大家按照这个顺序想排列组合题 ↓ ┌────────┴────────┐ ↓ ↓ 有没有限制 没有限制 ↓ ↓ 有 直接算 ↓ ┌─────┼─────┬─────┐ ↓ ↓ ↓ ↓ 相邻 不相邻 固定 至少/至多 ↓ ↓ ↓ ↓ 捆绑 插空 定位 分类/补集二十九、特别提醒不要死背公式例如看到5个人A、B相邻。不要第一反应4!×2!而应该问为什么因为A B C D E被我们转换成[AB] C D E这是4个整体。所以4!然后[AB]内部AB BA有2!所以是4! × 2!这样即使数字换成8个人3个人必须相邻你也能自己推出来。这才是我们最希望达到的状态不是背答案而是学会把复杂问题“变简单”。三十、本课必背口诀最后大家请记住 排列组合三大魔法必须相邻怎么办捆起来不能相邻怎么办插开来位置已经规定怎么办先固定相邻 → 捆绑不相邻 → 插空固定位置 → 定位“或者” → 加法“然后” → 乘法三十一、课后练习题16个人排成一排A、B必须相邻。问使用什么方法答案捆绑法题25个男生、3个女生排成一排要求3个女生必须连续。问使用什么方法答案捆绑法题34个男生、2个女生排成一排要求两个女生不能相邻。问使用什么方法答案插空法题47个人排队A必须站在最左边。问使用什么方法答案固定位置。题57个人排队A只能站在第1位或第7位。问使用什么思想答案分类 分步。题68个人排队A、B相邻而且A必须在B左边。问和“AB相邻”相比有什么区别答案“AB相邻”时内部有AB、BA两种“AB相邻且A在B左边”时内部只有AB一种。本课的知识网络把这两课连起来大家脑中应该形成这样一张知识网络图排列组合 │ ┌───────────┴───────────┐ ↓ ↓ 基础计数 特殊限制 │ │ ┌────┴────┐ ┌───────┼────────┐ ↓ ↓ ↓ ↓ ↓ 分类 分步 相邻 不相邻 固定位置 ↓ ↓ ↓ ↓ ↓ 加法 乘法 捆绑 插空 定位上一课解决“怎么算”这一课开始解决“有条件怎么算”。下一步再进入 “ 至少、至多、排除法、补集思想 ”排列组合就真正进入CSP-J初赛的综合题阶段了。