MENU

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$。

(c) 即意味着每个元素都不能出现在所有子集中,那么对于任意一个元素而言,我们可以构造 $A\subset[k]$ 表示所有包含该元素的子集编号,$A$ 的个数即为 $2^k-1$,元素之间是独立的,故答案为 $(2^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 即可得证。

Last Modified: October 26, 2022
Archives Tip
QR Code for this page
Tipping QR Code