离散数学 - 组合数学

This post is not yet available in English. Showing the original version.

June 5, 2025

Table of Contents
Table of Contents

离散数学 - 组合数学

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

公式

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

1. 公式 C(n−k+1,k): “选 k 个不相邻元素”

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

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

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

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

2. 公式 C(n+k−1,k−1) 或 C(n+k−1,n): “隔板法” / “不定方程非负整数解”

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

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

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

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

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

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

  1. 物品表示 (Stars)： 把 n 个相同的物品想象成 n 个小星星（*）排成一列：

        • … * (共 n 个星)

  2. 分组 (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

  3. 排列隔板和星星： 我们现在总共有 n 个星星和 k−1 个隔板。这些星星和隔板共同占据了 n+(k−1) 个位置。

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

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

  4. 等价形式：

    同样，我们也可以选择 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. 预先分配： 先给每人（每个变量）分配1个物品。这样就用掉了 k 个物品。

  2. 剩余分配： 还剩下 n−k 个物品。现在的问题变成将这 n−k 个物品分给 k 个人，每人可以分到0个或多个。

  3. 套用公式： 把问题中的 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。