计数问题的常用方法

分类加法原理: 完成一件事有几类互不相同的办法,每一类都能独立完成这件事,总数就是各类数目相加。关键词:「或」「分几种情况」。

分步乘法原理: 完成一件事需要连续几个步骤,每一步都不能单独完成,必须步步都做,总数就是各步数目相乘。关键词:「先…再…」「接着」。

⚠ 判断标准:一类里的任一种办法能否「独立把事办成」?能→分类(加);不能、必须接着做下一步→分步(乘)。混用加法乘法是失分头号原因。

触发词:「相邻」「必须挨在一起」「连在一块」。 做法两步:① 把必须相邻的 k 个元素捆成一个「大元素」,和其余元素一起做全排列;② 捆内部的 k 个元素自己也要排序(A(k,k)=k!)。两步相乘。

⚠ 最大陷阱:忘了捆内部还要排序!甲乙相邻有「甲乙」「乙丙」两种朝向,漏乘 A(2,2) 直接少一半。捆几个就乘 A(k,k)。

触发词:「不相邻」「互不相邻」「都不挨着」。 做法两步:① 先把没有相邻限制的 n 个元素全排,形成 n+1 个空(含两端);② 把要求不相邻的 k 个元素插进这些空里,一空至多一个,用排列 A(n+1, k)。

⚠ 空位数是n+1(含两端),别只数中间的 n−1 个!要「不相邻」就先排别人再插空;千万别拿要不相邻的那批去打头阵。

触发词:「相同的」「名额分配」「每人至少一个」「正整数解个数」。 想象 n 个完全相同的球排成一排,球与球之间有 n−1 个缝隙;要分给 m 个人,只需在缝里插 m−1 块隔板,隔板把球分成 m 段,每段给一个人。从 n−1 个缝里选 m−1 个放隔板 → C(n−1, m−1)。

变式(可以分到 0 个): 「每人至少 0 个」即允许空。技巧是先给每人「借」1 个凑成「至少 1 个」模型:n 个分给 m 人可为 0 → 变成 (n+m) 个分给 m 人每人至少 1 → C(n+m−1, m−1)。

⚠ 隔板法只对相同(不可区分)元素有效!球要是不同的就不能用。且标准型必须「每份至少 1 个」,能为 0 的先做「加人头」转化。

触发词:「至少」「至多」「不…」「不都…」。 当「正面直接数要分很多类、很容易漏」时,反过来算反面(反面通常只有一两类),用总数减掉它。尤其「至少」型——正面要分「1个、2个、3个…」很碎,反面「一个都没有」往往只有一种。

⚠ 「至少/至多」优先想间接法。但要确认「反面」互斥且好数;若反面也很碎(比如「至少 2」的反面是「0 或 1」两类),就得把反面各类都减掉。

触发词:「分成几组」「分配给几个人/地方」。 关键分清两件事:「分组」是否有序(分给不同的人=有序,单纯分成几堆=无序),以及各组是否等大。

为什么平均分组要除 k!? 因为组与组之间没有编号、无法区分,同一种分法被你的「先取哪组」重复数了 k! 次,必须除掉。有几组人数相同就除以那几组的阶乘。

⚠ 平均分组÷ 组数阶乘;若「分给不同的人」是有序的,分完组还要再×A(组数,组数)把组安到人头上(或直接不除)。部分均匀就只除均匀那部分的阶乘。

触发词:「某元素不能在某位置」「首位不能是0」「甲必须(不)在某处」。 遇到带限制的元素或位置,先安排受限的那个,再排其余。这样避免限制在最后引发大面积重算。

另一路(元素优先): 也可先看特殊元素 0——0 不能进百位,只能进十位或个位(2 个位置),再排其余,结果一致。

⚠ 数字排列的头号坑:首位不为 0。要么位置优先(先定首位),要么元素优先(先安置 0),别用普通全排 A 直接算。

题型A — 相邻问题(捆绑法)

触发信号:「必须相邻」「挨在一起」「连成一片」。

标准动作:把相邻的 k 个捆成一个整体与其余全排 A(总,总),再乘捆内部排列 A(k,k)。

示例(带解):4 名男生 3 名女生排一排,3 名女生必须相邻。女生捆成 1 个整体,与 4 男共 5 个元素全排 A(5,5)=120;女生内部 A(3,3)=6。总数 120×6=720。

陷阱:忘记捆内部还要排序(漏乘 A(k,k));多组相邻要每组各乘一次内部排列。

题型B — 不相邻问题(插空法)

触发信号:「互不相邻」「都不挨着」「彼此分开」。

标准动作:先排无约束的 n 个 A(n,n) → 形成 n+1 个空 → 把不相邻的 k 个插空 A(n+1,k)。

示例(带解):5 人排队,甲、乙、丙互不相邻。先排另外 2 人 A(2,2)=2,产生 3 个空;甲乙丙插进 3 个空 A(3,3)=6。总数 2×6=12。

陷阱:空位数写成 n−1(漏两端);把要不相邻的元素先排。

题型C — 相同元素分配(隔板法)

触发信号:「相同的球/名额」「每人至少 1 个」「正整数解个数」。

