tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 电子/电路 >>

容斥原理及其应用


2005年 11月 第 15卷   第 5期

榆 林 学 院 学 报 JO U RN A L O F Y U LIN CO LLEG E

N ov . 2005 V ol. 15 N o. 5

容斥原理及其应用
王竞才
(榆林市 教研室 ,陕西 榆林  719000) 摘  要: 通过对容斥原理的阐述 , 在此基础上着重介绍了容斥原理的应用 。 关键词: 容斥原理 ; 证明 ; 应用 中图分类号: O 157   文献标识码: A   文章编号 : 1008- 3871( 2005) 05- 0004- 02   容斥原理是组合数学中的一个重要原理 ,也是计数中常用的一种方法 ,尽管它所研究的是有限集元素计 数问题 , 然而它的应用是广泛有趣的 。 1   容斥原理 容斥原理 (逐步淘汰原理 ): 设有两个有限集 A和 B, 且 A、 B 分别由具有性质 P1、 P2 的元素组成 , 那么不 具有性质 P1 也不具有性质 P2 的元素个数 | A∩ B | , 就等于全体元素个数|U| 减去具有性质 P1 的元素个数 | A| , 再减去具有性质 P2 的元素个数| B | , 然后加上同时具有性质 P1 与 P2 元素个数 | A∩ B | 。 即: | A∩ B | =| U| - |A | -| B | + | A∩ B | … …… …① 容斥原理更一般地形式是 : 设 P1 , P2… Pk 个性质 , Ai ( i= 1, 2, … k)是 U 中的子集 , 它的元素具有性质 P1 (也可能同时具有其它性质 ) , 则有 k k | ∩ = | - ∑ | + ∑ | - ∑ |Ai∩ Aj∩ Am| + … + ( - 1) k| ∩ Ai| …… …… ② Ai| U| Ai| Ai∩ Aj|
i= 1 1≤ i ≤k k 1≤ i < j ≤k k 1 ≤i < j < m ≤k k i= 1

又由德莫根公式 : i= = U1 Ai = U - i=U1 Ai = U- ∩ Ai 得 : | U Ai| i= 1 i= 1
k

k



1 ≤i ≤k

|Ai| -

1≤ i≤ j ≤k



| + … + ( - 1)k- 1| Ai∩ Aj|

∩ Ai| …… …… ③ i= 1 同时容易证得 : ②、③两式的对偶公式 k | U A= |U| - 1∑ | Ai| + 1≤ ∑ | Ai∪ Aj| i= 1 ≤i ≤k i < j≤ k | ∩ = Ai| i= 1
k 1≤ i ≤k

|Ai∪ Aj∪ Am| + … + ( - 1) | U Ai| …… …… ②′ 1 ≤i < j < m ≤k i= 1
Am



k

k

∑ |A| - ∑
i

| + Ai∪ Aj| 1 ≤i < j ≤k

| Ai∪ Aj∪ 1≤ i < j < m≤ k



| + … + ( - 1) k- 1| … …… …③′ U Ai| i= 1

k

2   容斥原理的应用 2. 1 第二维数公式 d( V1+ V 2 ) = d( V 1 )+ d( V 2 ) - d( V1∩ V2 )的推广 设 Vi ( i= 1, 2, … k)是线性空间的子空间。 且 Vi 的基向量组 βi β (β 为线性空间 V 的基向量组 ) 则 ① d( 1∑ Vi ) = ≤i ≤k
k

d( Vi ) 1≤ i≤ k d( Vi ) -



d( Vi∩ Vj )+ … + ( - 1) k- 1 d(∩ Vi ) 1 ≤i < j ≤k i= 1 d( Vi+ Vj )+ … + ( - 1)
k- 1



k

② d(∩ Vi ) = i= 1



1 ≤ i≤ k

1≤ i < j ≤k



d( 1∑ Vi )其中 d( Vi )是 Vi 的维数 。 ≤ i≤ k

证明: ① 设 V 的向量组为 β= {α 1 ,α 2 ,… α n } , βi 是 β 的子集 ( i= 1, 2, … k) , β , βi 都是有限元素集 , 由容斥原 理可得 : | = Vβ 1| i= 1
k k



| β i| 1 ≤ i≤ k

| + … + ( - 1)k- 1| ∩ βi∩ β j| βi| 1 ≤ i < j≤ k i= 1
k k



k

