。第四十一课排列组合解题技巧①——分类、分步与“到底该加还是该乘”适合对象初学 C 的小学生 / CSP-J 初赛复习本课核心分类计数原理分步计数原理“加法还是乘法”的判断可重排列排列组合综合判断相邻问题——整体捆绑法一、今天先不学公式玩一个“选路线”游戏小明周末要去游乐场。从家到游乐场有两种方案方案A坐公交车 方案B坐地铁公交车有3条不同路线公交1 公交2 公交3地铁有2条不同路线地铁1 地铁2问小明一共有多少种不同的走法很明显325为什么是加法因为小明要么坐公交要么坐地铁。两个方案之间是“或者”的关系。二、这就是分类计数原理如果完成一件事情有第一类方法m₁种 第二类方法m₂种 …… 第k类方法mₖ种并且这些方法是互相独立、互不重复的不同类别那么总方法数m1m2⋯mk这就是分类计数原理三、小学生最好记的关键词看到或者就要想到加法例如去学校可以坐公交车也可以骑自行车。如果公交车有4种走法自行车有2种走法那么426种。四、但是如果是“然后”呢现在换一道题。小明去游乐场需要完成两个步骤第一步选择交通工具 第二步选择路线假设有2种交通工具每种交通工具都有3条路线那么交通工具1 路线1 路线2 路线3 交通工具2 路线1 路线2 路线3一共有2×3 6种。为什么是乘法因为第一步完成以后还必须继续完成第二步。这是分步计数原理五、分步计数原理如果完成一件事情需要经过第1步m₁种方法 第2步m₂种方法 …… 第k步mₖ种方法那么总方法数m1 × m2 × ⋯ × mk六、最重要的区别加还是乘这是今天最重要的内容。情况一分类方法A 或 方法B 或 方法C关键词或者所以加法情况二分步第一步 ↓ 第二步 ↓ 第三步关键词并且、然后、接着所以乘法七、一个超级简单的判断口诀分类用加法分步用乘法。“或者”用加“然后”用乘。提醒不能只看某一个字要看整个题目的逻辑。八、经典题密码问题现在我们来玩密码锁。一个密码由1个数字 1个字母组成。数字09一共有10种。字母假设有AZ一共有26种。那么密码有多少种第一步选数字10种。第二步选字母26种。因为两个步骤都必须完成10 × 26所以260九、为什么不能1026因为数字和字母不是“二选一”。而是先选一个数字 还要选一个字母所以10×26十、再来一个“加法陷阱”一个密码可以是4位数字密码也可以是3位字母密码。4位数字密码10^43位字母密码26^3因为两种情况是数字密码 或者 字母密码所以这时候就是加法。十一、初学者容易犯的错误看到两个数字10, 26就不知道应该是1026还是10×26不要看数字。要看这两个选择之间是什么关系十二、画树状图就不会错比如2种饮料3种蛋糕选一种饮料和一种蛋糕。饮料 / \ 可乐 果汁 / | \ / | \ 蛋1 蛋2 蛋3 蛋1 蛋2 蛋3最终2 × 3 6如果是可以选择3种水果中的一种或者选择2种蛋糕中的一种。那么水果 ├── 苹果 ├── 香蕉 └── 橙子 或者 蛋糕 ├── 蛋糕1 └── 蛋糕2所以3 2 5十三、第三个重要知识可重排列现在有3个数字1 2 3我们要制作一个2位密码。而且数字可以重复。例如11 12 13 21 22 23 31 32 33一共有9种。为什么第一位3种。第二位3种。所以3 × 3 9也就是十四、为什么叫“可重排列”因为11 22 33这些都允许出现。也就是选过以后还可以继续选。所以每一个位置都有m种选择。一共有n个位置。因此我们可以明确给出这一结论从m个不同元素中取出n个允许重复并考虑顺序时方法数为 m^n。十五、可重排列与普通排列的区别这个地方特别重要。例如3个数字1、2、3组成2位数不能重复。第一位3种。第二位只剩2种。所以3×2 6如果允许重复第一位3第二位仍然3所以3 × 3 9于是条件方法数不能重复3×26可以重复3×39记忆能重复每一位选择数不变。不能重复选走一个选择数就少一个。十六、进入今天的第一个真正的排列组合技巧相邻问题——整体捆绑法题目7名学生站成一排甲、乙必须站在一起有多少种排法先不要直接算。看看甲 乙必须相邻所以我们可以把甲乙看成一个整体[甲乙]于是原来7个人甲 乙 丙 丁 戊 己 庚变成[甲乙] 丙 丁 戊 己 庚一共变成6个“元素”。十七、6个元素怎么排列有6!种。但是[甲乙]内部还有两种情况甲乙 乙甲所以还要2!种。根据乘法原理6!×2所以720 × 2 1440答案1440我们可以明确像是本题这样采用了“把甲乙看作一个整体再乘上内部排列”的方法就叫做捆绑方法。十八、为什么叫“捆绑法”因为我们真的可以想象成甲 乙把他们“绑”在一起。原来甲 乙 丙 丁 戊 己 庚变成[甲乙] 丙 丁 戊 己 庚先安排大整体的位置再安排整体内部的人怎么排所以本质是外部×内部也就是分步计数原理。十九、再看一道捆绑题5个男生和3个女生排成一排要求3个女生必须站在一起有多少种排法把三个女生捆起来[女生女生女生]现在5个男生 1个女生整体一共6个整体。先排这6个整体6!然后3个女生内部排列3!所以6! × 3! 720×6 4320这就是一道经典的捆绑法的例题。二十、捆绑法的核心模板以后看到某几个元素必须相邻立刻想到① 捆起来 ② 把整体进行排列 ③ 再考虑内部排列 ④ 两者相乘即外部排列×内部排列二十一、一个很容易掉进去的坑例如甲、乙必须相邻。有的同学只写了6!错在哪里因为[甲乙]内部还有甲乙 乙甲两种。所以应该6! × 2!二十二、今天真正要掌握的“解题四连问”以后看到排列组合题不要马上套公式。先问自己第一问这是分类还是分步或者 → 分类 → 加 然后 → 分步 → 乘第二问顺序重要吗如果重要排列排列如果不重要组合组合第三问能不能重复如果能每一步选择数可能保持不变如果不能选择一个后后面的选择数减少第四问有没有特殊限制比如必须相邻 不能相邻 必须在一起 不能在一起 至少…… 至多……这些通常需要特殊技巧。二十三、把今天所有知识串起来排列组合 │ ┌────────┴────────┐ ↓ ↓ 分类 分步 │ │ “或者” “然后” │ │ 加法 乘法 │ ┌───────┴───────┐ ↓ ↓ 能重复 不能重复 ↓ ↓ m^n 选择数递减 │ ↓ 排列/组合 │ 特殊限制 ↓ 捆绑法……二十四、CSP-J 初赛特别容易出现的题型类型1菜单选择有4种主食3种饮料选择一份主食和一份饮料。4×3 12类型2交通路线去学校公交车5条路线地铁3条路线二选一。5 3 8类型3密码4位数字密码允许重复。10^4类型4密码不能重复4位数字密码不能重复。10 × 9 × 8 × 7类型5必须相邻甲乙必须相邻[甲乙]先整体再内部。二十五、课堂综合例题例题某商店有3种帽子 4种衣服 2种鞋子小明要选择一顶帽子、一件衣服、一双鞋子。问有多少种搭配分析必须完成三个步骤选帽子 ↓ 选衣服 ↓ 选鞋子每一步都必须完成。所以3 × 4 × 2 24二十六、再变化一下如果商店规定可以选择一顶帽子或者选择一双鞋子。那么32 5为什么因为是帽子 或者 鞋子这是分类。二十七、再变化一下如果要求选择一顶帽子和一件衣服或者选择一双鞋子。那么第一类3 × 4 12第二类2两类之间是“或者”12 2 14所以14这就是加法和乘法混合使用。二十八、初赛中的“反粗心训练”要求学生每道排列组合题都在草稿纸上先写这是 □ 分类 □ 分步 关键词 □ 或者 □ 然后 □ 并且 顺序 □ 有序 □ 无序 重复 □ 可以 □ 不可以 特殊条件 □ 相邻 □ 不相邻 □ 至少 □ 至多然后再计算。这比单纯要求孩子“细心一点”有效得多。二十九、今天的必背知识① 分类计数原理总数 各类相加② 分步计数原理总数 各步相乘③ 可重排列④ 普通排列⑤ 组合⑥ 相邻捆绑整体排列×内部排列三十、给大家的“本课魔法口诀”排列组合四大魔法第一招分类——或者就相加。第二招分步——然后就相乘。第三招排列——顺序不能忘。第四招组合——只选不排序。遇到相邻怎么办把它们捆起来先排整体再排内部最后相乘。三十一、课后小测1.3种饮料4种甜点选择一种饮料和一种甜点有多少种2.从A、B、C、D四个字母中选择一个作为密码第一位有多少种3.用1、2、3、4组成一个3位密码允许重复有多少种4.用1、2、3、4组成一个3位数不允许重复有多少种5.5个人排队甲乙必须相邻有多少种排法6.6个人排队甲乙丙三人必须站在一起有多少种排法参考答案第1题3×412第2题4第3题4^364第4题4 × 3 × 2 24第5题把甲乙捆起来4! × 2! 48第6题把甲乙丙捆起来[甲乙丙] 其他3人一共4个整体4!内部3!所以4! × 3! 24 × 6 144本课与后续课程的衔接本课先把孩子最容易混乱的“加法还是乘法”彻底解决然后把它与排列组合连接起来。这样后面讲第41课排列组合解题技巧②——捆绑法、插空法与特殊位置第42课排列组合解题技巧③——至少、至多、排除法