最近颓废的一批，逼自己翻译点东西。
翻译自 BIJECTIVE PROOF PROBLEMS，部分表述有修改。
进度：28 / 249 (upd on 2021.2.27)
标记 & 注意事项
标记
- $\mathbb{P}$：正整数集。
- $[n]$：$n \in \mathbb{N}$ 时，指集合 ${1, 2, 3, \cdots, n}$。
难度
- [1]：简单题，比较显然。
- [2]：中等难度，有点困难。
- [3]：难。
- [u]：本题还未被解决。
- [?]：本题结论已知，但我不确定目前是否有组合意义下的证明。
- [*]：本题目前还没有组合意义下的证明。
不管如何，目前所有题目的结论均是已知的。
我们使用 + 与 - 来对题目进行更精细的评分、如 [3-] 表示比 [3] 简单一点。
注意事项
- 本文名为“双射法题目合集”，请避免使用归纳法，递推法，生成函数等其他方法。
- 如果你上来就想搞学术研究，以下为一些有趣的双射法题目（但是里面大多数题目都挺难的）：27, 28, 59, 107, 143, 118, 123, 125, 140, 148, 151, 195, 198, 215, 216, 217, 226, 235, 247。
1 基础组合数学 | Elementary Combinatorics
题 1 [1]
证明：$n$ 元集合的子集（subset）数为 $2^n$。
题 2 [1]
定义正整数 $n$ 的一个拆分（composition）为一个正整数序列 $\alpha = \left(\alpha_1, \alpha_2, \cdots, \alpha_k\right)$，其中 $\sum \alpha_i = n$。
证明：$n$ 的拆分个数为 $2^{n-1}$。
题 3 [2]
证明：$n$ 的所有拆分的元素个数之和等于 $(n+1) 2^{n-2}$。
题 4 [2-]
对于正整数 $n \geq 2$，证明：$n$ 的所有拆分里，含有偶数个偶数元素的拆分数量为 $2^{n-2}$。
题 5 [2]
给定正整数 $n, k$，分别计算满足以下条件的 $k$ 元组 $(S_1, S_2, S_3, \cdots, S_k)$ 的数目。其中 $S_i (1 \leq i \leq k)$ 是 $[n]$ 的子集：（换言之，这是三道独立的题目。但是解决它们的方法有异曲同工之妙。）
(a) $S_1 \subseteq S_2 \subseteq \cdots \subseteq S_k$。
(b) $S_i$ 两两不交（pairwise disjoint）。
(c) $S_1 \cap S_2 \cap \cdots \cap S_k = \varnothing$
题 6 [1]
令 $S$ 为任意 $n$ 元集合，定义 $\binom{S}{k}$ 为 $S$ 所有 $k$ 元子集的集合。定义 $\binom{n}{k} = |\binom{S}{k}|$。（其实我们只是把二项式系数在组合意义下定义了一遍。此时 $n, k \in \N$）
证明：
$$
k! \dbinom{n}{k} = n(n-1)(n-2) \cdots (n-k+1)
$$
题 7 [1+]
已知 $ \binom{x}{k} = \frac{x(x-1)(x-2) \cdots (x-k+1)}{k!}$。
证明：
$$
(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}
$$
原作者注. 等式左右侧均为关于 $x$ 和 $y$ 的多项式，若两个多项式 $P(x, y)$ 与 $Q(x, y)$ 在 $x, y \in \mathbb{N}$ 时有 $P(x, y) = Q(x, y)$ 恒成立，那么 $P(x, y)$，$Q(x, y)$ 这两个多项式相同。所以此处，证明原式在 $x, y \in \mathbb{N}$ 时成立就已足够。
题 8 [1]
令正数 $n, m \geq 0$，求：在 $n \times m$ 的网格里，每一步仅能向左、向上移动一格，从 $(0, 0)$ 走到 $(n, m)$ 有多少种走法？
题 9 [1]
对于 $n > 0$，证明：
$$
2 \dbinom{2n-1}{n} = \dbinom{2n}{n}
$$
题 10 [1+]
对于 $n \geq 1$，证明：
$$
\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0
$$
题 11 [1+]
对于 $n \geq 0$，证明：
$$
\sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k} = \binom{x+y}{n}
$$
题 12 [2-]
对于 $n \geq 0$，证明：
$$
\sum_{k=0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}
$$
题 13 [3]
对于 $n \geq 0$，证明：
$$
\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^{n}
$$
题 14 [3-]
令 $m = \min(a, b)$，证明：
$$
\sum_{i=0}^{m} \binom{x+y+i}{i} \binom{y}{a-i}\binom{x}{b-i} = \binom{x+a}{b}
$$
题 15 [3-]
对于 $n \geq 0$，证明：
$$
\sum_{k=0}^{n} \binom{n}{k}^2 x^k = \sum_{j=0}^{n} \binom{n}{j} \binom{2n-j}{n} (x-1)^j
$$
题 16 [3-]
给定 $n \geq 0$，证明：
$$
\sum_{i+j+k=n} \binom{i+j}{i} \binom{j+k}{j} \binom{k+i}{k} = \sum_{r=0}^{n} \binom{2r}{r}
$$
题 17 [?]
给定 $n \geq 0$，证明：
$$
\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}^3 = (-1)^n \frac{(3n)!}{n!^3}
$$
题 18 [3]
令 $f(n)$ 为剩余系 $\mathbb{Z}/n\mathbb{Z}$ 中，元素之和 $\bmod n = 0$ 的子集的个数（包括 $\varnothing$）。比如说，$f(5) = 8$，这 $8$ 个集合分别为 $\varnothing$，${0}$，${1, 4}$，${2, 3}$，${0, 1, 4}$，${0, 2, 3}$，${1, 2, 3, 4}$，${0, 1, 2, 3, 4}$。
证明：$n$ 为正奇数时，$f(n)$ 即为有 $n$ 个珠子的黑白项链在旋转变化下的等价类个数。
原作者注. $n$ 为奇质数时，本题非常容易。
题 19 [2-]
求：有多少个 $m \times n$ 的 0-1 矩阵，满足矩阵的每一行，每一列都有奇数个 1？
题 20 (a) [1-]
给定 $k, n \geq 1$。证明：
满足 $1 \leq a_i \leq k$，且 $a_i \neq a_{i+1} (1 \leq i < n)$ 的序列 $(a_1, \cdots, a_n)$ 的数量为 $k(k-1)^{n-1}$。
题 20 (b) [2+]
题 20 (a) 中其他条件不变，再限定 $a_1 \neq a_n$，则满足条件的序列数量为：
$$
g_k(n) = (k-1)^n + (k-1)(-1)^n
$$
原作者注. 可以通过双射法轻松证明：
$$
g_k(n-1)+g_k(n) = k(k-1)^{n-1}
$$
故可证 1.20(b)-1 式。但是我并不清楚是否存在一种双射法能直接证明 1.20(b)-1 式。
题 21 [2-]
若 $p$ 为质数，$a \in \mathbb{N}_{+}$。证明：$a^p-a$ 可被 $p$ 整除。
题 22 (a) [2]
令 $p$ 为质数。证明：$\binom{2p}{p} - 2$ 可被 $p^2$ 整除。
题 22 (b) [*]
题 22 (a) 中其他条件不变。若 $p > 3$，证明：$\binom{2p}{p} - 2$ 可被 $p^3$ 整除。
题 23 [2-]
若 $p$ 为质数，证明：$(p-1)!+1$ 可被 $p$ 整除。
题 24 [1]
一个对多重集合（multiset）的不严谨的定义是：含有重复元素的集合。比如多重集合 ${1, 1, 1, 2, 4, 4, 5, 5}$，简写为 ${1^3, 2, 4^2, 5^2}$。
定义：
数字 $i$ 在一个多重集合 $M$ 内的出现次数为 $i$ 的重复次数（multiplicity），记作 $\nu_M(i)$ 或 $\nu(i)$。
若两个多重集合 $N, M$ 满足 $\forall i$，$\nu_N(i) \leq \nu_M(i)$，则称 $N$ 为 $M$ 的子多重集（submultiset）。
问：令 $M = {1^{\nu(1)}, 2^{\nu(2)},3^{\nu(3)}, \cdots, k^{\nu(k)}}$，$M$ 有多少个子多重集？
题 25 [2]
我们称一个多重集 $M$ 的大小（size）或基数（cardinality）为该多重集内的元素个数（重复的元素分别计算个数），记作 $|M|$。
如多重集 $M = {1, 1, 1, 2, 4, 4, 4, 5, 5}$，$|M| = 9$。
再称一个多重集 $M$ 可从集合 $S$ 中选出（on），当且仅当 $M$ 中的每个元素都在 $S$ 内。
令 $\left(\binom{n}{k}\right)$ 为从一个 $n$ 元集合中可选出的 $k$ 元多重集的个数。
证明：
$$
\left(\dbinom{n}{k}\right) = \binom{n+k-1}{k}
$$
题 26 [2-]
给定 $n, k \geq 0$，求方程
$$
x_1 + x_2 + \cdots + x_k = n
$$
的非负整数解数。
题 27 [*]
令 $n \geq 2$，$t \geq 0$。
注. 下面的定义修改了部分表述。
定义一个合法序列 $S(n, t)$ 为：
- 长度为 $n + 2t \binom{n}{2}$。
- 这个序列里有 $n$ 个 $x$，与 $2t$ 个 $a_{i, j}$（$1 \leq i < j \leq n$）。
- 对于每一个 $a_{i, j}$，它应该出现在第 $i$ 个 $x$ 与第 $j$ 个 $x$ 之间。
记 $f(n, t)$ 为 $S(n, t)$ 的个数。试证：
$$
f(n, t) = \dfrac{(n+tn(n-1)!)}{n!t!^n(2t)!^\binom{n}{2}} \prod_{i=1}^{n} \dfrac{((j-1)t)!^2(jt)!}{(1+(n+j-2)t)!}
$$
原作者注. 对于本题，某个特殊情况的式子可以通过 Selberg 积分得到。如果本题存在组合做法，那一定会非常有趣。
题 28 [*]
定义度数为 $n$ 的二进制德·布鲁金序列（binary de Brujin sequence）为一个 0-1 序列 $a_1, a_2, \cdots, a_{2^n}$，满足对于任意 $i \in [1, 2^n]$，其循环因子（circular factors） $a_i a_{i+1} \cdots a_{i+n-1}$ （下标模 $2^n$ 后加 1）互不相同。
如：一个度数为 $3$ 的二进制德·布鲁金序列为 00010111。
证明：度数为 $n$ 的二进制德·布鲁金序列有 $2^{2^{n-1}}$ 个。
原作者注. 注意到 $2^{2^{n-1}} = \sqrt{2^{2^n}}$。故令 $\mathcal{B}_n$ 为所有度数为 $n$ 的二进制德·布鲁金序列的集合，令 ${0, 1}^{2^n}$ 为度数为 $n$ 的二进制序列，只需证明双射 $\mathcal{B}_n \times \mathcal{B}_n \rightarrow {0, 1}^{2^n}$。
原作者注. 1946 年，数学家 Nicolaas Govert de Bruijn 第一次定义二进制德·布鲁金序列，并算出其个数。但 1975 年时，人们发现数学家 A. de Riviere 早就提出了这个问题，且数学家 C. Flye Sainte-Marie 在 1894 年就已证明这个问题。