多重集组合数：从隔板法到不定方程，打通组合计数核心模型

1. 项目概述从“选水果”到“分糖果”的计数思维跃迁刚接触组合数学的朋友常常会卡在排列组合的各种模型里感觉公式背了不少但题目稍微变个花样就无从下手。比如给你一堆苹果、香蕉、橘子让你随便选几个有多少种选法这听起来是个简单的“选取问题”。但如果我告诉你苹果有3个一模一样的香蕉有5个一模一样的橘子无限供应你还能轻松算出来吗这就引出了我们今天要啃的硬骨头——多重集组合数。它绝不是一个冷僻的数学概念而是理解“允许重复元素的选取”这一核心计数思想的钥匙。掌握了它你就能把“从三种水果里选5个”和“求方程xyz5的非负整数解个数”这两类看似风马牛不相及的问题统一到同一个数学模型下。本文的目标就是带你彻底打通“选取问题”、“多重集组合问题”和“不定方程非负整数解问题”这三个经典计数模型之间的任督二脉让你看到它们本质上是“一家人”。无论你是正在备考的学生还是对逻辑思维感兴趣的爱好者理解这套框架都能让你在面对复杂计数场景时拥有降维打击的能力。2. 核心思路拆解连接三个世界的“转化”艺术为什么这三个问题能放在一起讲关键在于一个核心的“转化”思想。我们不要孤立地记忆公式而要理解模型之间的桥梁。2.1 模型一基础选取问题球与盒子皆不同这是我们最熟悉的模型从n个不同的元素中选取r个元素。这里有两个关键变体排列Permutation关注顺序。比如从{A, B, C}中选2个排成一列AB和BA算两种。公式是P(n, r) n! / (n-r)!。组合Combination不关注顺序。同样是{A, B, C}中选2个AB和BA算同一种。公式是C(n, r) n! / (r! * (n-r)!)也记作 (n choose r)。这个模型的核心假设是每个元素都是独一无二的并且选取时“至多选一次”。它构成了我们计数思维的基石。2.2 模型二多重集组合问题球同盒子不同现在情况变了。我们有一堆元素但其中有些是相同的。比如一个多重集 {∞·苹果 ∞·香蕉 ∞·橘子}或者 {3·苹果 5·香蕉 2·橘子}。这里的“3·苹果”表示有3个相同的苹果。我们要从中选取r个元素例如选5个水果问有多少种选法。核心转化这个问题可以巧妙地转化为我们熟悉的“组合”问题。想象我们有n种不同类型的水果n3。我们想知道每种水果各选了多少个。设选苹果x1个香蕉x2个橘子x3个那么 x1 x2 x3 5。并且对于无限供应的情况x1, x2, x3可以是任意非负整数对于有限供应如苹果最多3个则还需满足 0 ≤ x1 ≤ 3。对于无限多重集的组合数有一个非常优美的结论从n种元素中可重复地选取r个的组合数等于C(n r - 1, r)。这个公式的推导是理解的关键我们稍后在实操部分会详细用“隔板法”来演绎。2.3 模型三不定方程非负整数解问题分拆问题现在我们完全抛开水果的比喻直接看一个方程x1 x2 ... xn r其中x1, x2, ..., xn都是非负整数。求这个方程有多少组解。惊人的联系你会发现模型二中的等式 x1 x2 x3 5代表三种水果各选几个在数学形式上与模型三的方程一模一样求方程的非负整数解个数就是在求“将r个无法区分的‘1’分配到n个有编号的变量盒子中允许空盒”的方法数。这本质上就是模型二的抽象表述。所以这三个模型的思维链条是这样的具体选取场景选水果→ 抽象为数量方程x1x2x35→ 对应不定方程求解问题。 解决它们的关键工具都是隔板法Stars and Bars。注意这里说的“盒子不同”对应的是变量x1, x2,...是有区别的代表不同种类的水果或不同的变量。如果盒子也相同那就变成了“整数分拆”问题难度更大不在本文讨论范围内。3. 核心原理与公式推导隔板法图解上面提到了神奇的公式 C(n r - 1, r) 和“隔板法”。光说不够我们必须亲手“画”出来才能印象深刻。假设我们面对一个经典问题方程 x y z 5 有多少组非负整数解我们可以把数字5想象成5个完全相同的小球或星星“★”。我们的任务是把这5个球放进3个有标签的盒子X盒 Y盒 Z盒里允许有的盒子为空。放好后每个盒子里的球数就对应了一个变量的值。关键技巧为了用组合数公式计算我们需要处理“空盒”问题。一个巧妙的方法是先给每个盒子“预支”一个球。但更直观的方法是使用“隔板”。我们把“球”和“隔板”一起排列。5个球排成一排它们之间和两端一共有6个空隙|球|球|球|球|球|。如果我们想分成3组只需要放入2块隔板因为n3个盒子需要n-12块隔板来分隔。例如排列 ★ | ★ ★ | ★ ★ 表示x1, y2, z2。第一块板在第一个球后第二块板在第三个球后排列 ★ ★ ★ ★ ★ | | 表示x5, y0, z0。两块板都放在所有球的后面排列 | | ★ ★ ★ ★ ★ 表示x0, y0, z5。现在问题转化为我们有5个★和2块|把它们排成一排有多少种排法注意★和★之间没有区别|和|之间也没有区别。这就是一个典型的组合问题从总共 (52)7 个位置中选出2个位置来放隔板或者等价地选出5个位置来放星星。所以总方法数就是C(7, 2)也就是C(53-1, 5)或C(53-1, 3-1)。一般化公式对于方程 x1 x2 ... xn r非负整数解解的数量等于C(r n - 1, r)或C(r n - 1, n - 1)。这两个是相等的因为 C(N, k) C(N, N-k)。这个 C(r n - 1, r) 正是前面提到的无限多重集组合数公式。其中 n 是种类数变量个数r 是要选取的总数方程右边的和。实操心得很多同学记混 C(nr-1, r) 里到底是谁减一。一个记忆窍门是“总和加种类减一”。把 r总和和 n种类加在一起再减去1。或者直接理解“物品球和隔板的总数是 r (n-1)从中选位置放隔板”。4. 从理论到实战三类问题互化示例解析懂了原理我们来看具体怎么用。下面用几个例子展示如何在这三类问题之间自由转换和求解。4.1 示例1经典多重集组合——水果挑选问题商店里有苹果、香蕉、橘子三种水果供应充足可视为无限多重集。小明要买5个水果有多少种不同的选购方案只关心每种水果的个数不关心单个水果的差异或挑选顺序解析识别模型从3种n3水果中可重复地选取5个r5。这是标准的无限多重集组合问题。建立方程设买苹果x个香蕉y个橘子z个。则 x y z 5其中 x, y, z ≥ 0。应用公式直接套用公式方案数为 C(53-1, 5) C(7, 5) C(7, 2)。计算C(7, 2) 7! / (2! * 5!) (76) / (21) 21。答案有21种不同的选购方案。转换视角这个问题完全等价于“求方程 xyz5 的非负整数解个数”。在计数课上它们就是同一道题。4.2 示例2带约束的多重集组合——有限库存问题商店里苹果只剩3个香蕉只剩5个但橘子充足。小明还是要买5个水果有多少种方案解析识别模型仍然是多重集组合但有了上界约束。多重集可表示为 {3·苹果, 5·香蕉, ∞·橘子}。建立方程设苹果、香蕉、橘子分别买 a, b, c 个。则有a b c 50 ≤ a ≤ 30 ≤ b ≤ 5 因为只买5个b≤5自然满足有效约束是b≤5c ≥ 0解题策略对于带约束的问题标准方法是使用容斥原理。先计算无约束下的总解数 C(53-1, 2)21。然后减去违反约束的部分。违反“a≤3”意味着 a≥4。令 a‘ a - 4 ≥ 0代入方程a’ b c 1。这个新方程的非负整数解个数为 C(13-1, 2)C(3,2)3。这部分需要减去。违反“b≤5”意味着 b≥6。但总共才买5个b不可能≥6。所以违反此条件的解数为0。应用容斥根据容斥原理合法解数 无约束解数 - (违反a约束的解数 违反b约束的解数) (同时违反a和b约束的解数)。同时违反意味着 a≥4 且 b≥6同样因为总数5不可能解数为0。 因此最终方案数 21 - 3 - 0 0 18。答案有18种购买方案。注意事项在处理多个上界约束时容斥原理的计算量会增大。务必仔细检查约束条件是否可能同时被违反。像本例中b≥6这种与总数矛盾的约束可以直接判断为0简化计算。4.3 示例3不定方程正整数解——至少一个问题方程 x y z 8 有多少组正整数解即 x, y, z ≥ 1解析识别模型这是不定方程非负整数解问题的一个变体要求每个变量至少为1。经典转化这是一个必须掌握的技巧。要求正整数解我们可以做一个变量替换。令 x’ x - 1, y‘ y - 1, z’ z - 1。因为 x, y, z ≥ 1所以 x‘, y’, z‘ ≥ 0。代入原方程(x‘1) (y’1) (z‘1) 8 x’ y‘ z’ 5。转化完成问题转化为求 x‘ y’ z‘ 5 的非负整数解个数。这就是我们熟悉的模型了。应用公式解的数量为 C(53-1, 5) C(7, 5) 21。答案有21组正整数解。更一般的结论方程 x1 x2 ... xn r 的正整数解个数为C(r - 1, n - 1)。推导过程就是上面的替换令每个新变量等于原变量减1总和 r 就变成了 r - n然后套用非负整数解公式 C((r-n)n-1, r-n) C(r-1, r-n) C(r-1, n-1)。这个“至少为1”的约束在“分糖果每人至少一颗”这类问题中非常常见。4.4 示例4综合应用——名额分配问题问题将7个相同的实习名额分配给3个不同的部门A, B, C。要求部门A至少分到1个名额。部门B至少分到2个名额。部门C可以没有名额。 问有多少种分配方案解析转化为方程设分配给A、B、C部门的名额分别为a, b, c。则a b c 7a ≥ 1, b ≥ 2, c ≥ 0标准化为非负整数约束为了使用标准公式需要消去下界。令 a‘ a - 1 ≥ 0令 b’ b - 2 ≥ 0令 c‘ c ≥ 0代入方程(a‘1) (b’2) c‘ 7 a’ b‘ c’ 4。问题转化现在变成了求 a‘ b’ c‘ 4 的非负整数解个数。这里 n3, r4。应用公式解的数量为 C(43-1, 4) C(6, 4) C(6, 2) 15。答案有15种分配方案。这个例子展示了如何综合运用“正整数解转化”技巧来处理多个不同的下界约束。核心思想就是通过变量替换将所有约束都化为“≥0”的标准形式。5. 常见误区与深度辨析在学习和应用这三个模型时有几个坑几乎每个人都会踩一遍。我把它们总结出来希望能帮你提前避雷。5.1 误区一“选取”与“排列”傻傻分不清这是最根本的混淆。务必时刻问自己顺序是否重要选水果你买了一个苹果和一个香蕉。无论你先拿苹果还是先拿香蕉最终你篮子里的东西是一样的。顺序不重要是组合问题。排座位让甲、乙、丙三人坐在三个不同的座位上甲坐1号位和甲坐2号位是不同的情况。顺序重要是排列问题。在多重集组合中我们讨论的始终是“组合”即只关心每种元素选了多少个不关心你挑选它们的先后顺序。如果问题涉及“排列”比如用“苹果、苹果、香蕉”这三个单词能组成多少个不同的字符串那就是多重集排列问题公式完全不同n! / (n1! * n2! * ...)千万别搞混。5.2 误区二混淆“可重复”与“元素本身是否相同”“从n个不同元素中可重复地选r个”这句话有点绕。关键在于“n个不同元素”指的是类型或种类不同。比如苹果、香蕉、橘子是3种不同的类型。“可重复”指的是同一种类型的元素你可以选取多个。比如你可以选2个苹果、3个香蕉。“元素本身相同”在同一个类型下比如所有苹果我们认为它们是没有区别的。选取“这个苹果”和“那个苹果”不算不同的选法。这正是多重集组合的设定。如果每个苹果都是独一无二的比如印了编号那就变成了从“n个不同元素”中选取但可能允许重复选取同一个元素有放回这又是另一种模型计算公式也不同是 n^r。所以审题时一定要明确“相同”是在哪个层面上说的。5.3 误区三隔板法中的“板”和“空位”数错这是计算错误的主要来源。记住这个定式我们有r个完全相同的物品球、星星、1。我们要把它们分配到n个有标签的盒子变量里。我们需要n-1块隔板来分隔出n个区域。物品和隔板总共有r (n-1)个位置。我们只需要决定这n-1块隔板放在哪里或者等价地决定r个物品放在哪里。所以方法是 C(r n - 1, n - 1) 或 C(r n - 1, r)。一个快速检查方法当 n2 时两个变量只需要1块隔板。公式变为 C(r1, 1) r1。这符合直觉x y r非负整数解就是 (0,r), (1,r-1), ..., (r,0)一共r1组。用这个简单情况验证你的公式记忆。5.4 误区四容斥原理应用时漏项或重复处理带约束尤其是上界的问题时容斥原理是利器但也容易出错。标准步骤设全集S为无约束下的所有解。设性质A1违反第一个约束如x1 U1。性质A2违反第二个约束如x2 U2...计算 |S|。计算 |A1|, |A2|,... 计算每个违反单个约束的解数方法通常是设新变量 xi‘ xi - (Ui1)。计算 |A1∩A2|, |A1∩A3|,... 计算同时违反两个约束的解数。计算更高阶的交集直到所有可能的组合。代入容斥公式合法解 |S| - Σ|Ai| Σ|Ai∩Aj| - Σ|Ai∩Aj∩Ak| ...常见错误忘记检查约束是否可能同时被违反如果总和r很小而两个上界U1和U2都很大可能根本不存在同时违反的情况那么这些交集项为0可以省去计算。计算|Ai|时新方程无解令 xi‘ xi - (Ui1) 后如果新方程的右边r - (Ui1)变成负数则 |Ai| 0。符号错误容斥原理是交错和奇数次交集是减偶数次交集是加。可以记口诀“减单加双”。6. 进阶技巧与问题变体掌握了基础模型后我们可以看看一些常见的变体这能极大拓宽你的解题视野。6.1 变体一变量有上下界约束这是示例2和示例4的综合。一般形式求 x1 x2 ... xn r 的整数解个数满足 Li ≤ xi ≤ Ui。通用解法处理下界令 yi xi - Li。则新变量 yi ≥ 0且新方程变为 Σyi r - ΣLi。记 R‘ r - ΣLi。如果R’为负则问题无解。处理上界对新的无下界变量 yi其上界变为 Ui‘ Ui - Li。问题转化为求 Σyi R’ 的非负整数解且 yi ≤ Ui‘。应用带上限的容斥原理如6.1所述使用容斥原理处理 yi ≤ Ui‘ 这些约束。6.2 变体二盒子变量部分相同这是更复杂的情况。例如方程 x y z 10但x和y被视为相同即(x,y,z)和(y,x,z)算同一种解。这不再是简单的隔板法因为隔板法默认盒子变量有标签不同。这类问题通常需要分类讨论或者使用生成函数等更高级的工具。在初等阶段如果变量相同的数量不多用分类枚举并除以排列数往往是可行的。6.3 变体三整数分拆无序分解这是把r拆成n个正整数之和但不考虑顺序。例如将5拆成3个正整数之和113, 131, 311都被视为同一种分拆1,1,3。这对应的是“把r个相同的球放入n个相同的盒子不允许空盒”的模型。整数分拆是一个深奥的领域没有像组合数那样简单的闭式解通常用递推关系或生成函数来研究。它和我们讨论的“变量有标签”的问题有本质区别。6.4 工具延伸生成函数母函数视角对于学有余力的朋友了解生成函数可以让你站在一个更高的维度统一这些问题。多重集组合问题可以对应到这样一个生成函数 G(x) (1 x x² x³ ...)^n 我们要求x^r项的系数。因为 (1 x x² ...) 1/(1-x)所以 G(x) 1/(1-x)^n。而 1/(1-x)^n 的幂级数展开中x^r 的系数正是C(nr-1, r)。生成函数将复杂的计数问题转化为代数运算是处理更复杂约束如每个变量有不同取值范围的终极武器。7. 实战演练与自查清单理论讲完了我们来点实战。下面有几个问题你可以先自己尝试再看解析。问题1一个烘焙店有巧克力、草莓、抹茶三种口味的无限供应的马卡龙。一位顾客要买8个马卡龙作为礼物有多少种购买组合问题2方程 a b c d 15其中 a, b, c, d 均为非负整数且要求 a ≤ 6, b ≤ 7。问有多少组解问题3将10支完全相同的铅笔分给4个小朋友每个小朋友至少得到1支铅笔有多少种分法解析与自查问题1解析这是标准的无限多重集组合问题。n3种类r8总数。解数为 C(83-1, 8) C(10, 8) C(10, 2) 45。自查点你是否清晰地识别出这是“可重复选取不计顺序”是否直接正确套用了公式问题2解析带约束的非负整数解问题。无约束解总数C(154-1, 15) C(18, 15) C(18, 3) 816。设A为违反a≤6的解即a≥7。令 a‘ a - 7 ≥ 0代入方程a’ b c d 8。解数 |A| C(84-1, 8) C(11, 8) C(11, 3) 165。设B为违反b≤7的解即b≥8。令 b‘ b - 8 ≥ 0代入方程a b’ c d 7。解数 |B| C(74-1, 7) C(10, 7) C(10, 3) 120。设A∩B为同时违反a≤6和b≤7的解即a≥7且b≥8。令 a‘ a - 7, b’ b - 8代入方程a‘ b’ c d 0。这个方程只有一组解 (0,0,0,0)。所以 |A∩B| 1。应用容斥原理合法解数 |S| - |A| - |B| |A∩B| 816 - 165 - 120 1 532。自查点你是否记得用容斥原理在计算|A∩B|时是否注意到新方程右边为0且非负整数解只有全零一组这是容易忽略的细节。问题3解析这是“正整数解”问题。将10支笔分给4人每人至少1支。设每人分得x1, x2, x3, x4支则 x1x2x3x410, xi ≥ 1。 令 yi xi - 1 ≥ 0则新方程为 Σyi 10 - 4 6。 解数为 C(64-1, 6) C(9, 6) C(9, 3) 84。自查点你是否熟练运用了“每人至少一个”转化为非负整数解的标准技巧是否记得n4 r10转化后新的r是10-46把这些模型和技巧内化后你会发现很多看似复杂的分配、选取、方程求解问题其实都是换了一层外衣的“老熟人”。关键在于训练自己剥离表象、识别核心模型的能力。我个人的经验是多做几种不同表述的练习题并强迫自己用“设变量、列方程、定约束、化标准、选公式”这五步法去分析很快就能形成条件反射。计数问题就像拼图一旦你拿对了第一块剩下的部分自然会各归其位。