卢开澄组合数学--组合数学第三章
更新时间:2023-09-04 15:10:01 阅读量: 教育文库 文档下载
- 组合数学卢开澄第五版推荐度:
- 相关推荐
卢开澄组合数学--
§3.1 容斥原理引论第三章 容斥原理和鸽巢原理 §1 容斥原理引论例 [1,20]中2或3的倍数的个数 [解] 2的倍数是:2,4,6,8,10, 12,14,16,18,20。 10个
卢开澄组合数学--
§3.2 容斥原理3的倍数是:3,6,9,12,15, 18。 6个 但答案不是10+6=16 个,因为6, 12,18在两类中重复计数,应减 去。故答案是:16-3=13
卢开澄组合数学--
§3.2 容斥原理容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U,补集 AA {x | x U 且x A} ,有
(a)
A B A B
(b) A B A B
卢开澄组合数学--
§3.2 容斥原理证:(a)的证明。 设 x A B ,则 x A B x A B 相当于 x A和 x B 同时成立,亦即x A B x A B
(1)
卢开澄组合数学--
§3.2 容斥原理反之,若 x A B,即x A和x B
故 x A和x B.亦即x A B x A B x A B
(2)
由(1)和(2)得x A B x A B
(b)的证明和(a)类似,从略.
卢开澄组合数学--
§3.2 容斥原理DeMogan定理的推广:设A1, A2 ,..., An是U的子集则 (a) 1 A2 ... An A1 A2 ... An A( b )A 1 A 2 ... A n A1 A 2 ... A n
证明:只证(a). N=2时定理已证。 设定理对n是正确的,即假定:
卢开澄组合数学--
§3.2 容斥原理A1 A2 ... An A A2 ... An 1则 A1 A2 ... An An 1 ( A1 ... An ) An 1 ( A1 A2 ... An An 1 A1 A2 ... An An 1
正确
即定理对n+1也是正确的。
卢开澄组合数学--
§3.2 容斥原理
§2定理:
容斥原理
最简单的计数问题是求有限集合A 和B的并的元素数目。显然有A B A B A B (1)
即具有性质A或B的元素的个数等于具
卢开澄组合数学--
§3.2 容斥原理有性质A和B的元素个数。 U AA B
B
卢开澄组合数学--
§3.2 容斥原理证 若A∩B=φ,则 | A∪B |= |A| + |B| | A |=| A ∩( B∪B) | =| (A∩B)∪(A∩B)| =| A∩B | + | A∩B | (1) 同理 | B | =| B∩A | + | B∩A | ( 2 ) | A∪B |=|(A∩( B∪B))∪(B∩(A∪A))| =|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)| =| A∩B| + |A∩B | + | B∩A| ( 3 )
卢开澄组合数学--
§3.2 容斥原理( 3 ) -( 1 ) -( 2 ) 得 | A∪B |-| A |-| B | =| A∩B| + |A∩B | + | B∩A| -( | A∩B | + | A∩B | ) -( | B∩A | + | B∩A | ) =- | A∩B | ∴| A∪B |=| A | + | B |-| A∩B |
卢开澄组合数学--
§3.2 容斥原理定理:A B C A B C A B - A C B C A B C
(2)
证明: A B C ( A B) C A B C ( A B) C
卢开澄组合数学--
§3.2 容斥原理根据 ( A B) C ( A C ) ( B C )
A B C A B C A B ( A C) (B C ) A B C A B - A C B C A B C
卢开澄组合数学--
§3.2 容斥原理AA B
B
A C
B C
A B C
C
卢开澄组合数学--
§3.2 容斥原理 例一个学校只有三门课程:数学、 物理、化学。已知修这三门课的学生 分别有170
、130、120人;同时修 数学、物理两门课的学生45人;同时 修数学、化学的20人;同时修物理化 学的22人。同时修三门的3人。问这学 校共有多少学生?
卢开澄组合数学--
§3.2 容斥原理令:M为修数学的学生集合; P 为修物理的学生集合; C 为修化学的学生集合;M 170, P 130, C 120, M P 45 M C 20, P C 22, M P C 3
卢开澄组合数学--
§3.2 容斥原理 M P C M P C M P M C P C M P C 170 130 120 45 20 22 3 336
即学校学生数为336人。
卢开澄组合数学--
§3.2 容斥原理同理可推出:A B C D A B C D A B A C B C A D A B C A B D B C D A B C D
利用数学归纳法可得一般的定理:
卢开澄组合数学--
§3.2
容斥原理
定理 设¢(n,k)是[1,n]的所有k子集的集合, 则 n n |∪Ai | = ∑ (-1)k-1 ∑ | ∩ Ai | i=1k=1
I∈¢(n,k) i∈I
证 对n用归纳法。n=2时,等式成立。 假设对n - 1,等式成立。对于n有
正在阅读:
卢开澄组合数学--组合数学第三章09-04
冷库制冷系统安装施工方案12-30
大地PE+dos装机人员维护工具05-09
国有企业人力资源存在的问题及对策05-17
地球的表面形态305-30
棚户区综合改造项目建议书06-10
泼水节是几号,泼水节是几月几日02-15
2012-2013学年度表彰名单汇总03-27
营销策划部工作流程(全啊!!)05-15
2012秋年郑大民法学21章在线测试答案04-18
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 组合数学
- 第三章