前面三课已经把分类计数、分步计数、排列组合、捆绑法、插空法、至少/至多、补集与排除法串了起来。本课我们把这些计数思想进一步提升到集合与子集。这一课的重点不是让同学们背很多集合符号而是让大家明白集合是在“数东西”子集是在“做选择”。而“每个元素选不选”就会产生第四十三课集合与子集——从“选不选”到 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^416恰好有1个元素的子集恰好有2个元素的子集恰好有3个元素的子集恰好有4个元素的子集把它们加起来得到1 4 6 4 116恰好等于2^4十三、这就是一个非常漂亮的数学规律这其实就是二项式定理中非常重要的一种情况。同学们已经学习过杨辉三角还可以把它联系起来1 1 1 1 2 1 1 3 3 1 1 4 6 4 1第四行1464116也就是2^4十四、从“子集”进入集合运算现在我们开始学习集合最常见的三个操作交集 并集 补集可以用两个“魔法圈”来理解。十五、并集两个集合“合起来”例如A{1,2,3} B{3,4,5}把两个集合放在一起A1 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或BA∩B交集A和B都有补集不属于A可以记成并合起来交共同部分补剩下的二十二、集合数量计算最重要的公式假设∣A∣表示A中元素的个数。例如A{1,2,3,4}那么∣A∣4如果∣A∣5 ∣B∣6而且A、B没有共同元素。那么∣A∪B∣ 56 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∣代入44−26所以∣A∪B∣6二十五、为什么一定要减一次交集可以把它想象成点名。第一次点A集合。4个人。第二次点B集合。4个人。总共点了448但是3 4被点了两次。我们真正需要每个人只算一次。所以8−2 6因此∣A∪B∣∣A∣∣B∣−∣A∩B∣二十六、这个公式在CSP-J非常重要看到喜欢A项目的有30人喜欢B项目的有25人两个项目都喜欢的有10人至少喜欢其中一个的有多少人马上想到3025−10所以是45二十七、为什么不是302555因为同时喜欢两个项目的人被计算了两次。所以要减掉一次55−1045这其实也是排除重复计数。二十八、集合和“至少一个”再次连接“至少喜欢一个”是什么意思就是喜欢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^532有人会写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} 一共有多少个子集82集合 A{1,2,3,4,5} 有多少个子集323一个有6个元素的集合有多少个真子集2^6 −1 634一个有5个元素的集合有多少个恰好包含2个元素的子集5一个有5个元素的集合有多少个至少包含1个元素的子集6一个有5个元素的集合有多少个至少包含2个元素的子集 32−1−5 267如果A{1,2,3} B{3,4,5}那么A∪B是什么答案{1,2,3,4,5}8前题中同样的A、BA ∩ B是什么答案{3}9某班有30人喜欢C20人喜欢数学其中10人两者都喜欢。至少喜欢其中一门的有多少人30 20 − 10 4010全班50人至少喜欢C或数学的有40人那么两门都不喜欢的有多少人50−40 10 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^416恰好有1个元素的子集恰好有2个元素的子集恰好有3个元素的子集恰好有4个元素的子集把它们加起来得到1 4 6 4 116恰好等于2^4十三、这就是一个非常漂亮的数学规律这其实就是二项式定理中非常重要的一种情况。同学们已经学习过杨辉三角还可以把它联系起来1 1 1 1 2 1 1 3 3 1 1 4 6 4 1第四行1464116也就是2^4十四、从“子集”进入集合运算现在我们开始学习集合最常见的三个操作交集 并集 补集可以用两个“魔法圈”来理解。十五、并集两个集合“合起来”例如A{1,2,3} B{3,4,5}把两个集合放在一起A1 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或BA∩B交集A和B都有补集不属于A可以记成并合起来交共同部分补剩下的二十二、集合数量计算最重要的公式假设∣A∣表示A中元素的个数。例如A{1,2,3,4}那么∣A∣4如果∣A∣5 ∣B∣6而且A、B没有共同元素。那么∣A∪B∣ 56 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∣代入44−26所以∣A∪B∣6二十五、为什么一定要减一次交集可以把它想象成点名。第一次点A集合。4个人。第二次点B集合。4个人。总共点了448但是3 4被点了两次。我们真正需要每个人只算一次。所以8−2 6因此∣A∪B∣∣A∣∣B∣−∣A∩B∣二十六、这个公式在CSP-J非常重要看到喜欢A项目的有30人喜欢B项目的有25人两个项目都喜欢的有10人至少喜欢其中一个的有多少人马上想到3025−10所以是45二十七、为什么不是302555因为同时喜欢两个项目的人被计算了两次。所以要减掉一次55−1045这其实也是排除重复计数。二十八、集合和“至少一个”再次连接“至少喜欢一个”是什么意思就是喜欢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^532有人会写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} 一共有多少个子集82集合 A{1,2,3,4,5} 有多少个子集323一个有6个元素的集合有多少个真子集2^6 −1 634一个有5个元素的集合有多少个恰好包含2个元素的子集5一个有5个元素的集合有多少个至少包含1个元素的子集6一个有5个元素的集合有多少个至少包含2个元素的子集 32−1−5 267如果A{1,2,3} B{3,4,5}那么A∪B是什么答案{1,2,3,4,5}8前题中同样的A、BA ∩ B是什么答案{3}9某班有30人喜欢C20人喜欢数学其中10人两者都喜欢。至少喜欢其中一门的有多少人30 20 − 10 4010全班50人至少喜欢C或数学的有40人那么两门都不喜欢的有多少人50−40 10