Bijective Proof Probs 选做

题目：https://math.mit.edu/~rstan/bij.pdf。

题解：https://jeanyeh.github.io/course/Comb/text/BIJECTIVE PROOF PROBLEMS - SOLUTIONS.pdf。

---

4. 对于 $n\ge 2$，$n$ 的有序分拆中恰有偶数个偶数的方案是 $2^{n-2}$。

考虑把它和恰有奇数个偶数的一一映射，方法叫做对合，考虑分拆的最后一个元素，如果是 $1$ 把它和倒数第二个合并，否则把它拆出一个 $1$。

13. 对于 $n\ge 0$，$$\sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}=4^n$$

不会 Bijective Proof。

每条路径以最后一次触碰 $y=x$ 为界点，分成前后两半。通过容斥算后半的方案数。具体地说，考虑所有格路要么可以是前半，要么可以是后半，要么第一步以后往终点的连线穿过了 $y=x$（则是容易算的），要么可以类似卡特兰数的手法容斥。

14

不会。

19. $n\times m$ 的 01 矩阵中，每行、每列和均为奇数的方案数是多少？

若 $n,m$ 奇偶性不同，无方案。

否则，考虑最后一列和最后一行是“被定的”，所以答案是 $2^{(m-1)(n-1)}$。

21. 对于质数 $p$ 和正整数 $a$，$p|a^p-a$。

考虑所有 $[p] \mapsto[a]$，把循环同构作为等价类，刨除映射到同一个数，得证。

22. (a) 对于质数 $p$，$p^2|\binom{2p}{p}-2$。

考虑长为 $2p$ 和为 $p$ 的 01 序列，把前 $p$ 位和后 $p$ 位循环同构作为等价类，刨除前半全部相等，得证。

22. (b) $p>3$ 时，$p^3|\binom{2p}{p}-2$。

只有复杂的代数证明。

23. 对于质数 $p$，$p|(p-1)!+1$。

考虑围成一圈的 $p$ 个顶点连成回路，对于旋转不同构的来说一种情况会被算 $2p$ 次。否则只有 $p-1$ 种情况，得证。

66. 求证 $\dfrac{(2m)!(2n)!}{m!n!(m+n)!}$ 为整数。

$m=n=0$ 显然，我们接下来证明 $C(m,n)=\dfrac{(2m)!(2n)!}{2m!n!(m+n)!}$ 在其余情况下也是整数，它叫超级卡特兰数。

定义 2-Motzkin 路径是含有以下四种步的折线：$(1,1)$（上升）、$(1,-1)$（下降）、$(1,0)$（类型 A）、$(1,0)$（类型 B）。并且纵坐标恒非负。

定义 Dyck 路径是合法括号序列的折线化。

构造长为 $n-1$ 的 2-Motzkin 路和长为 $2n$ 的 Dyck 路间的双射：令首位为 $(1,1)$、末位为 $(1,-1)$。把上升、下降翻倍，把 A 换成 $(1,1),(1,-1)$，把 B 换成 $(1,-1),(1,1)$。

$C(m,n)$ 是所有长为 $m+n-2$ 的 2-Motzkin 路的权值和，权值定义为 $(-1)^{y_m}$，$y_m$ 指第 $m$ 步起点的横坐标。

要证明它，只需证明边界正确且递推正确。

边界：$C(1,n)$ 为卡特兰数。由上面的双射，显然。

递推：$4C(m,n)=C(m+1,n)+C(m,n+1)$。证明：考虑每条长为 $m+n-1$ 的 2-Motzkin 路的贡献，如果这一步是上升、下降，则贡献和为 $0$，否则会算 $4$ 次。

证毕。

---