二项式定理及其推广公式的一种简单理解办法
0x00 二项式定理
写在最前：\(\mathrm{C}_n^k=\binom{n}{k}=\frac{n!}{(n-k)! \cdot k!}\)
0x00.1 杨辉三角
前情提要：一种特殊的输出杨辉三角的方法
1 | 1 (a+b)**0 = 1 |
不难发现，杨辉三角每一行的数字正好就是 \((a+b)^n\) 展开之后的对应多项式，而每一项的系数又和组合数 \(\binom{n}{k}\) 是相等的。
一种简单的理解是，杨辉三角中的每一个数字，表示的是从顶点开始，只向左下或右下前进，最终到达该数字所在位置的所有可能路径的总数。经过基本的推理，可以看出对于第 \(n\) 行的左起第 \(k\) 个数字，想要从顶点到达该数字所在位置都需要且只需要向左 \(n-k\) 次、向右 \(k-1\) 次。假想小明现在按照此规则从顶点出发，显然，小明每向左或向右一次，都会向下移动一行；因此，小明向下移动 \(n-1\) 行后，便会到达目标数所在的行。换言之，小明在路途上将且仅将移动 \(n-1\) 次，而这 \(n-1\) 次中有且仅有 \(n-k\) 次是向左下方移动的。于是，得出结论：这本质上是个超几何分布问题，可能性总数可以表示为 \({\rm C}_{n-1}^{n-k}={\rm C}_{n-1}^{k-1}=\binom{n-1}{k-1}\)。
而与之对应的，多项式展开也是一个超几何分布问题。这是因为展开式中的 \(p\cdot a^qb^{n-q}\) 项，\(p\) 表示的是有多少个 \(a^qb^{n-q}\)，而每个 \(a^qb^{n-q}\) 都是在 \((a+b)(a+b)\cdots(a+b)\) 中挑选出 \(q\) 组，令这 \(q\) 组的 \(a\) 和余下的 \(n-q\) 组中的 \(b\) 相乘所得到的，从 \(n\) 组中选出 \(q\) 组的可能性总数为 \(\binom{n}{q}\)。
这样就可以推出杨辉三角的第 \(n+1\) 行全部数字是 \((a+b)^n\) 展开式的二项式系数一一对应的。
稍作拓展：
令 \(f(x,y)=(x+y)^n\)，求 \(f(x,y)\) 的展开式二项式系数之和。
实际上，它的展开式的第 \(i+1\) 项可以直接表示为 \(\binom{n}{i}\cdot x^{n-i}y^i\)，其中 \(0 \le i \le n\)。换言之，我们如果想要求其二项式系数之和 \(\sum_{i=0}^{n}\binom{n}{i}\)，就可以通过将 \(x=1,\,y=1\) 代入到 \(\sum_{i=0}^{n}\binom{n}{i}\cdot x^{n-i}y^i\) 中来计算。换言之，所求即为：\(f(1,1)=2^n\)。
注意到 \(2^n\) 还可以视作 \(n\) 位二进制数的总数，这仅仅是一个巧合吗？
0x01 推广公式
在那耸立的高岗黑岩之上，恶魔的秽语悄然响起：\(\sum_{i=0}^n m^i\cdot\binom{n}{i}=(m+1)^n\)
引证：\(\binom{n}{n-k}=\binom{n}{k}\)，这其实很好理解。\(\binom{n}{n-k}\) 表示从 \(n\) 个东西里挑出 \(n-k\) 个，剩下 \(k\) 个；\(\binom{n}{k}\) 表示从 \(n\) 个东西里挑出 \(k\) 个，剩下 \(n-k\) 个。但是实际上，每一种挑出来的组合，必然对应且仅对应一组被剩下了的组合；所以，剩下 \(k\) 个也可以理解为挑出来了 \(k\) 个，只不过挑出来它们是为了把它们剩下。当然最直观的证明方法是用组合数定义，展开阶乘，把相同的项消掉，再重新写成阶乘、转换为组合数的表达形式。
是的，这里有一个二项式定理的推广公式，就是 \(\sum_{i=0}^n m^i\cdot\binom{n}{i}=(m+1)^n\)，其中 \(m,n \in \mathbb{Z^+}\)。现在我们要谈论的是该如何去简单理解这个公式。
我们先看看 \(m=1\) 的情况，这也就是上一个标题最后所给出的情况：\(\sum_{i=0}^{n}\binom{n}{i}=2^n\)。为了简单地解释它，我们暂时还是需要用到杨辉三角：小明移动 \(n\) 次后，一定会来到第 \(n+1\) 行的某一个数所在的位置。而他想要移动 \(n\) 次，就需要做出 \(n\) 个选择，每次都必须在向左下和向右下中二选其一。所以，总的可能数为：\(2^n\)，这也就是推广公式的右手侧。而左手侧所表示的正是小明走到第 \(n+1\) 行的每一个数的可能之和，所以自然也就等于 \(2^n\)。
那么，对这种思考方式稍加抽象，我们可以用二进制数的思想来考虑：有一个 \(n\) 位二进制数，它的第 \(k\) 位为 \(1\) 则表示小明第 \(k\) 次选择了向左下，为 \(0\) 则表示选择了向右下。再进一步抽象，把小明完全剥离出去，就会变成：列举出所有的 \(n\) 位二进制数，这些二进制数当中，有且仅有 \(k\) 个 \(1\) 的数的数量就是 \(\binom{n}{k}\)（这等价于从 \(n\) 位里挑出 \(k\) 位，令它们为 \(1\)，其余位为 \(0\)）。这种方式，在数学上更容易说明 \(m=1\) 时该式子成立。
如果 \(m > 1\) 呢？我们该怎样推广这个式子？其实也很简单，只需要对应地用 \(k\) 进制数的思想就好了。
例如，令 \(m=2\)：列举出所有的 \(n\) 位三进制数，共 \(3^n\) 个。这些三进制数当中，有且仅有 \(k\) 位不是 \(0\) 的数的数量就是 \(\binom{n}{k}\)（这等价于从 \(n\) 位里挑出 \(k\) 位，令它们为 \(1\) 或 \(2\)，其余位为 \(0\)）。注意到，每一个非 \(0\) 位都有两种选择：\(1\) 或 \(2\)。所以一个 \(n\) 位三进制数中如果有 \(n-k\) 个 \(0\)，剩下的 \(k\) 位就会有 \(2^k\) 种可能性；而“ \(n\) 位三进制数中有 \(n-k\) 个 \(0\)”本身已经有 \(\binom{n}{n-k}=\binom{n}{k}\) 种可能，二者相乘正好就是 \(\binom{n}{k}\cdot 2^k\)。于是，所有的 \(\binom{n}{k}\cdot 2^k\) 相加，应该等于\(n\) 位三进制数的总数 \(3^n\)。
再往下其实也不用推了，思路是一样的。