CSP-J 初赛（以满分为目标）：第四十三课《集合与子集——从“选不选”到 2^n》

前面三课已经把分类计数、分步计数、排列组合、捆绑法、插空法、至少/至多、补集与排除法串了起来。

本课我们把这些计数思想进一步提升到集合与子集。这一课的重点不是让同学们背很多集合符号，而是让大家明白：

集合是在“数东西”，子集是在“做选择”。

而“每个元素选不选”，就会产生：

第四十三课：集合与子集——从“选不选”到 2^n

一、先从一个“魔法集合”开始

小明有4张卡片：

1号：🐱
2号：🐶
3号：🐰
4号：🐼

现在老师问：

从这4张卡片中，任意挑一些出来，可以有多少种不同的选择？

注意：

可以一张都不选，也可以全部选。

例如：

什么都不选
只选🐱
只选🐶
🐱🐶
🐱🐰
🐶🐼
……
四张全部选

问题来了：

一共有多少种？

二、不要一个一个列！

如果只有4个元素，可以列。

但是如果有：

10个
20个
100个

还能一个一个列吗？

当然不行。

所以我们需要找到规律。

三、每个元素只有两个选择

对于🐱来说：

选
不选

只有2种可能。

对于🐶：

选
不选

也是2种。

对于🐰：

选
不选

还是2种。

对于🐼：

选
不选

还是2种。

于是：

第1个：2种
第2个：2种
第3个：2种
第4个：2种

根据我们第42课学过的：

分步计数 → 相乘

所以：

2×2×2×2

即：

四、这就是“子集个数”

一个集合有 n 个元素。

它的所有子集数量是：

为什么？

因为：

每一个元素，都只有“选”和“不选”两种状态。

于是：

2×2×⋯×2⏟n个 =  2^n

五、最重要的一个问题：空集算不算？

例如集合：

A = {1,2,3} 

它的子集有哪些？

{}
{1}
{2}
{3}
{1,2}
{1,3}
{2,3}
{1,2,3}

一共：

8

个。

也就是：

2^3 = 8

其中：

{}

就是：

空集

空集也是任何集合的子集。

所以：

计算子集数量时，一定要把空集算进去。

六、初学者容易混淆：子集和真子集

这是CSP-J初赛非常值得注意的概念。

假设：

A = {1,2,3}

那么：

{1,2}

是A的子集。

而：

{1,2,3}

也是A的子集。

因为一个集合本身也是自己的子集。

所以：

子集包括集合本身

七、什么是真子集？

真子集就是：

是子集，但是不能和原集合完全一样。

例如：

{1,2}

是A的真子集。

但是：

{1,2,3}

不是A的真子集。

所以：

如果集合有 n 个元素：

子集

真子集

把集合自己去掉：

八、用“小盒子”理解子集

可以继续使用我们一直给同学们讲的“盒子”思维。

集合：

┌───────────────┐
│ 1 2 3 4 │
└───────────────┘

构造一个子集，就相当于：

对每个数字做一次选择。

1：拿 / 不拿
2：拿 / 不拿
3：拿 / 不拿
4：拿 / 不拿

每个元素：

2种

所以：

2^4

九、子集为什么和前面课中的“分步计数”有关系？

因为：

选择每一个元素是否进入子集，就是一个步骤。

例如：

决定1进不进
↓
决定2进不进
↓
决定3进不进
↓
……

每一步：

2种

因此：

所以：

这就是数学知识之间的连接。

十、如果要求“恰好选2个”呢？

现在集合有：

{1,2,3,4,5} 

问：

有多少个子集恰好包含2个元素？

这时候就不是 2^5 了。

因为我们要求：

恰好选2个。

也就是从5个元素中：

选2个

所以：

十一、这就把“子集”和“组合”连接起来了

所有子集：每个元素选/不选

所以：

2^n

而：

恰好选k个元素：从n个元素中选择k个

所以：

十二、举一个完整例子

集合：

A={1,2,3,4}

一共有4个元素。

所有子集

2^4=16

恰好有1个元素的子集

恰好有2个元素的子集

恰好有3个元素的子集

恰好有4个元素的子集

把它们加起来：

得到：

1 + 4 + 6 + 4 + 1=16

恰好等于：

2^4

十三、这就是一个非常漂亮的数学规律

这其实就是二项式定理中非常重要的一种情况。

同学们已经学习过杨辉三角，还可以把它联系起来：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

第四行：

1+4+6+4+1=16

也就是：

2^4

十四、从“子集”进入集合运算

现在我们开始学习集合最常见的三个操作：

交集
并集
补集

可以用两个“魔法圈”来理解。

十五、并集：两个集合“合起来”

例如：

