跳至内容
Topos Uranos
中文 (中国)

初等组合学与二项式定理

摘要

本课研究不逐一列举就能数出有限集合元素个数的初等方法。课中借助双射定义有限集合的元素个数，从这一定义出发证明加法原理和乘法原理，由它们推出全排列、选排列和组合的个数，并定义二项式系数，其对称性和帕斯卡法则既用计数也用计算加以证明。随后把这些系数排成杨辉三角（帕斯卡三角），用归纳法证明推广了乘法公式的二项式定理，并把它应用于幂的展开、系数的求解和数值近似。本课是专讲自然数的单元中最后一节讲授内容的课，该单元以总结与挑战一课收尾。

学习目标

  1. 运用加法原理和乘法原理进行不列举的计数，当一次选择的各项条件相互干扰时分情况讨论。
  2. 区分全排列、选排列和组合，并借助阶乘计算它们的个数。
  3. 用计数和计算两种方法证明二项式系数的性质，并用它们构造杨辉三角。
  4. 证明二项式定理，并把它应用于幂的展开、系数的计算和幂的近似。

计数原理

只要有限集合可以逐个元素地走遍，数出它的元素就是算术中最基本的运算。然而，当元素是完成一次复合选择的方式时，例如把十本书排在书架上，或者从三十人中选出三名代表，逐一列举就变得行不通，个数要通过把选择分解为若干部分或若干阶段来求得。整个初等组合学建立在两条原理之上，它们都从「计数」含义的精确定义出发加以证明。

数出一个集合的元素，就是给它们编号：给从 11 到 nn 的每个数指派一个元素，既不重复也不遗漏。称集合 AA 有 nn 个元素（nn 为自然数），如果存在从集合 {1,2,…,n}\{1, 2, \ldots, n\} 到 AA 的双射，即一个把不同的数映到不同的元素、并取遍 AA 的所有元素的函数；空集有 00 个元素；一个集合称为有限的，如果它是空集，或者有 nn 个元素（nn 为某个自然数）。双射、双射的复合及其逆在关于集合、关系与函数的一课中研究。

不加证明的事实（元素个数）。我们不加证明地承认：有限集合的元素个数是确定的，即一个集合不可能同时有 mm 个元素和 nn 个元素，只要 m≠nm \neq n。还承认：有限集合的每个子集都是有限的。

这两个事实都用对 nn 的归纳法证明；第一个事实本质上就是抽屉原理：不存在这样的函数，它把 n+1n + 1 个数（即 {1,…,n+1}\{1, \ldots, n + 1\} 中的数）映到 {1,…,n}\{1, \ldots, n\} 中互不相同的数。它们的证明冗长，又不提供后面用得着的思想，因此予以承认。没有第一个事实，「元素个数」这一说法就没有意义，而组合证明以两种方式计数同一个集合，也就无法断定两个结果相等。

命题加法原理

若 AA 有 mm 个元素，BB 有 nn 个元素，且 AA 与 BB 没有公共元素，则 A∪BA \cup B 有 m+nm + n 个元素。图中以 m=3m = 3 和 n=2n = 2 的情形展示证明过程。

证明

  1. A={f(1),…,f(m)},B={g(1),…,g(n)}A = \{f(1), \ldots, f(m)\}, \quad B = \{g(1), \ldots, g(n)\}

    由假设，存在双射 ff（从 {1,…,m}\{1, \ldots, m\} 到 AA）和另一个双射 gg（从 {1,…,n}\{1, \ldots, n\} 到 BB）：每个集合的元素都已无重复地编号。

  2. i≤m ∨ i=m+j,1≤j≤n\dato{p}{i \leq m \ \vee \ i = m + j, \quad 1 \leq j \leq n}

    由三歧性，每个数 ii（从 11 到 m+nm + n）满足 i≤mi \leq m 或 i>mi > m；在第二种情形，由序的定义，i=m+ji = m + j，这里 jj 是某个自然数，由加法的消去律它是唯一的，并且由加法的单调性有 j≤nj \leq n。

  3. h(i)=f(i),h(m+j)=g(j)\dato{h}{h(i) = f(i), \quad h(m + j) = g(j)}

    我们定义 hh（在 {1,…,m+n}\{1, \ldots, m + n\} 上）：前 mm 个数按 ff 的方式编号，其后的 nn 个数按 gg 的方式编号。

  4. A∩B=∅→f(i)≠g(j)A \cap B = \emptyset \rightarrow \resaltar{f(i) \neq g(j)}

    函数 hh 把不同的数映到不同的元素：同属一部分的两个数，是因为 ff 和 gg 如此；分属两部分的两个数，是因为它们分别映到 AA 的一个元素和 BB 的一个元素，而这两个集合没有公共元素。

  5. A∪B={h(1),…,h(m),h(m+1),…,h(m+n)}A \cup B = \{h(1), \ldots, h(m), h(m + 1), \ldots, h(m + n)\}

    函数 hh 取遍并集的所有元素：AA 的元素是 ff 的值，BB 的元素是 gg 的值。

  6. h:{1,…,m+n}→A∪Bh : \{1, \ldots, \resaltar{m + n}\} \to A \cup B

    因此，hh 是一个双射（从 {1,…,m+n}\{1, \ldots, m + n\} 到 A∪BA \cup B），并集有 m+nm + n 个元素。若其中一个集合是空集，结论是显然的。

