数学复健6-组合证明
序章
第五章我们学习了有限集、排列组合、二项式定理等知识。通过构造有限对象并比较它们的数量来证明恒等式或存在性结论的方法，叫作组合证明。
若有限集 $A$ 与 $B$ 之间存在双射，就有：
$$ |A|=|B|.$$
通过构造这种一一对应来计算对象数量，叫作双射计数。
选择同一个有限集 $S$，用两种不同方法计算 $|S|$，再令两个结果相等，叫作双重计数。
若物品集合 $P$ 中的每个对象都被放入容器集合 $H$ 的一个容器，可以用函数：
$$ f:P\to H$$
表示。当 $|P|>|H|$ 时，$f$ 不可能是单射，因此至少两个物品进入同一容器。这叫作鸽巢原理。
这些定义会在正文中分别展开
小故事
一座剧院散场后，经理想知道今晚究竟来了多少位观众，他并没有一个个数人头，而是数了入口处回收的票根，假设一个观众对应一张票根、一张票根对应一个观众，那么，观众 $\longleftrightarrow$ 票根。票根比人头好数，经理没有改变观众数量，而是把难数的对象翻译成了容易数的对象
直接数不清 $\longrightarrow$ 换一个好数的对应对象
恒等式看不懂 $\longrightarrow$ 从两边数同一集合，看看能否能对上
不知道对象在哪里 $\longrightarrow$ 先证明它必然存在
组合证明的力量，常常来自重新决定“我们究竟在数什么”。
双射计数
把难数的对象翻译成容易数的对象
定义
设 $A,B$ 是有限集。
若构造出双射：
$$ f:A\to B$$
就得到：
$$ |A|=|B|.$$
通过建立这种一一对应来计算 $|A|$，叫作双射计数。
双射证明必须检查：
- 每个 $A$ 中对象都能被翻译；
- 不同对象不会被翻译成同一个结果；
- 每个 $B$ 中对象都能反向恢复。
例子
子集数量
求一个集合 $X$ 有多少个子集
我们可以用一个长度为 $n$ 的二进制串给子集做唯一编码，如果某个元素在子集中，就设为1，否则就设为0，通过数二进制串有多少种，得到集合有多少子集
设：
$$ X=[n]=\{1,2,\cdots ,n\}$$
对每个子集 $S\subseteq X$，定义长度为 $n$ 的二进制串：
$$ b_1b_2\cdots b_n,$$
其中：
$$ b_i= \begin{cases} 1,&i\in S,\\ 0,&i\notin S. \end{cases}$$
这个对应是双射：
$$ S \longleftrightarrow \{0,1\}^n.$$
右侧有 $2^n$ 个二进制串，所以：
$[n]$ 的子集总数为 $2^n$
单调格路
单调格路问题，在整数坐标平面上，从 $(0,0)$ 走到 $(a,b)$ 点，如果每次只能向上 $U=(0,1)$ 或向右走一步 $R=(1,0)$，请问有多少种走法
要从 $x=0$ 走到 $x=a$，一共需要 $\boldsymbol{a}$ 次向右 $R$
要从 $y=0$ 走到 $y=b$，一共需要 $\boldsymbol{b}$ 次向上 $U$
总步数为 $a+b$ 步，其中恰有 $a$ 步为 $R$，我们可以判断到底在哪一步我们执行 $R$
选择哪些位置放 $R$，就唯一决定整条路（也等价于选择在哪些位置放 $U$）。
因此：
$$ \text{Count} = \binom{a+b}{a} = \binom{a+b}{b}$$
几何路线被翻译成了位置选择。
双重计数
对于一些比较复杂的恒等式，我们难以通过纯符号直接推导，如果我们可以构造出一个组合对象，用两种办法数这个对象，而且这两种办法正好是恒等式左右两边，那么我们就可以证明这个恒等式成立
定义
选择一个有限集合 $S$，用两种不同方法计算 $|S|$，再令两个结果相等，这种证明方法叫作双重计数。
基本结构是：
$$ |S| = \text{Count_1} = \text{Count_2}$$
因此得到一个恒等式。
这本质其实是一种证明方法。
例子
带标记的子集，对于一个集合 $[n]$，这个集合的某个子集我们叫做 $A$，我们从子集 $A$ 中挑选一个元素 $a$ 打上标记，我们要数有多少种带标记的子集
设 $n\geq1$，定义集合：
$$ S= \{(A,a)\mid A\subseteq[n],\ a\in A\}$$
一个元素 $(A,a)$ 表示：
- 先选择一个子集 $A$；
- 再在 $A$ 中标记一个元素 $a$。
第一种数法：先看子集大小
若：
$$ |A|=k$$
那么从 $[n]$ 中选择 $A$ 有 $\binom nk$ 种
从 $A$ 再选择标记元素 $a$ ，有 $k$ 种
所以：
$$ |S| = \sum_{k=0}^{n} k\binom nk$$
第二种数法：先选标记元素
先从 $[n]$ 中选择元素 $a$，有 $n$ 种选法
$$ a\in[n]$$
剩余 $n-1$ 个元素各自决定是否进入 $A$，有 $2^{n-1}$ 种选法
所以：
$$ |S|=n\,2^{n-1}.$$
结论
两种计数相等：
$$ \sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$$
当然这个证明完全可以通过二项式定理纯符号推导出来
双重计数的设计方法
看到一个求和恒等式时，可以问：
- 每个求和项在数什么对象？
- 求和指标 $k$ 是否表示一种分类？
- 能否先选择另一个部分？
- 能否把整个表达式解释成同一个有限集合的大小？
代数恒等式可能由计算得到。
双重计数则进一步解释：
两边相等，是因为它们在数同一批对象
鸽巢原理
把11个小球放进10个盒子里，那么至少有一个盒子里有至少2个小球
基本形式
设 $P$ 是物品集合，$H$ 是容器集合。
把每个物品放入一个容器，可以表示为函数：
$$ f:P\to H.$$
如果：
$$ |P|>|H|,$$
那么 $f$ 不可能是单射。
因此存在两个不同物品 $p_1,p_2\in P$，满足：
$$ p_1\neq p_2 \qquad f(p_1)=f(p_2)$$
这叫作鸽巢原理。
反证法证明
假设每个容器至多放一个物品。
那么放入 $|H|$ 个容器的物品数至多为：
$$ |H|$$
但实际物品数满足：
$$ |P|>|H|$$
矛盾
所以至少有一个容器包含两个或更多物品。
例子
相同余数问题，选择任意 $n+1$ 个整数，每个整数除以正整数 $n$ 的余数只能是：
$$ 0,1,\ldots,n-1$$
余数类别只有 $n$ 个
把每个整数放入“它的余数”对应的容器。
由鸽巢原理，至少两个整数具有相同余数（容器尺寸 $n-1$，物品数量为 $n$）
若它们是 $a,b$，则：
$$ a\bmod n=b\bmod n.$$
于是：
$$ n\mid(a-b)$$
于是我们得到：
有限余数类别 $\longrightarrow$ 两个数必然相撞 $\longrightarrow$ 差具有整除性质
我们经常可以在数论中用到鸽巢原理
广义鸽巢原理
对实数 $x$，大于或等于 $x$ 的最小整数叫作 $x$ 的上取整，记作：
$$ \lceil x\rceil$$
设 $N\in\mathbb N$ 且 $m\geq1$。
若把 $N$ 个物品放入 $m$ 个容器，则至少一个容器包含：
$$ \left\lceil\frac Nm\right\rceil$$
个物品，这叫作广义鸽巢原理。
广义鸽巢原理只负责证明存在，不负责寻找。存在性证明 $\neq$ 构造算法
递归计数
本类任务的核心，是先看最后一个对象是怎么构造的
递归计数的共同结构
递归计数通常按对象的最后一步或第一步分类：
$$ a_n \longrightarrow \begin{cases} a_{n-1} \\ a_{n-2} \\ \cdots \end{cases}$$
只要这些生成方式：
- 覆盖全部对象；
- 彼此不重叠；
就能把分类数相加。
例子
铺砖问题
用两种砖（长度为1和长度为2）铺满长度为 $n$ 的一维走廊，请问有多少种铺法
设铺法数为：
$$ a_n$$
对 $n\geq2$，观察最后一块砖：
若最后一块长度为 $1$，前面是长度 $n-1$ 的铺法，共 $a_{n-1}$ 种
若最后一块长度为 $2$，前面是长度 $n-2$ 的铺法，共 $a_{n-2}$ 种
两类互不相交，所以：
$$ a_n=a_{n-1}+a_{n-2}$$
初值为：
$$ a_0=1, \qquad a_1=1$$
其中 $a_0=1$ 表示长度为 $0$ 的走廊有一种空铺法，即不放任何砖。
因此这是一个斐波那契数列问题
$$ a_n=F_{n+1}$$
其中 $F_n$ 是 Fibonacci 数列
没有连续两个 $1$ 的二进制串
设 $b_n$ 表示长度为 $n$、且不含连续子串 $11$ 的二进制串数量。
对 $n\geq2$，按开头分类：
- 以 $0$ 开头，后面可接任意合法的长度 $n-1$ 串；
- 以 $1$ 开头，则下一位必须是 $0$，后面可接任意合法的长度 $n-2$ 串。
所以：
$$ b_n=b_{n-1}+b_{n-2}$$
初值：
$$ b_0=1, \qquad b_1=2.$$
因此：
$$ b_n=F_{n+2}.$$