标准动作:n 个相同球 n−1 个缝,插 m−1 块隔板分给 m 人:C(n−1,m−1)。允许为 0 先「每人加 1 头」转化。

示例(带解):方程 x+y+z=8 的正整数解个数=把 8 个相同单位分给 3 个未知量每个至少 1:C(8−1,3−1)=C(7,2)=21。

陷阱:元素不同却用隔板;忘了「至少 1」的前提;可为 0 时没做加人头转化。

题型D — 间接法(至少/至多)

触发信号:「至少」「至多」「不全是」「不都」,正面情况太碎。

标准动作:算全部情况数 − 反面(不合要求)的情况数。反面最好只有一两类且互斥。

示例(带解):从 5 男 4 女选 4 人,至少 1 女。总 C(9,4)=126,反面全男 C(5,4)=5。答案 126−5=121。

陷阱:反面没数全(至少2的反面是0或1两类都要减);把「至少1」误算成 C(4,1)·C(8,3)（重复计数）。

题型E — 分组分配(均匀/非均匀)

触发信号:「分成几组/几堆」「分配给几个人」,组是否等大、是否有主。

标准动作:非均匀:连乘 C 即可。平均分成 k 组:连乘 C ÷ k!。分给不同的人(有序):在分组基础上不除,或分完再×A(组,组)。

示例(带解):6 本不同书分给甲乙丙,分别得 1、2、3 本:C(6,1)·C(5,2)·C(3,3)=6×10×1=60(人不同,有序不除)。若平均每人 2 本:C(6,2)C(4,2)C(2,2)=90,人可区分不除,仍是 90。

陷阱:平均分「无编号堆」忘了÷k!；分给不同的人却错误地÷k!；部分均匀只对均匀那部分除阶乘。

题型F — 数字排列(特殊位置)

触发信号:组数、无重复数字、「首位不为 0」、奇偶位约束。

标准动作:特殊位置(或特殊元素 0)优先安排,再排其余;有奇偶/整除约束的先定末位。

示例(带解):用 0~5 组无重复的三位偶数。末位是特殊位置(要偶:0,2,4)。末位为0:百十位 A(5,2)=20;末位为2或4(2种):百位不能0(4种)、十位(4种)=4×4×2=32。合计 20+32=52。

陷阱:首位放了0;偶数约束下末位与首位互相牵制,要分「末位是否为0」讨论。

① 捆绑法捆内部要排序!相邻 k 个别忘乘 A(k,k),多组相邻各乘一次。

② 插空法空位数是 n+1(含两端),不是 n−1;而且要先排别人再插不相邻的。

③ 隔板法只对相同元素,且标准型要求每份至少 1 个;可为 0 先「加人头」转化。

④ 平均分组÷ 组数阶乘(无编号的堆重复了 k! 次);分给不同的人则不除。

⑤ 分类要不重不漏:各类必须互斥且穷尽;分类(加)与分步(乘)不能混。

⑥ 「至少/至多」优先间接法;但反面若有多类要全减,别只减一类。

⑦ 排列 A(有序) vs 组合 C(无序):选出来还排不排队,决定用 A 还是 C。

⑧ 数字排列首位不为 0;有偶/整除约束先定末位,再讨论首位。

⑨ 「至少 1 女」别用 C(4,1)·C(8,3)——那样把含多女的情况重复计数了;要用间接法或分类。

① 一切方法都在回答一个问题:「怎样让每种结果被数到且只数一次」。 捆绑是把「相邻」这个约束变成「一个整体」从而不重不漏;插空是把「不相邻」翻译成「先占位再填空」;隔板是把「相同元素分配」转成「在缝里选位置」。看穿这一层,你选方法不再靠背题型,而靠「哪种表述让计数变得干净」。

② 相同 vs 不同,是选隔板还是排列的分水岭。 相同元素之间的顺序没有意义(用隔板/组合),不同元素之间的顺序有意义(用排列)。做题第一眼先给元素「贴标签」:能区分吗?这决定了你整套工具。

③ 有序无序,是÷阶乘的总开关。 平均分组÷k!、组合 C 里的÷m!、乃至圆排列÷n——本质都一样:某个「顺序」在本题里不算数,就把它多数的倍数除掉。理解「除以对称的阶数」,分组、圆桌、项链问题一网打尽。

④ 正难则反是一种「视角切换」而非技巧。 「至少」正面碎、反面整,就减反面;有时「恰好」也能用两个「至少/至多」相减。养成「先估正反两边谁更好数」的习惯,能省掉大量分类。

⑤ 优先安排「最受限的」。 无论是特殊位置(百位非0)还是特殊元素(数字0、必须相邻的人),谁的自由度最小谁先上——这和贪心地「先处理硬约束」一个道理,能把后续步骤变成无约束的纯排列,避免层层修正。

⑥ 计数≠二项式定理。 本页讲「怎么数方案数」(排列组合的应用);二项式定理讲的是 (a+b)ⁿ 展开后每一项的系数(通项 C(n,r)aⁿ⁻ʳbʳ)。二者共用组合数 C,但一个求「有多少种」,一个求「某项系数是多少」,别把两类问题的套路混用。