由于线性空间基向量组向量个数就是它的维数。 即 d( Vi ) = | β i|   d( Vi+ V j ) = | β i∩ β j| … d(∩ Vi ) = | i= 1 ∩ βi| d( V1+ V2+ … + Vk ) = | Uβi| i= 1 i= 1 ∴①得证  同法可证得 ② 注意: 命题中 β i β , 在 k> 2时是很必要的 , 否则上述命题不真。 例如: 以 V 1= { x 轴 }  V2 { y 轴 }  V3 {角平分线 y= x } 则 d( V1+ V2+ V3 ) = 2
收稿日期 : 2004- 12- 05   修回日期 : 2005- 09- 10 作者简介 : 王竞才 ( 1961- ) ,男 ,陕西榆林人 ,中教高级 .

王竞才 : 容斥原理及其应用

· 5 ·

  ( i= 1, 2, 3) d ( Vi ) = 1 1 d( V ∩ V2 ) = d( V1∩ V 3 )= d( V 2∩ V 3 ) = d( V1∩ V2∩ V3 ) = 0 因而 d ( V 1+ V 2+ V 3 )≠ ∑ d ( Vi ) 1 ≤ i≤ 3 2. 2 组合恒等式的证明 范德蒙 ( Vandermo nde)恒等式
k 1 ≤i < j < 3



d ( Vi∩ Vj )+ d ( V1∩ V2∩ V3 )


k

i= 0

i k Cin Ckm = C m+

n

证 : 设 U= { a1 , a2 , … am , b1 , b2 , … bn }是 m 个不同的红球和 n 个不同的白球构成的集合。 k 令 Ai 表示从 U 中取 k 个球中有 i 个红球取法组成的集。 ( i= 0, 1, … k) , 则从 U 中取 k 个球方法为 Cm+ = | U Ai| 因为 i≠ j ( i, j= 0, 1, 2 … k)时 , Ai ∩ Aj = Υ, 且 |Ai| = C C i= 0
k i n k- i m

n

, 所以由 容斥原理 得 C

k m+ n

k

= | U| = i= 0



i= 0

Cn Cm

i

k- i

2. 3 匹配问题 有 n扇门各有钥匙一把 ,某人忘记了每把钥匙是开哪一扇门的 ,于是他把各种分配方式一一试验 ,问 : ① (耦合问题 )至少有一个门打开的分配方式有多少种。 ② (借位问题 )没有一个门被打开的分配方式有多少种。 解 : ① 设 Ai 表示能打开第 i 扇门的分配方式的全体 ( i= 1, 2, … n) , 由于第 i把钥匙总是分配给第 i 扇门 的 , 其它 n- 1把钥匙则可以任意分配给其它的 n- 1 扇门 。 ∴| = ( n - 1)!      ( i= 1, 2, … n ) Ai| 类似把|Ai∩ Aj| = ( n- 2)!      ( i≠ j) …… { A1∩ A2…∩ An }= ( n- n)! = 1 ∴ Dn = | = U Ai| i= 1
1 n

| Ai| 1≤ i≤ k
2



| + … + ( - 1) k- 1| Ai∩ Aj| n Ai| 1≤ i < j ≤k i= 1
n- 1



k

n

= Cn ( n- 1)! - Cn ( n- 2)! + … + ( - 1) 1 1 1 1 = (n ! )[ - + - … + ( - 1) n- 1 ] 1 ! 2 ! 3 ! n !
n

Cn ( n- n)!

n

②| ∩ Ai| =| U| -| U Ai| i= 1 i= 1 1 1 n 1   = (n ! )〔 2 !- 3 ! + … + ( - 1) n !〕 2. 4 数论中的应用 设 n为正整数 , 且 a1 , a2 , … aN 是 N 个两两互素的正整数 , 求满足 0 < k ≤n   ai K ( i= 1, 2, … N )的整数 k 的个数 。 解 : 设 U= { 1, 2, 3,… n }中是 ai 倍数的元素组成的集为 Ai ( i= 1, 2, … N ) n n 则有|Ai| = 〔 ai 〕  | Ai∩ Aj| = 〔 ai aj〕   i≠ j N n | ∩ = 〔 〕 Ai| i= 1 a1· a2… aN n n n 由容斥原理 , 所求数是 | ∩ Ai| = n- 1∑ 〔 〕+ … + ( - 1) N〔 〕 i= 1 ≤ i≤ N ai a1· a2… aN (其中〔 X〕表示不超过 x 的最大整数 ) 由上式易得欧拉函数 Υ( n ) (即: 1到 n 中 ,与 n 互素的数的个数 ) a a a 事实上 , 设 n 分解成素数幂的乘积 n= P1 1 · P2 2 … Pn n n n n 则由上式得 Ф ( n) = n- 1∑ + 1≤ ∑ - … + ( - 1) N ≤ i≤ N P i<j ≤ N Pi P i j P1… PN 1 1 1 1 1 1 n 1 1 1 = n- n( P1+ P2+ … + PN )+ n( P1 P2+ P2 P3+ … + PN- 1 PN ) - …± P1 P2… PN = n( 1- P1 ) ( 1- P2 )… ( 1- PN )
N

