1. 为什么排列组合是很多人的第一道坎排列组合这个东西说起来大家都学过高中课本里就那几页纸公式背下来好像也不难。但真正做题的时候很多人会发现一个尴尬的情况公式明明记得题目一变形就不知道从哪下手了。更让人头疼的是有时候自己算出来的答案和标准答案差一点点检查半天也找不出哪里错了。我当年第一次系统接触排列组合的时候最大的感受就是——这玩意儿不像方程题那样有固定的套路可以套。方程题你按照步骤一步步来基本不会出大错。但排列组合不一样同一道题换个角度理解可能就变成了完全不同的模型用错了模型答案自然就偏了。后来我慢慢琢磨明白了一件事排列组合的核心难点其实不在计算而在分类和判断。你得先搞清楚题目到底在问什么是排列还是组合是有序还是无序能不能重复有没有限制条件。这些判断做对了剩下的就是套公式算数反而简单了。这篇文章我打算把排列组合的基础从头到尾捋一遍不讲那些花里胡哨的难题偏题就讲最核心的概念、最容易混淆的地方、以及我自己踩过的那些坑。不管你是正在学这部分内容的学生还是工作中偶尔需要用到排列组合的从业者应该都能从中找到有用的东西。排列组合的本质是计数。计数的核心原则只有两条加法原理和乘法原理。所有复杂的排列组合问题最终都可以拆解成这两条原则的组合应用。2. 加法原理和乘法原理一切计数的根基2.1 加法原理到底在说什么加法原理用一句话概括就是做一件事有若干类互不重叠的方法总方法数等于各类方法数之和。举个例子。你从A城市到B城市可以坐火车也可以坐飞机也可以自己开车。火车每天有5趟飞机每天有3趟自驾路线有2条。那么从A到B总共有多少种走法答案是53210种。这就是加法原理因为这三类方式是互斥的——你不可能同时坐火车又坐飞机这里说的是选择一种交通方式不是换乘。加法原理的关键在于分类不重不漏。什么叫不重就是每一类方法之间不能有交叉。什么叫不漏就是所有可能的情况都要覆盖到。这两点说起来简单做起来特别容易出错。我见过一个很典型的错误案例从一副扑克牌中抽一张牌问抽到红桃或者K有多少种可能。有人直接算13417但这是错的。因为红桃K被算了两次——它既是红桃又是K。正确答案应该是134-116。这就是典型的“重”了。2.2 乘法原理为什么是“分步相乘”乘法原理的表述是做一件事需要分成若干个步骤每一步有若干种方法总方法数等于各步方法数的乘积。比如你搭配衣服上衣有4件可选裤子有3条可选鞋子有2双可选。那么总的搭配方案就是4×3×224种。因为你是先选上衣再选裤子再选鞋子每一步的选择是独立的所以用乘法。乘法原理的关键在于分步完整。什么叫完整就是你分的这些步骤做完之后这件事就真的做完了不需要再补额外的步骤。而且每一步的选择数量不受前面步骤的影响或者说即使受影响你也要把受影响后的数量算清楚。这里有个容易犯的错误分步的时候漏掉了某些步骤或者步骤之间不独立却直接相乘。比如从5个人里选3个人排成一排有人直接算5×4×360这其实是对的因为选第一个位置有5种第二个位置有4种第三个位置有3种。但如果题目改成从5个人里选3个人组成一个小组不排序那就不能用5×4×3了因为这样会把同一组人的不同排列当成不同结果。2.3 两个原理的配合使用实际题目中加法原理和乘法原理往往是配合使用的。大框架上用加法原理分类每一类内部用乘法原理分步计算。举个稍微复杂点的例子。从甲地到乙地有3条路从乙地到丙地有4条路。问从甲地到丙地有多少种走法如果必须经过乙地那就是3×412种。但如果还有一条从甲地直接到丙地的路那就是3×4113种。这里就是先分类经过乙地和不经过乙地再在每一类里分步计算。实操心得做排列组合题的时候先问自己三个问题——这件事能不能分类分类之后每一类能不能分步分步之后每一步有多少种选择把这三个问题回答清楚大部分基础题都能解决。3. 排列与组合的分水岭顺序到底重不重要3.1 排列的核心特征排列的核心特征是有序。也就是说同样的几个元素顺序不同就算不同的结果。最经典的例子就是排队。3个人排成一排有多少种排法第一个人有3种选择第二个人有2种选择第三个人只有1种选择所以是3×2×16种。这就是排列因为“甲乙丙”和“乙甲丙”是两种不同的排法。排列数的公式是[ A_n^m \frac{n!}{(n-m)!} ]其中n是总元素个数m是取出的元素个数。这个公式的意思是从n个元素中取m个出来排列第一个位置有n种选择第二个位置有n-1种选择一直到第m个位置有n-m1种选择乘起来就是n×(n-1)×...×(n-m1)也就是n!/(n-m)!。3.2 组合的核心特征组合的核心特征是无序。也就是说只要选出来的元素集合相同不管顺序如何都算同一种结果。比如从5个人里选3个人组成一个小组这就是组合问题。因为小组里的人是“甲乙丙”还是“丙乙甲”没有区别都是同一组人。组合数的公式是[ C_n^m \frac{n!}{m!(n-m)!} ]这个公式是怎么来的其实很简单。先按排列算从n个里取m个排列有A_n^m种。但每一种组合都被重复算了m!次因为m个元素有m!种排列方式。所以组合数就是排列数除以m!。3.3 怎么快速判断用排列还是组合判断标准其实就一句话交换两个元素的位置结果是否改变如果改变就是排列如果不改变就是组合。我总结了一个更实用的判断方法看题目里有没有“顺序”“排队”“排列”“依次”这类词如果有大概率是排列如果题目说的是“选出”“挑选”“组成一个集合”“分组”这类词大概率是组合。但也不能完全靠关键词有些题目表述很隐晦。比如“从5个人里选3个人分别担任班长、副班长、学习委员”虽然说的是“选”但因为有具体的职位区分所以是排列。而“从5个人里选3个人参加比赛”没有职位区分就是组合。对比维度排列组合顺序是否重要重要不重要典型关键词排队、排列、依次、分别担任选出、挑选、分组、组成公式A(n,m) n!/(n-m)!C(n,m) n!/[m!(n-m)!]示例5人选3人排成一排5人选3人组成小组结果差异同一组人的不同顺序算不同结果同一组人只算一种结果注意排列和组合最容易混淆的地方就是“选出来之后要不要排序”。我的经验是读完题目之后自己脑子里模拟一下——如果我把选出来的两个人换个位置题目描述的场景会变吗会变就是排列不会变就是组合。4. 那些年我踩过的排列组合坑4.1 重复计数的坑重复计数是排列组合里最常见的错误没有之一。很多时候你算出来的答案比正确答案大大概率就是重复计数了。我印象最深的一次是算“从6个人里选4个人围成一圈”的问题。我当时的思路是先选4个人然后把这4个人排成一圈。选4个人是C(6,4)15种4个人围成一圈是(4-1)!6种所以总共是15×690种。这个答案是对的但当时我花了很长时间才理解为什么围成一圈是(4-1)!而不是4!。原因在于围成一圈的时候没有固定的起点。你把一圈人整体旋转一下还是同一圈人。所以4个人围成一圈实际上只有(4-1)!3!6种不同的排列方式。这就是典型的“重复计数”——如果你按4!24算就把同一圈人的不同旋转当成了不同结果。类似的坑还有很多。比如“从10个人里选5个人分成两组每组5人”有人直接算C(10,5)×C(5,5)252但这是错的因为两组是无区别的你先把A组选出来和先把B组选出来是一样的。正确答案应该是C(10,5)/2126。4.2 分类不完整的坑分类不完整是另一个高频错误。你觉得自己把所有情况都考虑到了但实际上漏掉了某些特殊情况。比如“从1到100中选两个数使它们的和是偶数”有人只考虑了“两个偶数”的情况忘了“两个奇数”的情况。正确答案应该是C(50,2)C(50,2)2450。再比如“从5男4女中选3人要求至少有1女”有人只算了“1女2男”的情况忘了“2女1男”和“3女0男”的情况。正确的做法是分类计算C(4,1)×C(5,2)C(4,2)×C(5,1)C(4,3)4030474。或者用补集思想总数C(9,3)84减去全是男生的C(5,3)10得到74。4.3 混淆“至少”和“恰好”的坑“至少”和“恰好”是两个完全不同的概念但很多人在做题的时候会不自觉地混淆。“恰好有1个”就是只有1个不多不少。“至少有1个”是1个、2个、3个……都要算进去。我见过太多人把“至少”当成“恰好”来算结果答案差了一大截。处理“至少”问题有两种常用方法。一种是直接分类把所有满足条件的情况都加起来。另一种是用补集思想用总数减去不满足条件的情况。哪种方法更简单取决于具体题目。一般来说如果“至少”的反面情况比较少用补集思想会更方便。4.4 特殊元素和特殊位置的坑有些题目里会有特殊元素或特殊位置比如“甲不能站在排头”“红球不能放在第一个盒子”之类的。这种题目如果直接按常规方法算很容易出错。处理这类问题的基本原则是优先安排特殊元素或特殊位置。比如“5个人排队甲不能站排头”那就先安排甲甲有4个位置可选不能站排头然后剩下4个人全排列所以是4×4!96种。如果特殊条件比较多可能需要分类讨论。比如“甲不能站排头乙不能站排尾”那就得分情况甲站排尾和甲不站排尾两种情况分别计算最后加起来。实操心得遇到带限制条件的排列组合题先不要急着算先把限制条件列出来看看哪些是“不能”哪些是“必须”。然后按照“先特殊后一般”的顺序来安排。如果限制条件之间有交叉就用分类讨论或者容斥原理来处理。5. 分组分配问题排列组合里的重灾区5.1 均匀分组与非均匀分组的区别分组问题是排列组合里最容易出错的一类没有之一。核心难点在于均匀分组要除以组数的阶乘非均匀分组不用除。什么叫均匀分组就是每组的人数相同。比如6个人分成3组每组2人这就是均匀分组。什么叫非均匀分组就是每组的人数不完全相同。比如6个人分成3组人数分别是1、2、3这就是非均匀分组。为什么均匀分组要除以组数的阶乘因为当每组人数相同时组与组之间是没有区别的。你先把A、B选出来再把C、D选出来再把E、F选出来和先把C、D选出来再把A、B选出来再把E、F选出来其实是一样的分组结果。所以要把重复计算的次数除掉。具体来说6人分成3组每组2人正确的计算是[ \frac{C_6^2 \times C_4^2 \times C_2^2}{3!} \frac{15 \times 6 \times 1}{6} 15 ]如果忘了除以3!就会得到90比正确答案大了6倍。5.2 分组后分配的问题分组和分配往往是连在一起的。比如“6个人分成3组每组2人然后分配到3个不同的岗位”这时候分组之后还要乘以3!因为3个岗位是不同的。所以完整的计算是[ \frac{C_6^2 \times C_4^2 \times C_2^2}{3!} \times 3! 15 \times 6 90 ]你会发现除以3!又乘以3!其实抵消了。所以如果分组之后要分配到不同的对象均匀分组的除法就不用做了。但如果是分组之后不分配或者分配到相同的对象那就必须除以组数的阶乘。这个逻辑我当初理解了很久才转过弯来。后来我总结了一个简单的判断方法看分组之后有没有“标签”。如果分出来的组有名字比如甲组、乙组、丙组那就是分配问题不用除如果分出来的组没有名字就是纯分组问题均匀分组要除。5.3 隔板法解决相同元素分配问题的利器隔板法是解决“把n个相同的元素分给m个不同的对象每个对象至少分到1个”这类问题的经典方法。方法很简单把n个元素排成一排它们之间有n-1个空隙。在这些空隙中插入m-1个隔板就把元素分成了m份。所以方法数是C(n-1, m-1)。比如“把10个相同的苹果分给3个小朋友每人至少1个”就是在9个空隙里插2个隔板答案是C(9,2)36。如果题目改成“每人至少0个”也就是可以有人分不到那就先借3个苹果每人先分1个变成13个苹果分给3人每人至少1个答案是C(12,2)66。这就是隔板法的变形。隔板法的适用条件很严格元素必须相同对象必须不同每个对象至少分到1个或者可以通过变形转化为至少1个。如果元素不同就不能用隔板法得用分组分配的方法。问题类型方法公式适用条件相同元素分给不同对象每人至少1个隔板法C(n-1, m-1)元素相同对象不同相同元素分给不同对象允许有人0个隔板法变形C(nm-1, m-1)先借后还不同元素均匀分组分组除法C(n,m)×C(n-m,m)×.../k!每组人数相同不同元素非均匀分组直接分步C(n,m1)×C(n-m1,m2)×...每组人数不同注意隔板法只能用于相同元素的分配。如果元素是不同的比如“把10本不同的书分给3个人”那就不能用隔板法得用乘法原理一步步分。6. 容斥原理处理“至少”和“至多”的万能工具6.1 容斥原理的基本思想容斥原理的核心思想是先加后减把重复算的减掉把多减的加回来。两个集合的容斥原理公式是[ |A \cup B| |A| |B| - |A \cap B| ]三个集合的公式是[ |A \cup B \cup C| |A| |B| |C| - |A \cap B| - |A \cap C| - |B \cap C| |A \cap B \cap C| ]这个公式看起来复杂但逻辑很清晰先把所有单个集合的大小加起来然后减去两两交集的大小因为被多算了一次最后加回三个集合的交集因为被多减了一次。6.2 容斥原理在排列组合中的应用容斥原理在排列组合里主要用来处理“至少”“至多”“不能”“必须”这类限制条件。比如“从1到100中选一个数它不能被2、3、5中任何一个整除”这就是典型的容斥原理问题。设A是被2整除的数B是被3整除的数C是被5整除的数。要求的是既不在A里也不在B里也不在C里的数。先算总数100然后减去|A||B||C|加上两两交集减去三三交集。具体计算|A|50|B|33|C|20|A∩B|16被6整除|A∩C|10被10整除|B∩C|6被15整除|A∩B∩C|3被30整除所以不能被2、3、5整除的数有[ 100 - (503320) (16106) - 3 100 - 103 32 - 3 26 ]6.3 错排问题容斥原理的经典应用错排问题是容斥原理最经典的应用之一。问题描述是n个元素排成一排每个元素都不在自己原来的位置上有多少种排法错排问题的公式是[ D_n n! \left(1 - \frac{1}{1!} \frac{1}{2!} - \frac{1}{3!} ... (-1)^n \frac{1}{n!}\right) ]这个公式看起来吓人但其实用容斥原理推导很自然。设A_i表示第i个元素在自己位置上的情况。要求的是所有A_i都不发生的情况数。用总数n!减去至少一个A_i发生的情况加上至少两个A_i同时发生的情况以此类推。错排问题的前几个值值得记住D_10D_21D_32D_49D_544。考试的时候如果遇到n比较小的错排问题直接套这些值比现推公式快得多。实操心得容斥原理的难点不在公式本身而在“怎么把题目条件转化成集合”。我的经验是先把所有限制条件列出来每个限制条件对应一个集合然后看题目要求的是“都不满足”还是“至少满足一个”。如果是“都不满足”就用总数减去至少满足一个的情况如果是“至少满足一个”就直接用容斥公式。7. 排列组合的实战解题框架7.1 读题阶段提取关键信息拿到一道排列组合题不要急着算。先花30秒把题目读两遍提取以下关键信息总共有多少个元素要选出多少个元素选出来的元素要不要排序有没有特殊元素或特殊位置有没有“至少”“至多”“不能”这类限制条件元素是相同的还是不同的分组之后要不要分配把这些信息列清楚题目的模型基本就确定了。7.2 建模阶段选择合适的模型根据提取的信息判断题目属于哪种模型纯排列问题直接套排列公式纯组合问题直接套组合公式分组问题判断是均匀分组还是非均匀分组分配问题判断是相同元素分配还是不同元素分配带限制条件的问题考虑用容斥原理或分类讨论错排问题直接套错排公式7.3 计算阶段注意细节计算的时候有几个容易出错的地方阶乘的计算要仔细尤其是大数的阶乘组合数的计算可以用对称性简化C(n,m)C(n,n-m)分类讨论的时候要确保不重不漏均匀分组记得除以组数的阶乘7.4 验证阶段用不同方法交叉验证如果时间允许算完之后可以用另一种方法验证一下。比如用补集思想算一遍看看结果是否一致。或者把n改小一点手动枚举所有情况看看公式算出来的结果对不对。我自己的习惯是对于n比较小比如n≤5的题目直接手动枚举验证。虽然费点时间但能有效避免低级错误。注意排列组合题最忌讳的就是“想当然”。你觉得自己的思路没问题但很可能漏掉了某种情况。所以算完之后一定要回头检查一遍看看有没有遗漏或重复。8. 从入门到熟练的练习路径8.1 基础阶段把公式用熟刚开始学排列组合的时候不要急着做难题。先把最基本的公式用熟做到看到题目就能条件反射地写出公式。这个阶段建议做以下练习纯排列题n个人排队、n个数字组成几位数纯组合题从n个里选m个、从n个里选m个组成小组简单的分组分配题n个人分成几组、n个物品分给几个人简单的限制条件题某人不能站某位置、某物不能放某处这个阶段的目标是看到题目能在30秒内判断出用排列还是组合并写出正确的公式。8.2 进阶阶段掌握分类讨论和容斥原理基础打牢之后开始接触带限制条件的题目。这个阶段的核心是学会分类讨论和容斥原理。分类讨论的关键是找到合适的分类标准。比如按特殊元素的位置分类按是否满足某个条件分类按元素的类型分类。分类的标准不同计算的复杂度可能差很多。多试几种分类方式找到最简洁的那种。容斥原理的关键是正确识别集合。把每个限制条件对应成一个集合然后判断题目要求的是“都不满足”还是“至少满足一个”。8.3 熟练阶段形成条件反射到了这个阶段你应该能做到看到题目就知道它属于哪种模型知道用哪种方法最简洁知道哪里容易出错。这个阶段建议做一些综合题把排列、组合、分组、分配、容斥原理混合在一起。比如“从n个人里选m个人分成k组其中甲必须入选乙不能入选然后分配到不同的岗位”。这种题目需要你把多个知识点串联起来。我自己的经验是排列组合的熟练度不是靠“看懂”得来的而是靠“做错”得来的。每做错一道题就分析一下错在哪里——是分类不完整还是重复计数还是模型判断错了。把这些错误记下来下次遇到类似题目的时候提醒自己。8.4 常见错误清单最后列一个我总结的常见错误清单做题的时候可以对照检查把组合当排列算忘了除以m!把排列当组合算忘了乘以m!均匀分组忘了除以组数的阶乘分类讨论漏掉了某些情况容斥原理的符号搞反了隔板法用在了不同元素上“至少”和“恰好”混淆特殊元素没有优先安排重复计数没有发现这个清单里的每一条我都至少踩过一次坑。希望你能避开这些坑少走一些弯路。排列组合这个东西入门的时候确实有点绕但一旦你把基本概念理清楚了把常见模型练熟了后面就会越来越顺。关键是不要怕犯错每错一次就离掌握更近一步。
