0x00 二项式定理

写在最前:\(\mathrm{C}_n^k=\binom{n}{k}=\frac{n!}{(n-k)! \cdot k!}\)

0x00.1 杨辉三角

前情提要:一种特殊的输出杨辉三角的方法

1
2
3
4
5
6
7
8
      1               (a+b)**0 = 1
/ \
1 1 (a+b)**1 = a+b
/ \ / \
1 2 1 (a+b)**2 = a² + 2ab + b²
/ \ / \ / \
1 3 3 1 (a+b)**3 = a³ + 3a²b + 3ab² + b³
... ...

不难发现,杨辉三角每一行的数字正好就是 \((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\)

再往下其实也不用推了,思路是一样的。

来源:https://blog.jiejiss.com/