对部分的个数用归纳法，这一原理可以推广到任意有限个两两没有公共元素的集合：A1,…,ArA_1, \ldots, A_r 的并集（各有 n1,…,nrn_1, \ldots, n_r 个元素）有 n1+⋯+nrn_1 + \cdots + n_r 个元素，因为前 r+1r + 1 个集合的并集就是前 rr 个集合的并集与最后一个集合的并集，而最后一个集合与它们没有公共元素。由这一原理可以推出第二条原理，它计数分阶段进行的选择。

命题乘法原理

如果一次选择分两个阶段完成，第一阶段有 mm 种方式，而无论第一阶段如何选择，第二阶段都有 nn 种方式，那么整个选择可以用 m⋅nm \cdot n 种方式完成。图中把每个完整的选择画成一个点，放在其第一阶段所对应的行中，取 n=4n = 4。

证明

  1. E=E1∪E2∪⋯∪EmE = E_1 \cup E_2 \cup \cdots \cup E_m

    我们按第一阶段把完整的选择分组：共有 mm 个类 E1,…,EmE_1, \ldots, E_m，彼此没有公共元素，每个类有 nn 个元素，即补全该第一阶段选择的 nn 种方式。

  2. 1⋅n=n1 \cdot n = n

    对类的个数 mm 用归纳法。起始步：若 m=1m = 1，所有选择都在 E1E_1 中，它有 nn 个元素。

  3. E1∪⋯∪Ek,k⋅n\dato{h}{E_1 \cup \cdots \cup E_k}, \quad k \cdot n

    归纳步：假设 kk 个两两没有公共元素的类（每个类有 nn 个元素）的并集有 k⋅nk \cdot n 个元素。

  4. (E1∪⋯∪Ek)∪Ek+1,k⋅n+n(E_1 \cup \cdots \cup E_k) \cup \resaltar{E_{k + 1}}, \quad k \cdot n + \resaltar{n}

    k+1k + 1 个类的并集就是前 kk 个类的并集与最后一个类的并集，而最后一个类与它们没有公共元素；由加法原理，它有 k⋅n+nk \cdot n + n 个元素。

  5. k⋅n+n=(k+1)⋅nk \cdot n + n = \resaltar{(k + 1) \cdot n}

    由引理 S(k)⋅n=k⋅n+nS(k) \cdot n = k \cdot n + n（在关于运算的一课中证明乘法交换律时已经证明），这个数就是 (k+1)⋅n(k + 1) \cdot n。

  6. E1∪⋯∪Em,m⋅nE_1 \cup \cdots \cup E_m, \quad \resaltar{m \cdot n}

    由数学归纳原理，mm 个类的并集有 m⋅nm \cdot n 个元素：整个选择可以用 m⋅nm \cdot n 种方式完成。在图中，3⋅4=123 \cdot 4 = 12。

同样，对阶段数用归纳法，乘法原理可以推广到任意有限个阶段：一次分 rr 个阶段的选择，各阶段分别有 n1,n2,…,nrn_1, n_2, \ldots, n_r 种完成方式，那么这次选择可以用 n1n2⋯nrn_1 n_2 \cdots n_r 种方式完成。例如，在关于进位记数制的一课所研究的十进制中，三位数共有 9⋅10⋅10=9009 \cdot 10 \cdot 10 = 900 个，因为首位数字不能是 00，而另外两位可以任取。需要注意，乘法原理要求每个阶段的选项个数不依赖于此前的选择，尽管选项本身可以依赖；若这一条件不成立，就分成若干使它成立的情形，再用加法原理把各情形的结果相加。

一次选择的相继阶段可以用树形图表示：从起点（即根）引出的枝数等于第一阶段的选项数；从每根枝的端点引出的枝数等于第二阶段的选项数，依此类推。从根到一个最终端点（即叶）的每条路线都是一个完整的选择，而乘法原理不必画出叶就能数出它们。

例题用数字 11、22 和 33 组成的三位数

数出用数字 11、22 和 33 不重复地能写出的三位数，并与允许重复时得到的三位数比较。

证明

  1. 3\resaltar{3}

    首位数字可以是三个数字中的任何一个：从根引出三根枝。

  2. 3⋅2=63 \cdot \resaltar{2} = \resaltar{6}

    选定首位数字后，无论首位是什么，第二位都还剩两个数字可选：每根枝分成两根，由乘法原理，共有六种可能的开头。

  3. 3⋅2⋅1=6\dato{p}{3 \cdot 2 \cdot \resaltar{1} = \resaltar{6}}

    第三位只剩一种可能，因此每种开头都只能以唯一的方式补全。

  4. 123, 132, 213, 231, 312, 321123, \ 132, \ 213, \ 231, \ 312, \ 321

    从根读起，树的叶就是所求的六个数，按从小到大排列。

  5. 3⋅3⋅3=27\resaltar{3 \cdot 3 \cdot 3} = \resaltar{27}

    如果允许数字重复，每个阶段都有三个选项，树的叶比不允许重复时多得多。