112 个组合问题：1-3 章整理

组合计数的第一步不是套公式，而是判断：对象是否有区别、位置是否有区别、是否允许重复、顺序是否重要。

  • 组合数学
  • 读书笔记
  • 排列组合
  • 球盒模型

一句话算法

组合计数的第一步不是套公式，而是判断：对象是否有区别、位置是否有区别、是否允许重复、顺序是否重要。

问题模型

本页整理《112 个组合问题》前 3 章中最常用的基础模型：

  1. 分类加法原理。
  2. 分步乘法原理。
  3. 幂集与子集数量。
  4. 排列、组合和有重复排列。
  5. 星星与杠杠，也就是隔板法。
  6. 多项式系数。

这些内容的共同目标是：把题目中的“方案”变成一个可以计数的集合。

核心直觉

计数题最怕重复和遗漏。

  • 分类加法原理解决“分成几类”的问题。
  • 分步乘法原理解决“按步骤构造”的问题。
  • 排列组合解决“顺序是否重要”的问题。
  • 隔板法解决“相同物品分配到不同盒子”的问题。
  • 多项式系数解决“重复元素排列”或“按指定大小分组”的问题。

只要能说清楚每个方案的唯一表示，公式通常就自然出现。

第一章：计数基本知识

集合大小

集合 AA 的元素个数记作：

∣A∣ |A|

计数题本质上是在求某个方案集合的大小。

分类加法原理

如果集合 SS 被拆成若干个互不相交的子集：

S=A1∪A2∪⋯∪Am S=A_1\cup A_2\cup\cdots\cup A_m

并且任意两类不相交：

Ai∩Aj=∅(i≠j) A_i\cap A_j=\varnothing\quad(i\ne j)

那么：

∣S∣=∣A1∣+∣A2∣+⋯+∣Am∣ |S|=|A_1|+|A_2|+\cdots+|A_m|

直觉：每个方案只属于一个类别，所以把各类数量相加不会重复。

分步乘法原理

如果一个方案必须按 mm 步构造，并且第 ii 步有 cic_i 种选择，那么方案总数是：

c1c2⋯cm c_1c_2\cdots c_m

直觉：第一步的每一种选择，都能和第二步的每一种选择配对；所有步骤连起来形成一条完整方案。

幂集

集合 AA 的所有子集组成的集合叫幂集，记作：

2A 2^A

如果 ∣A∣=n|A|=n，则：

∣2A∣=2n |2^A|=2^n

证明直觉：每个元素只有“选”或“不选”两种状态，nn 个元素独立选择，所以共有 2n2^n 个子集。

第二章：排列组合四种基本模型

设有 kk 次选择或 kk 个球，候选对象或盒子共有 nn 个。

模型 球是否有区别 盒子是否有区别 是否允许重复放入同一盒 方案数
有重排序 有区别 有区别 允许 nkn^k
无重排序 有区别 有区别 不允许 n!(n−k)!\frac{n!}{(n-k)!}
组合 无区别 有区别 不允许 (nk)\binom nk
星星与杠杠 无区别 有区别 允许 (n+k−1k)\binom{n+k-1}{k}

这张表对应很多表面不同、实质相同的问题。

模型一：有重排序

问题形式：

  • 共有 nn 种冰淇淋口味，取 kk 勺，顺序有区别，可以重复取。
  • 把 kk 个有编号的球放到 nn 个有编号的盒子中，每个盒子可以放任意多个球。

每一勺或每一个球都有 nn 种选择，所以：

nk n^k

模型二：无重排序

问题形式：

  • 从 nn 个对象中按顺序取 kk 个，不允许重复。
  • 把 kk 个有编号的球放到 nn 个有编号的盒子中，每盒最多一个球。

第一个位置有 nn 种选择，第二个位置有 n−1n-1 种，直到第 kk 个位置：

P(n,k)=n(n−1)⋯(n−k+1)=n!(n−k)! P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}

模型三：组合

问题形式：

  • 从 nn 个对象中选 kk 个，不考虑顺序。
  • 把 kk 个无区别的球放入 nn 个有编号盒子，每盒最多一个。

先按排列数计算，再把同一组元素内部的 k!k! 种顺序除掉：

(nk)=P(n,k)k!=n!k!(n−k)! \binom nk=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}

组合数也可以理解为：nn 个元素的集合中，含 kk 个元素的子集数量。

常用性质：

(nk)=(nn−k) \binom nk=\binom n{n-k}
(nk)=(n−1k)+(n−1k−1) \binom nk=\binom{n-1}{k}+\binom{n-1}{k-1}

第二个式子来自“固定一个元素，按选不选它分类”。

模型四：星星与杠杠

问题形式：

把 kk 个无区别的球放到 nn 个有编号盒子中，每个盒子可以放任意多个，允许空盒。

等价于求非负整数解数量：

x1+x2+⋯+xn=k,xi≥0 x_1+x_2+\cdots+x_n=k,\quad x_i\ge0

答案：

(n+k−1k) \binom{n+k-1}{k}

也可以写成：

(n+k−1n−1) \binom{n+k-1}{n-1}

如果要求每个盒子至少一个：

x1+x2+⋯+xn=k,xi≥1 x_1+x_2+\cdots+x_n=k,\quad x_i\ge1

答案为：

(k−1n−1) \binom{k-1}{n-1}

第三章：多项式系数

例 18：冰淇淋蛋筒

有三种口味：香草、巧克力、草莓。必须使用：

  • vv 勺香草。
  • cc 勺巧克力。
  • ss 勺草莓。

总勺数为：

k=v+c+s k=v+c+s

蛋筒从下到上有顺序，问有多少种不同蛋筒？

