从集合划分到二项式定理

1. 最初的问题：如何将N个不同的物品分成两份？ 🤔

这是最基础的组合问题。答案取决于“两份”是否有区别。

思路: 每个物品都有2个选择 (给甲或给乙)，总共有 $2 \times 2 \times \dots \times 2 = 2^N$ 种选择。但是，这包含了所有物品都给甲（乙为空）和所有物品都给乙（甲为空）这两种极端情况。因为要求是分成“两份”，所以需要排除这2种情况。
公式: $2^N - 2$

思路: 这种情况是在“有区别”的基础上思考的。对于任何一种分法，比如 {A堆, B堆}，在情况一中被当成了“甲得A，乙得B”和“甲得B，乙得A”两种。在这里，这两种被视为一种。因此，情况一的结果中，每种分法都重复计算了2次，直接除以2即可。
公式: $(2^N - 2) / 2 = 2^{N-1} - 1$
知识点: 这个数在组合数学中被称为第二类斯特林数 S(N, 2)。

为了理解更复杂的问题，我们需要一个核心工具：组合数。

定义: $C(n,k)$ 或 $\binom{n}{k}$ 表示从 n 个不同物品中，选出 k 个，一共有多少种选法。
口号: “n 选 k，顺序无关”。
计算公式: $C(n,k) = \frac{n!}{k!(n-k)!}$
- 这里的 n! 代表 n 的阶乘 (例如, $3! = 3 \times 2 \times 1 = 6$)

现在我们可以回答一个相关的问题：从 N 个物品中，选出任意数量的物品（0个、1个、…、N个），总共有多少种子集？

问题: $C(N,0) + C(N,1) + C(N,2) + \dots + C(N,N) = ?$
直观解释: 这个加法公式的本质，是计算一个包含 N 个元素的集合的所有子集的总数。
- $C(N,0)$ 是大小为0的子集数量 (空集)。
- $C(N,1)$ 是大小为1的子集数量。
- …
- $C(N,N)$ 是大小为N的子集数量 (原集合本身)。
更简单的思路: 换个角度想，对于集合中的每一个元素，我们都有2种独立的决定：“选入子集”或“不选入子集”。因此，总共有 $\underbrace{2 \times 2 \times \dots \times 2}_{N \text{ times}} = 2^N$ 个子集。
结论: $C(N,0) + C(N,1) + \dots + C(N,N) = 2^N$

二项式定理是将上述思想推广到代数的强大工具。它告诉我们如何展开 $(x+y)$ 的 n 次方。

定理: 它将组合数 $C(n,k)$ 作为展开式中的系数。
公式: $$(x+y)^n = \sum_{k=0}^{n} C(n,k) x^{n-k} y^k$$
展开形式: $$(x+y)^n = C(n,0)x^n + C(n,1)x^{n-1}y^1 + C(n,2)x^{n-2}y^2 + \dots + C(n,n)y^n$$
内在逻辑: 展开 $(x+y)^n = (x+y)\dots(x+y)$ 时，要得到 $x^{n-k}y^k$ 这一项，你需要从 n 个 $(x+y)$ 括号中选出 k 个来提供 y（其余 n-k 个则提供 x）。而“从n个中选k个”的方法数，正好就是 $C(n,k)$。
关联: 如果我们让 $x=1$ 并且 $y=1$，二项式定理就变成了： $$(1+1)^n = C(n,0)(1)^{n}(1)^{0} + C(n,1)(1)^{n-1}(1)^{1} + \dots + C(n,n)(1)^{0}(1)^{n}$$ $$2^n = C(n,0) + C(n,1) + \dots + C(n,n)$$ 这完美地验证了第3步的结论，展示了代数与组合计数的深刻联系。

有没有一种图形化的方式来看待这些系数 $C(n,k)$ 呢？有！就是杨辉三角。

由 Gemini 创建：https://g.co/gemini/share/69995f1f6b50