下载此文档

组合3容斥原理鸽巢原理.ppt

文档分类： | 页数：约88页举报非法文档有奖

1/88

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/88 下载此文档

文档列表 文档介绍

组合数学
帅天平
北京邮电大学数学系
Email: tpshuai@
第三章排列组合
容斥原理
容斥原理应用
广义容斥原理
广义容斥原理应用
鸽巢原理及其应用
Ramsay数
应用举例
计数问题是组合数学研究的重要问题之一。
已学过的一些计数方法:如加法法则,母函数方法等;
两个重要的计数原理:容斥原理和PÓlya计数定理。
本次课我们学****容斥原理及其应用。
容斥原理
解: 2的倍数是:2,4,6,8,10,12,14,16,18,20。共10个;
容斥原理
例1 求不超过20的正整数中2或3的倍数的个数。
否!因为6,12,18在两类中重复计数,应减去。
3 的倍数是:3,6,9,12,15,18。共 6个;
答案是10+6=16个吗?
故答案是:16-3=13
对于求两个有限集合A和B的并的元素数目,我们有
即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元素个数减去同时具有性质A和B的元素个数。
(1)
定理1
容斥原理
容斥原理
A
B
A∩B
U
容斥原理
证若A∩B=,则| A∪B |= |A| + |B|,
否则
同理
容斥原理
( iii ) -( i ) -( ii ) 得
∴| A∪B |=| A | + | B |-| A∩B |
定理2
容斥原理
A
B
C
A∩B
A∩B ∩C
B∩C
A∩C
U
容斥原理
证明

组合3容斥原理鸽巢原理来自淘豆网www.taodocs.com转载请标明出处.