∴Υ( n) = n ∏ ( 1i= 1

1 1 )或 Ф( n) = n ∏ ( 1) P /n Pi P

参考文献: [ 1]卢开澄 . 组合数学算法与分析 [ M ]. 北京: 清华大学出版社 , 1983. [ 2]左孝凌 . 李为监 , 刘永才 , 离散数学 [ M ], 上海: 上海科学技术文献出版社 , 1981. (责任编辑: 姚有林 )


推荐相关:

容斥原理及应用.ppt

容斥原理及应用_数学_自然科学_专业资料。§3.1 容斥原理引论第三章 容斥原理


容斥原理及其应用_李琼琳.pdf

容斥原理及其应用_李琼琳 - 基础及前沿研究 Fundamental and f


容斥原理及其应用_卢金余.pdf

容斥原理及其应用_卢金余 - 第 22 卷第 4 期 2016 年 8 月 JO


浅论容斥原理及其应用.txt

浅论容斥原理及其应用 - 第十五卷 第三、四期 四川教育学院学报 1999. 4 浅论容斥原理及其应用 刘雅宁 到使用一个称之为容斥原理的问题 ...


容斥原理及其应用_王竞才.pdf

容斥原理及其应用_王竞才 - 2005年 11月 第 15卷 第 5期 榆林学院


容斥原理及其应用_图文.doc

容斥原理及其应用 - 龙源期刊网 http://www.qikan.com.cn 容斥原理及其应用 作者:卢金余 耿玉仙 来源:《江苏理工学院学报》2016 年第 04 期 摘要:容斥原理...


2第二章 容斥原理及其应用_图文.ppt

2第二章 容斥原理及其应用_工学_高等教育_教育专区。曹汝成 组合数学 华南理工大学 第二章 容斥原理及其应用 inclusion and exclusion principle §1 容斥原理 容斥...


容斥原理及其应用_论文.pdf

容斥原理及其应用 - 第2 2 卷第4 期 2016年8 月 江苏理工学院学报


容斥原理公式及运用.doc

容斥原理公式及运用在计数时,必须注意无一重复,无一遗漏。为了使重叠部分不被重复计


容斥原理及其简单应用_崔军.pdf

容斥原理及其简单应用_崔军 - 第 10卷总 34期 V o l. 10 Sum


第四章(Chapter 4)容斥原理及其应用_图文.ppt

第四章(Chapter 第四章(Chapter 4) 容斥原理及其应用(The


容斥原理的推广及其在奥数中的应用_图文.pdf

容斥原理的推广及其在奥数中的应用 - 第3 0卷V01.30 第l期 成 都师范


6.容斥原理及其应用(一)_图文.pdf

6.容斥原理及其应用(一) - 第六讲 容斥原理及其应用 (一) 容斥原理是一种


容斥原理及应用_图文.ppt

容斥原理及应用 - 第六章 容斥原理及应用 6.1容斥原理 容斥原理是讨论包容和


奥数精讲 第10讲讲义 容斥原理的应用 (教师)_图文.doc

第10 讲 容斥原理应用 熟练运用容斥原理解决计数问题。 教学目标 培养学生分


7.容斥原理及其应用(二)_图文.pdf

7.容斥原理及其应用(二) - 第七讲 容斥原理及其应用 (二) 1.1 1.2


容斥原理的推广及其在奥数中的应用_图文.pdf

容斥原理的推广及其在奥数中的应用 - 第30卷第1期V01.30 成都师范学院学


容斥原理的拓展及其应用_唐善刚.pdf

容斥原理的拓展及其应用_唐善刚 - 第 45 卷 第 12 期 Vo l . 4


容斥原理的推广及其在奥数中的应用_古传运.pdf

容斥原理的推广及其在奥数中的应用_古传运_数学_自然科学_专业资料。奥数学习!第


第六章(Chapter 6)容斥原理及其应用_图文.ppt

第六章(Chapter 第六章(Chapter 6) 容斥原理及其应用(The

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com