有限集元素的数目 · 看得见的小蓝本·高中卷

有限集元素的数目

数不清就换个东西数：把子集换成 0-1 串，把大问题按“含不含最后一个元素”拆成两个小问题。

这一招在做什么

有限集 $A$ 的元素个数记作 $∣ A ∣$ 。数得清的直接列举；数不清的，靠下面三招：

列举：小的情形全部写出来，看清结构。
对应：造一个一一对应，把要数的东西换成好数的东西。子集 $⟷$ 0-1 串：第 $i$ 位是 $1$ 表示 $i$ 在子集里。
递推：按“含不含最后一个元素 $n$ ”把对象分成两类，每一类都变成规模更小的同一个问题。

第 2 招立刻给出最基本的公式：每一位独立地取 $0$ 或 $1$ ，所以

{A ∣ A \subseteq {1, 2, \dots, n}} = 2^{n} .

按元素个数分组，第 $k$ 组有 $C_{n}^{k}$ 个，于是 $C_{n}^{0} + C_{n}^{1} + \dots + C_{n}^{n} = 2^{n}$ ——上面操作台按大小分出的那几组，就是杨辉三角的一行。

先猜后证

${1, 2, \dots, 8}$ 的子集中，含 $1$ 但不含 $2$ 的有多少个？

个

先选定答案，才能看到结论。

跟着做一遍

问题： ${1, 2, \dots, n}$ 有多少个子集不含相邻的两个数？ 记这个个数为 $a_{n}$ 。

递推：不含相邻两数的子集

第 1 / 6 步

先数一个小的
$n = 4$ ： $16$ 个子集里，带 ✗ 的含有相邻两数。数一数没有 ✗ 的， $a_{4} = 8$ 。

$a_{4} = 8$
按含不含 4 分两类
不含 4 的一类
含 4 的一类
递推式
一路推下去

什么时候不灵

Break it

反例实验室：去掉一个条件

结论：两边的个数相等

子集 $\leftrightarrow$ 0-1 串：不同的子集给出不同的串，每个串也都能读回一个子集。所以 ${1, 2, 3, 4}$ 的子集和长为 $4$ 的 0-1 串一样多，都是 $16$ 个。

练一练

练习 1基础

${1, 2, \dots, 10}$ 的子集中，同时含 $3$ 和 $7$ 的有多少个？

练习 2基础

${1, 2, \dots, 10}$ 有多少个子集不含相邻的两个数？（空集也算。）

练习 3提高

${1, 2, \dots, 6}$ 有多少个子集含偶数个元素？要求：不要把 $C_{6}^{0} + C_{6}^{2} + \dots$ 算出来，而是造一个一一对应。

练习 4挑战

${1, 2, \dots, 10}$ 有多少个子集不含三个连续的整数？

错误博物馆 · 本站展品

离站之前，看看别人在这里踩过的坑。去博物馆看全部展品 →

展品

非空真子集，只减了一个

{1, 2, \dots, n}

的非空真子集有

2^{n} - 1

个。

错在哪里？先想一想，再打开

病因　 $2^{n}$ 个子集里，要去掉的有两个：空集（不是非空的）和全集本身（不是真子集）。

非空真子集有

2^{n} - 2

个。数之前先把要排除的对象逐个点名。

「排除几个，就点名几个」

展品

对应不是一一的，就拿去数

{1, 2, 3, 4}

的每个子集对应它的元素和，和只能是

0, 1, \dots, 10

，所以子集有

11

个。

错在哪里？先想一想，再打开

病因　不同的子集可以有相同的和： ${1, 4}$ 和 ${2, 3}$ 的和都是 $5$ 。这个对应是“多对一”的，两边个数并不相等（子集实际有 $16$ 个）。

用对应计数之前检查两件事：不同的对象对到不同的像（单射），每个像都有对象对到（满射）。子集 ↔ 0-1 串两条都满足。

「只有一一对应，才能把数这边换成数那边」