组合学 [4]

发表于 更新于 分类于 ,
本文字数: 4k 阅读时长 ≈ 25 分钟

本篇内容

  • 括号化（Parenthesization）
  • 卡特兰数（Catalan Number）
  • 集合的组合
    • 普通组合
    • 重组合
    • 多重集合的组合

括号化

1. 概念

括号化（Parenthesization）是指在一串数学表达式中添加括号，以明确运算顺序的过程。

在数学表达式中，括号的使用可以改变运算顺序，进而影响最终的计算结果。因此，括号化的目的是为了避免歧义，确保表达式的计算顺序是正确的。

假设 ∗* 是一个任意运算符，并且 ∗* 能同时表示不同的运算符[1]，对于一个长度为 n+1n+1 的数列 a1, a2, …, an,an+1a_1,\ a_2,\ \dots,\ a_n, a_{n+1}，我们可以在其中添加括号，使得表达式的计算顺序是正确的。

例如，对于 n=3n = 3 的数列 a1,a2,a3,a4a_1, a_2, a_3, a_4，有以下 55 种不同的括号化方式：
((a1∗a2)∗a3)∗a4((a_1 \ast a_2) \ast a_3) \ast a_4

(a1∗a2)∗(a3∗a4)(a_1 \ast a_2) \ast (a_3 \ast a_4)

(a1∗(a2∗a3))∗a4(a_1 \ast (a_2 \ast a_3)) \ast a_4

a1∗((a2∗a3)∗a4)a_1 \ast ((a_2 \ast a_3) \ast a_4)

a1∗(a2∗(a3∗a4))a_1 \ast (a_2 \ast (a_3 \ast a_4))

这些括号化方式的目的是为了明确运算的顺序，以确保计算的结果是正确的。

在数学中，有一类问题是求解括号化问题的方案数，即给定数列，计算可以构造的不同的括号化方式的数量。这类问题的答案被称为 卡特兰数（Catalan number） ，记为 CnC_n。

2. Catalan Number

在组成元素为 a1⋅a2⋅⋯⋅an⋅an+1a_1 \cdot a_2 \cdot \cdots \cdot a_n \cdot a_{n+1} 的所有不同括号化方案构成的集合中，记为 An\mathcal{A}_n，以及由 00 和 11 组成的长为 2n+12n+1 的序列 x=x1x2⋯x2n+1x = x_1x_2 \cdots x_{2n+1} 的集合中，满足 xx 中 11 的数量恰好为 nn，并且 xx 的任何前缀中 11 的数量都小于 00 的数量，记为 Cn\mathcal{C}_n。存在一个双射 f:An→Cnf: \mathcal{A}_n \rightarrow \mathcal{C}_n，使得 Cn\mathcal{C}_n 中的元素对应于下面方程组的所有解：