A={1,2,3}   B={3,4,5} 

把两个集合放在一起：

A：1 2 3
B： 3 4 5

并集就是：

A或B中的元素都要。

记作：

A∪B

所以：

A∪B={1,2,3,4,5} 

十六、为什么3只能写一次？

因为集合中：

相同元素不能重复记录。

虽然：

A里有3
B里也有3

但是并集仍然只有一个3。

所以：

A∪B={1,2,3,4,5} 

而不是：

{1,2,3,3,4,5}

十七、交集：两个集合“共同拥有”

还是：

A={1,2,3}   B={3,4,5} 

A和B共同拥有：

3

所以：

A∩B 

表示交集：

A∩B = {3} 

记忆：

并集：有一个就行。

交集：两个都要有。

十八、生活中的例子

班级里：

A集合：

喜欢足球的同学

B集合：

喜欢篮球的同学

那么：

A∪B

表示：

喜欢足球或者篮球的同学。

A∩B

表示：

足球、篮球都喜欢的同学。

这和前面课程中的：

“或者”与“并且”

其实又联系起来了。

十九、集合中的“补集”

假设全集：

U={1,2,3,4,5} 

集合：

A={1,2,3} 

那么：

不属于A，但属于全集U的元素

就是：

4 5

这叫：

A的补集 

记作：

因此：

二十、补集与上一课“至少、排除法”再次连接

上一课我们学习：

符合条件 = 总数 − 不符合条件

现在集合中：

就是：

A的反面。

所以：

A → 满足条件
A的补集 → 不满足条件

这就是为什么：

集合补集和排列组合中的补集思想，本质上是同一个思维。

二十一、集合的三个基本运算

同学们要记住：

A∪B	并集	A或B
A∩B	交集	A和B都有
	补集	不属于A

可以记成：

并：合起来

交：共同部分

补：剩下的

二十二、集合数量计算：最重要的公式

假设：

∣A∣

表示A中元素的个数。

例如：

A={1,2,3,4} 

那么：

∣A∣=4 

如果：

∣A∣=5  ∣B∣=6

而且A、B没有共同元素。

那么：

∣A∪B∣= 5+6 = 11

二十三、如果A、B有重复元素怎么办？

例如：

A={1,2,3,4}   B={3,4,5,6} 

那么：

∣A∣=4    ∣B∣=4  

但是：

∣A∪B∣

不是8。

因为3、4被重复计算了。

二十四、要减去重复部分

A和B共同拥有：

{3,4}

所以：

∣A∩B∣=2 

因此：

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

代入：

4+4−2=6 

所以：

∣A∪B∣=6 

二十五、为什么一定要减一次交集？

可以把它想象成点名。

第一次：

点A集合。

4个人。

第二次：

点B集合。

4个人。

总共点了：

4+4=8

但是：

3
4

被点了两次。

我们真正需要：

每个人只算一次。

所以：

8−2 = 6

因此：

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

二十六、这个公式在CSP-J非常重要

看到：

喜欢A项目的有30人；

喜欢B项目的有25人；

两个项目都喜欢的有10人；

至少喜欢其中一个的有多少人？

马上想到：

30+25−10

所以是：

45

二十七、为什么不是30+25=55？

因为：

同时喜欢两个项目的人，被计算了两次。

所以要减掉一次：

55−10=45

这其实也是：

排除重复计数。

二十八、集合和“至少一个”再次连接

“至少喜欢一个”是什么意思？

就是：

喜欢A或者喜欢B。

也就是：

A∪B

所以：

至少一个 ⟺ 并集

而：

两个都喜欢

就是：

A ∩ B 

所以：

两个都满足 ⟺ 交集 

二十九、一个综合例题

班里有40名同学。

其中：

• 25人喜欢数学

• 20人喜欢编程

• 10人数学和编程都喜欢

问：

至少喜欢数学和编程中的一个的有多少人？

设：

A=喜欢数学    B=喜欢编程 

那么：

∣A∣=25   ∣B∣=20    ∣A∩B∣=10 

所以：

∣A∪B∣= 25 + 20−10 = 35

三十、那两样都不喜欢的有多少人？

全班40人。

至少喜欢一个：

35

所以：

40−35 = 5

这又一次用到了：

补集思想。

也就是：

都不喜欢 = 总人数 − 至少喜欢一个

三十一、把整个思路串起来

集合
│
├── 并集 A∪B
│ ↓
│ 至少一个
│
├── 交集 A∩B
│ ↓
│ 两个都有
│
└── 补集 Aᶜ
↓
反面
↓
总数-满足

大家会发现：

上一课的补集思想，在本课再次出现。

三十二、集合与排列组合又连接起来了

