杨辉三角与排列组合

· · 个人记录

前置知识

\begin{matrix} A^m_n= \dfrac{n!}{(n-m)!} \\\\ \dbinom{n}{m}=C^m_n=\dfrac{A^m_n}{A^n_n}=\dfrac{n!}{(n-m)! \cdot m!} \end{matrix}

1. 从二项式定理说起

在初中的时候，我们就知道了这个公式：

(a+b)^2=a^2+2ab+b^2

不过，这个公式的一般形式 (a+b)^n 怎么求呢？

先把这个式子展开：

(a+b)^n=(a+b)\cdot (a+b) \cdots (a+b)

总共有 n 个 (a+b) , 展开后每一个单项式的次数显然是 n 。又因为整个式子中只有 a 和 b , 所以每个单项式中只有 a 和 b 这两种字母。

综上，每个单项式一定是这种形式：

a^kb^{n-k} \ \ (0 \le k \le n)

其实你也可以把它看成有 n 个有着 a 和 b 的盒子，每个盒子里面抽一个字母，然后将它们拼起来。

那么我们再来看看 a^kb^{n-k} 这个单项式的系数，也就是从 n 个 (a+b) 中选出 k 个 a 和 (n-k) 个 b 的方案数，也就是 \dbinom{n}{k} 。

接着，我们就可以得到 牛顿二项式定理 了：

(a+b)^n= \sum_{i=0}^{n} \dbinom{n}{i}a^i b^{n-i}

2. 组合数的递推式

在这一节，我们将会证明这个公式：

\dbinom{a}{b}=\dbinom{a-1}{b-1}+\dbinom{a-1}{b}

先来看看 \dbinom{a}{b} 的含义。它指的就是从 a 个数里面选出 b 个数的方案数。

我们可以这样分类讨论：

  1. 不选最后一个数，那么就要从 (a-1) 个数里面选出 b 个，即 \dbinom{a-1}{b} 。

  2. 选最后一个数，那么只要从 (a-1) 个数里面选 (b-1) 个数即可，那么就是 \dbinom{a-1}{b-1} 。

由加法原理可以得到

\dbinom{a}{b}=\dbinom{a-1}{b-1}+\dbinom{a-1}{b} \begin{matrix} \dbinom{a-1}{b-1}+\dbinom{a-1}{b} \\\\ = \dfrac{(a-1)!}{(a-b)! \cdot (b-1)!}+\dfrac{(a-1)!}{(a-b-1)!\cdot b!} \\\\ = \dfrac{(a-1)(a-2)\cdots(a-b+1)}{(b-1)!}+ \dfrac{(a-1)(a-2)\cdots(a-b)}{b!} \end{matrix}

提公因式 (a-1)(a-2)\cdots(a-b+1)，得原式

\begin{matrix} =(a-1)(a-2)\cdots(a-b+1) \cdot ( \dfrac{1}{(b-1)!} +\dfrac{a-b}{b!} )\\\\ = (a-1)(a-2)\cdots(a-b+1) \cdot ( \dfrac{b}{b!} +\dfrac{a-b}{b!} )\\\\ = (a-1)(a-2)\cdots(a-b+1) \cdot \dfrac{a}{b!}\\\\ = \dfrac{a(a-1)(a-2)\cdots(a-b+1)}{b!}\\\\ = \dfrac{a!}{(a-b)! \cdot b!}=\dbinom{a}{b} \end{matrix}

3. 杨辉三角与排列组合

先将杨辉三角集体左移，放在一张表格上。（ 注意表格的开头是 0 ）

我们设表格中第 x 行，第 y 列的数是 P(x,y) 。

首先，由杨辉三角本身可以得到 P(a,b)=P(a-1,b)+P(a-1,b-1) 。

接着，我们可以发现一个比较神奇的事实：P(a,b)=\dbinom{a}{b} 。

证明：

显然可得 P(1,1)=\dbinom{1}{1} 。

发现杨辉三角的递推式

P(a,b)=P(a-1,b)+P(a-1,b-1)

与组合数的递推式

\dbinom{a}{b}=\dbinom{a-1}{b-1}+\dbinom{a-1}{b}

形式是相同的，由此可以判断下列等式成立：

P(a,b)=\dbinom{a}{b}

证明完毕。

我们再来回顾一下二项式定理：

(a+b)^n= \sum_{i=0}^{n} \dbinom{n}{i}a^i b^{n-i}

将它的系数从前往后列出来：

\dbinom{n}{0}, \ \dbinom{n}{1} , \ \dbinom{n}{2} , \ \cdots , \ \dbinom{n}{n}

由 P(a,b)=\dbinom{a}{b} 可以得到：

这些数字刚好就是杨辉三角第 n 行从前往后的数字！

至此，关于杨辉三角和排列组合的关系，我们已经通过严谨的数学证明得到了。

4. Exercise

首先可以 O(nm) 用杨辉三角预处理出所有的组合数。

接着可以用 O(nm) 二维前缀和来求出满足条件的数字个数。

最后对于每组数据 O(1) 直接输出答案。

总时间复杂度：O(nm+t) 。