(涵盖第 13、14个讲义)

LN13

函数映射

• 函数的三种映射 给定集合 A 和 B，函数 f:A → B 把每个输入 a ∈ A 指向唯一的输出 f(a) ∈ B。如果不同的输入不会落在同一输出上，|A| ≥ |B|，称 单射 Injection；如果每个 B 里的元素都能被命中，|A| ≤ |B|，称 满射 Surjection；两者兼具称 双射 Bijection。双射意味着 |A| = |B|——可以把难数的集合 A 转换为好数的集合 B 来计数 |A|。
• “双射计数法” 步骤：①想一个更好数的集合 B；②构造映射 f:A → B；③论证 f 是双射（或者 “k-to-1”，后续补充）；④数 |B|（或用除法规则 |A|=k|B|，后续补充）。

除法规则 (Division Rule)

• 除法规则： 若 f: A → B 是 k-to-1（每个 b ∈ B 都恰被 k 个 A 中的元素命中），则 |A| = k·|B|，从而 $|B|=\dfrac{|A|}{k}$。这拓展了上述的双射情形（k=1）。

四个常见模型

1. 幂集基数 (Cardinality of Power Set) 回忆上半学期的知识：幂集 = 包含某一集合全部子集的集合；基数 = 集合包含的元素个数。假设集合 |M| = k。 A：幂集的元素 B： k 位二进制数，用 0 | 1 表示 M 中各个元素是否在当前子集中，共有 2^k 个可能的数 因为 B 覆盖所有子集情况，A → B 为双射，|A| = |B| = 2^k。

   类似的，基数为 m 的子集个数可以理解排列数到组合数的 m!·(k-m)!-to-1 映射，得到的结果阐释了组合数的由来：$\frac{k!}{m!·(k-m)!}= {k \choose m}$

2. 环形排列 (Circular Permutation) A：n 个元素的线性排列：P(n) = n!

   

   B：n 个元素的环形排列：需要考虑封闭队列没有首尾导致的“旋转等价冗余” ，比如 ABCD、BCDA、CDAB、DABC 四个是旋转等价的。普遍的，n 个元素排列就有 n 个不同元素在 A 中作为排头的冗余，故而 A → B 为 n-to-1。 所以根据除法规则， $|B|=\dfrac{n!}{n}=(n-1)!$。

3. 相同棋子的排序冗余 把象棋中 “两车不互吃的摆法” 映射到四元组 (r(1),c(1),r(2),c(2)) 且 $r(1)\neq r(2),c(1)\neq c(2)$。注意：互换“哪辆车叫 1 还是 2”应当得到同一布局，所以 A → B 为 2!-to-1： $|B|=\dfrac{|A|}{2!}=\dfrac{8\cdot8\cdot7\cdot7}{2}=1568$。

4. 隔板法 (Stars-and-Bars Method) 的数学化 从五个种类选一打 (12 个) 甜甜圈：表示为二进制数。 A：用四个 1 分割出五段有序空间，其中填入 0 作为这种甜甜圈要几个，形成的 16-bit 二进制数代表一种选择。比如对于五元组 (choco, icing, plain, glazed, crème)，1100010000010000 表示三个原味的、五个蘸糖的、四个奶油的 B：五个种类选一打 因为 A 覆盖了所有可能，A → B 为双射，|B| = |A| = $16 \choose 4$ = 1820。

所以，所有隔板法都可以转化为二进制数来描述，其通解为：${隔板数+选择次数 \choose 隔板数}$=$C(0)+C(1) \choose C(1)$( C() 代表某个字符在二进制数中的出现次数)

练习题

• 12 个人分成人数相同的三组，并围着三个桌子坐下，有多少坐法？ $$\frac{12!}{(4!)^3·3!}\times((4-1)!)^3 =\frac{12!·(3!)^2}{(4!)^3}=1247400$$

  $$Takeaway:\ 对于一个\ n\ 排序，有\ k\ 个无序组\ I,排序数：{n!\over \prod_{k}|I_k|!}$$

卡塔兰数 (Catalan Number)

这里有四个看似不同的问题：

(A) 正方形网格从左下角到右上角，只能向右或向上，不越过对角线的走法有多少？ (B) Dyck-n 词 (含相同数量 x 和 y 的字符串，每个 y 之前的 x 数量必须大于 y 数量) 有多少种？ (C) n 对括号的合法配对方法有多少？ (D) 一笔能表示固定距离的上坡或下坡，画 n 笔能有多少种合理的山脉轮廓？

它们之间两两之前存在双射，因此“答案相同”，全部都符合卡塔兰数。

• 双射示例 把 (A)“右/上路径” 编码成含 n 个 x 与 n 个 y 的字符串，要求任何前缀中 x 的数不少于 y 的数，这正是 (B)Dyck-2n 词 的定义；把“(”映成 x、“)”映成 y，就变成了 (C)“合法括号串”。

• 反射法 (Reflection / Flipping) 证明 以 (A) 为例，先数从 (0,0) 到 (n,n) 的所有右上方法 $\binom{2n}{n}$；再把“越过对角线的路径”与“从 (0,0) 到 (n-1,n+1) 的路径”做双射：在 (0,0) 到 (n,n) 路径第一次穿过对角线处开始把之后所有步骤反转(右变成上，上变成右），就变成了(0,0) 到 (n-1,n+1) 的对应路径。因为不超出对角线的路径绝对无法走到 (n-1,n+1)，所以越过对角线的走法与(0,0) 到 (n-1,n+1)的所有走法 1-to-1 对应。

  

  双射：|(0, 0)→(n, n) Exceed| = |(0, 0)→(n-1, n+1) All| = $\binom{2n}{n+1}$

  $$Catalan(n)=\binom{2n}{n}-\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n}.$$

  这样就可以证明卡塔兰数。

LN14

Cardinality 基数

• CSC3001