现在再看一个问题：

集合有5个元素。

问：

它有多少个子集？

答案：

2^5

如果问：

恰好有2个元素的子集有多少个？

答案：

如果问：

至少有1个元素的子集有多少个？

所有子集：

2^5

但是空集不符合。

所以：

2^5 – 1 =31

三十三、如果问“至少2个元素”呢？

全集子集数量：

2^5

不满足：

0个
1个

所以：

= 32−1−5 = 26

这正好把：

组合

至少/补集

子集

全部连接起来。

三十四、CSP-J初赛的典型考法

以后看到：

一个集合有 n 个元素，它的子集有多少个？

答案：

看到：

真子集有多少个？

答案：

看到：

恰好包含 k 个元素的子集有多少个？

答案：

看到：

至少包含一个元素的子集有多少个？

答案：

看到：

至少包含2个元素？

答案：

三十五、一个初学者容易错的地方

题目：

一个集合有5个元素，有多少个子集？

答案：

2^5=32

有人会写：

5!

这是错的。

为什么？

因为：

5!

是在考虑：

5个元素怎么排列。

而：

2^5

是在考虑：

5个元素每一个选还是不选。

两者解决的问题完全不同。

三十六、“排列”和“子集”有什么区别？

例如：

{A,B,C} 

选择两个元素。

如果问：

选出两个元素。

那么：

AB
AC
BC

一共：

因为：

AB和BA是同一种选择。

但是如果问：

从A、B、C中选2个排成一排。

那么：

AB
BA
AC
CA
BC
CB

一共：

3×2 = 6

因为：

AB和BA是不同顺序。

三十七、所以大家必须记住

集合关注“有没有”。

排列关注“顺序”。

例如：

{A,B}

和：

{B,A}

它们是同一个集合。

但是排列：

AB

和：

BA

是两种不同的排列。

三十八、本课“反粗心”训练

做集合题的时候，同学们强制检查：

① 子集包括集合本身吗？

包括。

② 空集算不算？

算。

③ 真子集包括集合本身吗？

不包括。

④ 集合中的元素有顺序吗？

没有。

⑤ 并集中的重复元素怎么算？

只算一次。

⑥ 交集表示什么？

共同部分。

⑦ “至少一个”对应什么？

并集。

⑧ “都不满足”怎么办？

考虑补集。

三十九、本课知识地图

集合
│
┌──────────┼──────────┐
↓ ↓ ↓
并集 交集 补集
A∪B A∩B Aᶜ
│ │ │
或者 都有 反面
│ │ │
至少一个 同时满足 总数-满足
│
↓
子集
│
┌─────────┼─────────┐
↓ ↓ ↓
所有子集 恰好k个 真子集
↓ ↓ ↓
2ⁿ C(n,k) 2ⁿ-1

四十、我们已经形成一条完整的数学链

现在回头看前面四课：

第40课
分类、分步
↓
加法、乘法
↓
排列、组合

第41课
特殊限制
↓
捆绑、插空、固定位置

第42课
至少、至多
↓
补集、排除、避免重复

第43课
集合与子集
↓
并集、交集、补集
↓
2ⁿ、C(n,k)
↓
再次连接排列组合

所以我们不是在“堆知识点”，而是在不断把前面的知识重新组合起来。

四十一、本课给同学们的“魔法口诀”

🪄 集合与子集四句口诀

集合没有顺序，重复元素不算；

并集就是合起来，交集就是共同部分；

每个元素选不选，两种选择乘起来；

n个元素的子集，一共就是 2n2^n。

空集也算子集，真子集要减掉自己！

再加一句：

“至少”想并集，“都不”想补集，“恰好k个”想组合。

四十二、课后练习

1

集合 A={1,2,3}  ，一共有多少个子集？

8

2

集合 A={1,2,3,4,5}  ，有多少个子集？

32

3

一个有6个元素的集合，有多少个真子集？

2^6 −1 = 63 

4

一个有5个元素的集合，有多少个恰好包含2个元素的子集？

5

一个有5个元素的集合，有多少个至少包含1个元素的子集？

6

一个有5个元素的集合，有多少个至少包含2个元素的子集？

= 32−1−5  =26

7

如果：

A={1,2,3}    B={3,4,5}  

那么：

A∪B  

是什么？

答案：

{1,2,3,4,5}

8

前题中，同样的A、B：

A ∩ B

是什么？

答案：

{3} 

9

某班有30人喜欢C++，20人喜欢数学，其中10人两者都喜欢。

至少喜欢其中一门的有多少人？

30 + 20 − 10 = 40

10

全班50人，至少喜欢C++或数学的有40人，那么两门都不喜欢的有多少人？

50−40 = 10