离散数学 - 组合数学

2025年6月5日

只是 copy，没有力气整理了。

公式

这两个公式在组合数学中非常有用，分别解决不同类型的问题。我们来逐个解释一下它们的来源和思路：

问题场景：从排成一排的 n 个不同元素中，选出 k 个元素，要求这 k 个元素中任意两个都不能相邻。问有多少种选法？ 推导思路 (转换法/映射法):

标记元素位置： 假设这 n 个元素的位置编号为 1,2,…,n。我们要选出 k 个位置 x1,x2,…,xk，并且它们满足 1≤x1<x2<…<xk≤n。
不相邻条件： “任意两个不相邻”意味着：
- x2−x1≥2
- x3−x2≥2
- …
- xk−xk−1≥2
变量代换 (核心技巧)： 为了消除“≥2”这个不方便处理的条件，我们引入一组新的变量 y1,y2,…,yk：
- y1=x1
- y2=x2−1
- y3=x3−2
- …
- yk=xk−(k−1)
分析新变量的性质：
- 由于 x1≥1，所以 y1≥1。
- y2−y1=(x2−1)−x1=(x2−x1)−1。因为 x2−x1≥2，所以 (x2−x1)−1≥1。这意味着 y2>y1。
- 同理，y3−y2=(x3−2)−(x2−1)=(x3−x2)−1≥1。这意味着 y3>y2。
- 依此类推，我们得到 1≤y1<y2<…<yk。
- 现在看 yk 的上限：yk=xk−(k−1)。因为 xk≤n，所以 yk≤n−(k−1)=n−k+1。
问题转化：我们成功地将“从 1,…,n 中选 k 个不相邻的数 xi”的问题，转化为了“从 1,…,n−k+1 中选 k 个不同的数 yi”的问题。从 n−k+1 个数中选 k 个不同的数，选法数量就是组合数 C(n−k+1,k)。

另一种直观理解 (插空法变种 / 隔板法思想)：

想象我们有 k 个要选中的物品（“选中球”）和 n−k 个不选中的物品（“白色球”）。
为了保证选中的 k 个物品不相邻，我们可以先把这 k 个“选中球”拿出来。
剩下 n−k 个“白色球”。将它们排成一排，它们之间以及两端会形成 (n−k)+1 个空隙。 _ W _ W _ … _ W _ (W代表白色球，_ 代表空隙)
现在，将 k 个“选中球”放入这 (n−k)+1 个空隙中，每个空隙最多放一个球。这样就能保证任意两个“选中球”之间至少隔着一个“白色球”，即它们不相邻。
从 (n−k)+1 个空隙中选择 k 个空隙来放置“选中球”，选法数量就是 C(n−k+1,k)。

问题场景1 (不定方程解)：

方程 x1+x2+…+xk=n 有多少组非负整数解 (即 xi≥0)？

问题场景2 (相同物品分给不同人)：

将 n 个相同的物品分给 k 个不同的人，每人可以分到0个或多个，有多少种分法？

这两个场景是等价的。xi 可以看作第 i 个人分到的物品数量。

推导思路 (“隔板法” / “Stars and Bars”):

物品表示 (Stars)：把 n 个相同的物品想象成 n 个小星星（*）排成一列：
- - - … * (共 n 个星)
分组 (Bars)： 要将这 n 个星星分成 k 组 (对应 k 个人或 k 个变量 xi)，我们只需要在这 n 个星星形成的序列中插入 k−1 个隔板（|）。
- 例如，如果 n=5,k=3 (即 x1+x2+x3=5)：
  - **|*|** 表示 x1=2,x2=1,x3=2
  - ***||** 表示 x1=3,x2=0,x3=2
  - ||***** 表示 x1=0,x2=0,x3=5
排列隔板和星星：我们现在总共有 n 个星星和 k−1 个隔板。这些星星和隔板共同占据了 n+(k−1) 个位置。

我们的问题就转化成了：在这 n+k−1 个位置中，选择 k−1 个位置放置隔板（剩下的位置自然就是星星了）。

选择的方法数就是组合数 C(n+k−1,k−1)。
等价形式：

同样，我们也可以选择 n 个位置放置星星（剩下的位置就是隔板）。

选择的方法数是 C(n+k−1,n)。

根据组合数的性质 C(N,K)=C(N,N−K)，我们知道 C(n+k−1,k−1)=C(n+k−1,(n+k−1)−(k−1))=C(n+k−1,n)。所以这两个表达式是等价的。

场景变形：如果要求每人至少分到1个物品 (即 xi≥1)

预先分配： 先给每人（每个变量）分配1个物品。这样就用掉了 k 个物品。
剩余分配： 还剩下 n−k 个物品。现在的问题变成将这 n−k 个物品分给 k 个人，每人可以分到0个或多个。
套用公式：把问题中的 n 替换为 n−k，套用上面的隔板法公式：

C((n−k)+k−1,k−1)=C(n−1,k−1)。
- 或者直观理解：有 n 个星星 * * ... *。它们之间有 n−1 个空隙。要将它们分成 k 份（且每份至少1个），只需要在这 n−1 个空隙中选择 k−1 个位置插入隔板。方法数是 C(n−1,k−1)。
- 你之前第一个问题“4位同学分吃10个相同的苹果，每位同学至少会吃1个”，就是这个变形。n=10,k=4，所以是 C(10−1,4−1)=C(9,3)=84。