挑战≈ 16 分钟未开始

对应与双射计数

核心概念

双射原理:若两个有限集合 $A,B$ 之间存在一一对应(双射),则 $|A| = |B|$ 。于是,要数一个难数的集合,可以把它和一个好数的集合建立一一对应,转而去数后者。

两个经典对应:

子集 ↔ 0/1 串: $n$ 元集合的子集,对应长度 $n$ 的 0/1 串(每个元素"选/不选"),故子集共 $2^n$ 个;
格点最短路 ↔ 排列:从 $(0,0)$ 沿向右/向上走到 $(m,n)$ 的最短路径,对应一串由 $m$ 个"右"和 $n$ 个"上"组成的序列,共 $C_{m+n}^{m}$ 条。

双射是计数里最优雅的思想:与其硬数,不如换个等价的东西数。一个组合对象难以直接计数时,如果能给它配上一个"影子"——另一个一目了然的对象,并保证两者一一对应,那么数影子就等于数本身。

关键在于"对应必须是一一的":既不能两个原对象对到同一个影子(否则少算),也不能有影子无原象(否则多算)。常用的影子有 0/1 串、格点路径、排列等。学会把陌生的计数翻译成熟悉的对象,是组合高手的标志性能力。

双射计数

每条路径 ↔ 用 3 个「右」和 3 个「上」排成的序列,共 C(6, 3) = 20 条

向右 m3

向上 n3

把「难数的路径」对应到「好数的序列」:共走 m+n 步,选哪 m 步向右即可,故路径数 = C(m+n, m)。

例题 1子集计数

证明 $n$ 元集合恰有 $2^n$ 个子集。

▸查看解答步骤

答: 2ⁿ

例题 2格点最短路

从 $(0,0)$ 每次向右或向上一格,走到 $(3,3)$ ,有多少条最短路径?

▸查看解答步骤

答: C(6,3)=20

$4$ 元集合有多少个子集?

$2^4 = 16$ 。

从 $(0,0)$ 向右/向上走到 $(3,3)$ 的最短路径有几条?

$C_6^3 = 20$ 。

从 $(0,0)$ 向右/向上走到 $(3,2)$ 的最短路径有几条?

共 $5$ 步选 $3$ 步向右: $C_5^3 = C_5^2 = 10$ 。

双射原理要求两集合之间的对应是?

一一对应(既不重复也不遗漏)多对一一对多任意对应即可

必须是双射(一一对应),才能保证两集合元素个数相等。

长度为 $3$ 的 0/1 串共有多少个?

每位 $2$ 种选择, $2^3 = 8$ 。

前置知识点

接下来学习