Bijective Proof Problems 乱做

其实没有什么组合数学的底子，但是 BijProbs 确实有趣且技巧性，主要是把这玩意视作一种思维体操，尽可能在能力范围内解决一些问题。

约定

顾名思义，对于每个问题，我们期望得到一个组合意义的证明。

在大多数情况下，应该构造一个 $S\to T$ 的双射，从而得到 $|S|=|T|$。

被禁止的证明方法包括但不限于归纳、递归、生成函数。

尽可能让证明更加简洁和优雅。

记号

$\mathbb{P}$ 表示正整数集
$[n]=\{1,2,\dots,n\}$
$[l,r]=\{l,l+1,\dots,r\}$
$C(S,k)$ 表示 $S$ 所有大小为 $k$ 的子集

难度记号

[1] 简单或显然
[2] 难度适中或有技巧性
[3] 困难
[u] 尚未解决
$+/-$ 表示难度微调

Prob.1 [1]

大小为 $n$ 集合的子集个数为 $2^n$。

一个元素在子集中只有选或不选两种情况，且元素之间显然是独立的，故答案为 $2^n$。

形式化的，我们可以用一个 $n$ 维向量 $V=(v_1,v_2,\dots,v_n)$ 来表示一个子集，其中 $v_i\in\{0,1\}$，$v_i=1$ 当且仅当第 $i$ 个元素在子集中。子集与向量一一对应，即构成双射，容易发现 $n$ 维 0-1 向量的个数为 $2^n$，故答案为 $2^n$。

Prob.2 [1]

正整数 $n$ 的有序划分数为 $2^{n-1}$。

将 $n$ 视作一行 $n$ 个点，根据插板法，我们只需要在 $n-1$ 个空位放入若干挡板即可。

如果将 $n-1$ 个空位视作一个集合，放入挡板的过程视作提取集合的一个子集，根据 Prob.1 可得答案为 $2^{n-1}$。

Prob.3 [2]

正整数 $n$ 所有有序划分的划分部分数总和为 $(n+1)2^{n-2}$。

在 Prob.2 的基础上进行进一步讨论，我们现在即是要求所有子集大小的总和。

考虑集合中的一个元素，由于元素之间是独立的，于是在所有子集中，包含与不包含这个元素的子集个数均为 $2^{n-2}$，换言之，每个元素在 $2^{n-1}$ 个子集中共出现了 $2^{n-2}$ 次，故对答案的贡献也为 $2^{n-2}$。

所以，在所有 $2^{n-1}$ 个有序划分中，我们一共放置了 $(n-1)2^{n-2}$ 个挡板，但请注意，$k$ 个挡板会将一行点分为 $k+1$ 个部分，所以我们的最终答案为 $(n-1)2^{n-2}+2^{n-1}=(n+1)2^{n-2}$。

Prob.4 [2-]

对于正整数 $n\ge 2$，$n$ 的所有有序划分中，满足偶数个数为偶数的共有 $2^{n-2}$ 个。

对于一个有序划分 $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k),\sum\alpha_i=n$，我们考虑这样一种变换：

如果 $\alpha_k=1$，合并 $\alpha_k$ 与 $\alpha_{k-1}$。
否则我们有 $\alpha_k>1$，那么将 $\alpha_k$ 拆分为 $\alpha_k-1$ 与 $1$，注意这里是有序的。

容易发现，对于任意有序划分，经过变换后「偶数个数」的奇偶性都发生了改变。并且，对一个有序划分进行 2 次变换后，我们还能够得到原来的有序划分。

于是，按照上面的变换规则，我们便能够得到一个「偶数个数为偶数的有序划分」与「偶数个数为奇数的有序划分」间的双射，故两个集合的大小是相等的；另一方面，两个集合的并即为 $n$ 的所有有序划分，故答案为 $2^{n-1}/2=2^{n-2}$。

Prob.5 [2]

分别求出满足以下条件的 $k$ 元组 $(S_1,S_2,\dots,S_k)$ 的个数，其中 $S_i$ 为 $[n]$ 的子集。

(a) $S_1\subseteq S_2\subseteq\cdots\subseteq S_k$

(b) $S_1,S_2,\dots,S_k$ 两两不交

(c) $\bigcap S_i=\varnothing$

个人还是更加喜欢 bac 的顺序，那么就按照这个顺序来吧。

首先来看 (b)，两两不交意味着 $[n]$ 中每个元素至多在一个子集中出现，那么构造 $n$ 维向量 $V=(v_1,v_2,\dots,v_n),v_i\in[0,k]$，$v_i=0$ 意味着 $i$ 没有出现于任何一个子集中，否则 $i\in S_{v_i}$，容易发现 $k$ 元组与向量构成双射，故答案为 $(k+1)^n$。

考虑 (a)，显然对于满足 (b) 的 $k$ 元组 $(S_1,S_2,\dots,S_k)$，$(S_1,S_1\cup S_2,\dots,\bigcup_{i=1}^{k}S_i)$ 满足 (a)，反之亦然，故 (a) 的答案也为 $(k+1)^n$。

Prob.6 [1]

$S$ 是一个大小为 $n$ 的集合，若 $\binom{n}{k}=|C(S,k)|$，则
$$
k!\binom{n}{k}=\prod_{i=n-k+1}^ni
$$
（即二项式系数定义的组合形式）

分别考虑两边的组合意义。

左边表示从 $S$ 中提取 $k$ 个元素并对其进行排列，即 $S$ 大小为 $k$ 的有序子集的个数。

右边则是分步考虑了左边这一过程，即首先从 $n$ 个元素中选择一个放在第一个位置上（方案数为 $n$），然后从剩下 $n-1$ 个元素中选择一个放在第二个位置上（方案数为 $n-1$），以此类推，重复这一过程 $k$ 次，就能够得到右边的式子。

所以左边=右边，将 $k!$ 除到右边去就是常见的二项式系数定义。

Prob.7 [1+]

若

$$
(x+y)^n=\sum\binom{n}{k}x^ky^{n-k}
$$

则
$$
\binom{n}{k}=\frac{\prod_{i=n-k+1}^{n}i}{k!}
$$

左边可以视作 $\underbrace{(x+y)(x+y)\cdots(x+y)}_{n}$，考虑多项式乘法的过程，我们实际上从每个 $(x+y)$ 中选择了 $x$ 或 $y$，然后得到 $2^n$ 项形如 $x^?y^?$ 的单项式，$x$ 和 $y$ 的指数分别对应了选择 $x$ 与 $y$ 的次数，那么 $x^ky^{n-k}$ 的系数就应该是 $n$ 选 $k$ （或 $n$ 选 $n-k$，容易发现两者表达的意义相反，方案数则是相等的）的方案数，根据 Prob.6 即可得证。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog