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. (责任编辑: 姚有林 )



推荐相关:

容斥原理问题

容斥原理问题_其它_工作范文_应用文书。容斥原理问题的模型一、问题背景 容斥原理问题是人教版三、 年级数学下册数学广角里内容,使学生会借助直观 图, 利用集合的思...


论文:容斥原理的应用 (1)

论文:容斥原理应用 (1)_数学_自然科学_专业资料。由《集合中元素的个数》到...他们必须解决一个代数学问题、一个几何学问 题以及一个三角学问题。具体情况如...


上海奥数精讲 第10讲讲义 容斥原理的应用 (学生)

引入 容斥原理应用 熟练运用容斥原理解决计数问题。 教学目标 培养学生分析问题、解决问题的能 力,锻炼思维的缜密性。 联系生活实际, 使学生学到有用的数 学。...


...同步课程圆与扇形初步(修改版 公式 割补法 容斥原理 等应用)_...

【小奥】五年级寒假同步课程圆与扇形初步(修改版 公式 割补法 容斥原理应用) - 圆与扇形初步 1. 圆与扇形的定义: 平面上到定点的距离为定长的所有点组成...

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