{x1+x2+⋯+x2n+1=nx1+x2+⋯+xi<i2,i=1,2,…,2n+1xi∈{0,1},     i=1,2,…,2n+1\left\{\begin{aligned} &x_1 + x_2 + \cdots + x_{2n+1} = n \\ &x_1 + x_2 + \cdots + x_i < \frac{i}{2}, \qquad i = 1,2,\ldots,2n+1 \\ &x_i \in \{0,1\}, \qquad \qquad \qquad \ \ \ \ \ i = 1,2,\ldots,2n+1 \end{aligned}\right.

特别地，记 CnC_n 为上述方程组的解的数量，则 Cn=∣An∣=∣Cn∣=(2n)!n!(n+1)!C_n = |\mathcal{A}_n| = |\mathcal{C}_n| = \frac{(2n)!}{n!(n+1)!}。

这个公式的证明我暂时搁置，因为要考试了，一下是证明的一部分内容

此外，记由一个 2n+12n+1 阶单位三角形的左下角 (1,1)(1,1) 出发，在保持路径位于 xx 轴上方的前提下，前进 nn 步到达右下角 (2n+1,1)(2n+1,1) 的所有 T−routesT-routes 构成的集合为 Tn\mathcal{T}_n。

集合的组合

1. 概念

在组合学中，组合是指从一个元素集合中选择特定数量的元素，无序的排列组合成子集。组合的概念是用于研究离散结构的一种基本工具，也是计数学中的一个分支。

和排列相同，有两种不同类型的组合，不重复的和含重复的：

  1. nn 个元素的 rr 元组合，指的是从 nn 个元素中选择 rr 个元素构成的无序子集。例如，从 {1,2,3,4,5}\{1,2,3,4,5\} 中选择 33 个元素的组合可以是 {1,2,3}\{1,2,3\}，{2,3,5}\{2,3,5\} 等等。
  1. nn 个元素的 rr 元重组合，指的是从 nn 个元素中选择 rr 个元素，可以重复选取同一个元素。例如，从 {1,2,3}\{1,2,3\} 中选择 22 个元素的组合（带重复）可以是 {1,1}\{1,1\}，{1,2}\{1,2\} 等等。

这两种组合概念在实际问题中都有广泛应用，例如排列组合问题、概率计算问题、统计学中的二项分布等等。组合的概念是计算数学、概率论、统计学等学科的重要基础，因此对组合的理解是非常有意义的。

2. 计算

i. 不重复的组合

对于有 nn 个元素集合的 rr 元组合（不重复）的数目为 (nr)\binom{n}{r}，即从 nn 个元素中选择 rr 个元素的不同组合数，其中

(nr)=n!r!(n−r)!\binom{n}{r}=\frac{n!}{r!(n-r)!}

要理解这个算式的来源，我们需要结合排序的概念。

假设我们要求一个nn 元素集合的 rr 元排序数量，我们有公式 n!(n−r)!\frac{n!}{(n-r)!} 。
这个公式意味着从集合中挑出 rr 个元素，并将他们排序的所有可能性；注意，我们在这里面的一个操作： 从集合中挑出 rr 个元素 。也就是说我们在计算排序的时候就已经隐形地计算了其组合的可能性。

那么，要利用这个性质求出单纯组合的可能性，我们需要剥离掉公式中的 顺序性 。

要做到这点，我们只用逆向思考，有 rr 个元素，如何求出这些元素的所有排序可能性，没错，就是 r!r! ，所以，我们只要对公式 n!(n−r)!\frac{n!}{(n-r)!} 除以 r!r! ，就能消除公式中的顺序性，得到组合的计算方法。

ii. 带有重复组合

对于有 nn 个元素集合的 rr 元重组合的数目为 (n+r−1r)\binom{n+r-1}{r}。

这个式子的来由我只简单提示一下

想象一个情形，你有 nn 个小球，你需要用 rr 根棒子来分隔这些球，把它们分成不同的组并且，我们允许有些组是空的，也就是两根棒子之间可以没有任何球。所有球都是一模一样的[2]，没有任何区别。请问我们总共有多少中分法？

3. 多重集合的组合

多重集合的组合是指从一个包含相同元素的集合中选择出一定数量的元素的所有可能情况。其中，每个元素可以出现多次，因此，可以用一个多重集合来表示这样的集合。

具体来说，对于 nn 元重集合 A={n1⋅a1, n2⋅a2, … nk⋅ak}A=\{n_1\cdot a_1,\ n_2\cdot a_2,\ \ldots\ n_k\cdot a_k\} 和一个整数rr，0≤r≤n0\leq r\leq n；rr 元组合是指从 AA 中选择出 rr 个元素的集合。其中，每个元素可以选择多次，因此，重集合的组合也可以被看作是一个多重集合，表示为 {x1⋅a1, x2⋅a2, … xk⋅ak}\{x_1\cdot a_1,\ x_2\cdot a_2,\ \ldots\ x_k\cdot a_k\}，其中 xix_i 表示元素 aia_i 被选择的次数，满足 0≤xi≤ni0\leq x_i\leq n_i，且 ∑i=1kxi=r\sum_{i=1}^k x_i=r。

需要注意的是，当多重集合的元素数量全部为 11 时[3]，rr 元组合可以看作是一个普通的组合。而当元素可以重复选择时，可以将其看作是一个包含无限个相同元素的多重集合。

  1. 1.例如在算式： x * y * z 中第一个 * 和第二 * 可以代表不同的运算符 ↩
  2. 2.这就意味着在同一个组内，所有的球都是一种 “重复” 元素。 ↩
  3. 3.这是多重集合的性质与普通集合没有什么区别 ↩