视角一：重复元素排列

把蛋筒看成长度为 kk 的序列，其中有：

  • vv 个相同的 V。
  • cc 个相同的 C。
  • ss 个相同的 S。

如果 kk 个位置都不同，先全排列有 k!k! 种。

但同一种口味内部交换不产生新方案，所以要除掉重复：

k!v!c!s! \frac{k!}{v!c!s!}

这就是多项式系数：

(kv,c,s) \binom{k}{v,c,s}

视角二：分步占位

从 kk 个位置中选 vv 个放香草：

(kv) \binom{k}{v}

再从剩下 k−vk-v 个位置中选 cc 个放巧克力：

(k−vc) \binom{k-v}{c}

剩下 ss 个位置自动放草莓。

总数为：

(kv)(k−vc) \binom{k}{v}\binom{k-v}{c}

化简：

(kv)(k−vc)=k!v!(k−v)!⋅(k−v)!c!s!=k!v!c!s! \binom{k}{v}\binom{k-v}{c} = \frac{k!}{v!(k-v)!}\cdot\frac{(k-v)!}{c!s!} = \frac{k!}{v!c!s!}

两个视角得到同一个答案。

算法步骤

遇到排列组合题，可以按这个顺序判断：

  1. 方案是否可以分成互不重叠的几类。如果可以，用加法原理。
  2. 方案是否由连续步骤构造。如果可以，用乘法原理。
  3. 顺序是否重要。重要时偏排列，不重要时偏组合。
  4. 是否允许重复选择。允许时考虑 nkn^k 或隔板法。
  5. 是否有多个相同元素。若有，考虑多项式系数。
  6. 是否是在分配相同物品。若是，优先转成整数解。

算法证明

组合公式证明

从 nn 个不同元素中有序选出 kk 个，一共有：

P(n,k)=n!(n−k)! P(n,k)=\frac{n!}{(n-k)!}

每一个 kk 元集合内部可以排成 k!k! 个顺序。

所以：

P(n,k)=(nk)k! P(n,k)=\binom nk k!

因此：

(nk)=n!k!(n−k)! \binom nk=\frac{n!}{k!(n-k)!}

星星与杠杠证明

求：

x1+x2+⋯+xn=k,xi≥0 x_1+x_2+\cdots+x_n=k,\quad x_i\ge0

把 kk 个星星排成一行，再插入 n−1n-1 个隔板。总共有：

k+n−1 k+n-1

个位置，其中选 n−1n-1 个位置放隔板：

(k+n−1n−1) \binom{k+n-1}{n-1}

也就是：

(k+n−1k) \binom{k+n-1}{k}

复杂度分析

这些基础模型主要是数学计数，复杂度取决于实现方式：

  • 单次按公式计算：通常 O(k)O(k)。
  • 预处理阶乘和逆元后查询组合数：O(1)O(1) 查询，预处理 O(n)O(n)。
  • Pascal 递推组合数：时间复杂度 O(n2)O(n^2)，空间复杂度 O(n2)O(n^2)。
  • 输出所有方案时，复杂度至少等于方案数量。

测试用例

有重排序

n=3,k=2n=3,k=2：

AA AB AC
BA BB BC
CA CB CC

共有：

32=9 3^2=9

组合

从 {1,2,3,4} 中选 22 个：

1 2
1 3
1 4
2 3
2 4
3 4

共有：

(42)=6 \binom42=6

隔板法

求：

x1+x2+x3=4,xi≥0 x_1+x_2+x_3=4,\quad x_i\ge0

答案：

(4+3−13−1)=(62)=15 \binom{4+3-1}{3-1}=\binom62=15

应用分类详解

一、按类别计数

典型模式： 题目可以拆成若干互斥情况。

识别信号： 出现“要么……要么……”“按最后一步分类”“按是否包含某元素分类”。

核心建模： 用分类加法原理，重点检查类别之间是否重叠。

二、按步骤构造

典型模式： 一个方案由多个连续选择组成。

识别信号： 先选谁，再选谁；先定位置，再填内容。

核心建模： 用分步乘法原理，重点检查每一步选择数量是否依赖前一步。

三、排列与组合

典型模式： 从若干对象中选一部分。

识别信号： “顺序不同是否算不同”是关键句。

核心建模： 顺序重要用排列；顺序不重要用组合。

四、整数分配

典型模式： 把相同物品分给不同对象。

识别信号： 相同球、糖果、苹果、金币、每个盒子可多个。

核心建模： 转成非负整数解或正整数解，用隔板法。

五、重复元素排列

典型模式： 排列一个有重复元素的序列。

识别信号： 有若干种颜色、口味、字符，每种出现次数固定。

核心建模： 用多项式系数，先全排再除掉相同元素内部交换。

经典例题

1. 子集数量

问 nn 个元素有多少个子集。每个元素选或不选，答案为 2n2^n。

2. 不重复选人排队

从 nn 个人中选 kk 个排成一队，顺序重要，答案为 P(n,k)P(n,k)。

3. 选委员会

从 nn 个人中选 kk 个组成委员会，顺序不重要，答案为 (nk)\binom nk。

4. 分糖果

kk 个相同糖果分给 nn 个不同小朋友，允许有人没有，答案为 (n+k−1k)\binom{n+k-1}{k}。

5. 冰淇淋蛋筒

固定每种口味出现次数，问从下到上的排列数，答案为多项式系数。

参考

  • 本书排列与组合：math/combinatorics/combinatorics/index.md
  • 本书球盒模型：enumeration_permutaion_combination/ball_and_box/index.md
  • 本书组合计数模板题：math/combinatorics/模板题目.md