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

容斥原理及应用


年 12 4 卷 第 1

2 000

胜 利 油 田 师 范专 科 学 校 学 报
J
o u r n a

D

e e

.

20 00

l

o

f Sh

e n

g li O il f i l d T

e

e a e

h

e r s

e o

ll g

e

e

V

o

l 14

.

N

o

.

4

容 斥 原 理 及 应 用
于 其芳
( 胜 利油 田 师 范学 校

山 东省 东 营市

2 5 7 09 7 )





利 用 集 合 的 包含 与排 除 关 来解 决 问 题 的 策 略 通 常 称 为 容 斥 原 理
,
、 、

,



它 的 实质 是 一 种 计 数 工 具
,



当 一种 对 象的


卜 计 数 不 容 易计 葬 时 利 用 集 合 的 交 并 苹 运 茸 进 行 转 化 从 而 使 问题 得 到 解 决

,



其应 用 较 为 广 泛 在数 学竟 赛 中 也 经 常 用 到

关键 词

集合

子集

相容

相斥

1

原理
定义 定义 定理
1 2
1

对 于 集合 有限集 合 若
,

A A

,

B

,


I

A

n

B

并⑦ 则 称 A 与 B 相 容 ; 若 A n B 一 ⑦ 则 称
,

,

,

A



B

相斥



c a d (A ) 的 元 素 个 数 记为 r



是有 限 集
, ,

的子 集 则
x

c a r

d (A ) =

。 a r

d (I )一ea r d (A )
;

证明

x

采 用 赋 值法 即 当
〔 A
2

任对
A
,

时 记
,

,

。 a r

d (对 ) = l
,


x

x

告M 时 记
,

,

e a r

d(M ) = 0

则 cr a d (A ) ~

1 A

,


,

里I
:



r d(I a ) 一 1 此时

告A

C

r d (A ) 一 O a

有 1一 1 一 。 定理 成 立

,



定理

对 于 有 限集 合 设
,

B



e a r

d (A L JB )一

c a r

d (A ) +

。 a r

d ( B ) 一。 a r d ( A 自B )

证明

二任

A

UB 则
,


,

c a r

d (A U B )一 1

( l ) 若 八 自召 = ② 则
1 一 O+ 1 一 O

c a r

d (八

自召 ) =
x

o

,

c a r

d(八)

,

c a r

d ( B ) 的值



个为
,

1

,

另一个 为



,



z 一 1+ o 一 。

或 同

定 理成立
x

(2 )



A

门B 护 O 当
,

x

任A 而

在B 时
;

,

。 a r

d (八 ) 一 l

,

Ca r

d (B ) = o

。 a r

d ( A 门B ) 一 。


,



1= 1+ o 一 。

;

理 当

,

x

〔 B 而

在A
,

时 有

,

1一 0 十 1一 。


:

x

任A

门B

时 有
d(A

,

1一 1+ 1一 1

定理 成 立

推论
e a r



A

B

是 有限 集
ea r

I

的子 集 则
,

,

d (A

门B ) 一
。 a r

d(I)一

。 a r

d ( A ) 一。a r d ( B ) +

。a r

门B )


证明 由定 理
e a r

因 为 ( 八 U 召 ) U ( 万门万) = I 得
3

( 八 U 刀 ) 自 ( 万门万) 一 ②
d (八
,

1

d ( 万门云) 一
八 B
, ,

Ca r

d (I )一
I

Ca r

U 召 ) 再 由定 理 2 即 得 证
c a r

,

定理


。a r

C

是 有 限集
门C ) 一
。a r

的子集 则 有
d (B

d (八 U B U C ) 一

Ca r

d (八 ) +

c a r

d (B ) +

c a r

d(C )一

d (A

门B ) 一
d(A

e a r

d (A

c a r

门C ) +

。 a r

d (A
c a r

门B 自 C )
。a r

推论
e a r

自B 门 C ) =
。 a r

d (I ) 一

。a r

d (A )一

d (B )一

d (C ) +

。 a r

d ( A 门B ) +

c a r

d (A

门C ) +

d(B
3

门C ) 一

d (A

自 B 门C )
2



定理

的证 明 方法 同定 理

( 证 明略 )
I

定理

4
1



A

:

,

A

Z

,

… …A
A
·

都是 有 限 集

的子 集 则 有

,

:

…d (A
推论

Z UA U…… U

,一





/ 二d` A ,一


,

… d` A
:

/

n

A, , +



桑…

*

d` A

/

n

A少

n

A乏 , +

……

+ (一 1 )



一 ` e a r

d ( A l〕 A: 自… … 门 A )
l
,



A

:

,

A:

,

…… A

,

是 有限集

I

的子 集 则 有

收 稿 日期

2 0 0 0 一 1 0一 0 8

于 其 芳 容 斥 原 理 及应 用

:

e a r

d (A
1

l

: ) 一。 a 门 A 门 … … 门凡
.

r

d (, )一



。 a r

d (八 )+


`


e a r



二 d (“ 门八 , ’ ,


汇< j

。 a r

d ( A`

<k
,

n

A,

n

A

*

)十……

+ (一` ,

“纂 一 d (
4
1




A

, 1

门A

/Z

n


、 门A ) + … … + ( 一 1 )


d(A

Z 自 A 自… … 自 A

定理
定理

的证 明用 数 学 归纳 法 定理
2


( 证 明略 )
4

定理

3

都是 定 理

的特 殊 情 形



应用
例 解
召=

,

1

求 1~

{


100 0

的 自然 数 中能 被
11
,

7

或 n 整 除 的 数 的个 数
7

A 一

{1 ~ 1 0 0 0

的 自然数 中能被 整 除 的数 }


整 除 的数 }
, 二 、

1 ~ 10 0 0
,
,

中能 被
r -

,

_ 1000 , , r 立」 14 2 d ( A ) = `[ 翌 苦 一 则 e- a J 一 7 一 一 。a r d (A U B ) 一。a r d ( A ) + 所以
,






,







e a r
-



`







生 d (B ) = 「 = 90 兴拼〕 J


1000 1I

,

_

_ ,


,

e a r



。 a r

d ( B ) 一 。 a r d ( A 门 B ) 一 1 4 2 + 90 一 1 2 ~ 2 2 0










d (A 门B )~ 「 一 12 去岑锐 飞 ` J “ ~


~

_



1000

,
,


“ ” 一



7X 1I

`

答 例
:

:

1~ 1000 2
;

的 自然 数 中能 被
,

7

或 n 整 除 的数 共 有 2 0 2 个
,

学 校 开 运 动会 某班 8 2 名 同 学 参 加 比赛 其 中 1 5 人 参 加游 泳 比 赛
4

,

8 3

人 参加 田 径 比 赛 1 4 人参 加 人 没 人 同 时 参 加三 项 比 赛
, ,


,

球 类 比 赛 同 时 参 加 游 泳 和 田 径 比 赛 的有

人 同 时 参 加 游 泳 和 球 类 比赛 的 有
,

,

问 同时 参 加 田 径 和 球 类 比 赛的 有 多 少 人 ? 只 参 加 游 泳 一项 比 赛 的 有 多 少 人 ?


e a r
e a r

设 A ~ {参 加 游泳 比 赛 的同 学 } B 一 {参加 田 径 比 赛 的 同学 } C 二 {参 加 球 类 比 赛 的同学 } 则
d (A ) 一 15
d(A
,

,

c a r

d(B ) 一8
o
,

,

。 a r

d ( C ) = 14
3

,

c a r

d (A U B U C ) = 28

,

c a r

d(A

自C ) 一
o

3

,

。a r

d (A

门B ) =

4

,

门 B 自C ) ~

根 据定 理
Ca r



2 8 = 1 5 + 8 + 14 一 3 一 4 一 。 a r d ( B
e a r

自C ) +

所以

d (B

门C ) 一 2


e a r
:

d( A )一

。 a r

d (A

自B ) 一


d(A

自C ) ~
2
;

15一 4一 3一 8

答 同时参 加 田 径 和 球 类 比 赛 的有

人 只参 加 游 泳 一 项 比 赛 的有 8 人
,

例 解

一 3!

3

在 设

a



b




,



d
,


,



f 六 个 字母 的全 排 列 中 求 不 允 许 出 现 a b
,





d
,



的 排 列 个数
,



I一

{a b



d



,

f 的 全 排列 }
a
。 占

,

A 一

{I 中 出现 a b
,



的全 排 列 }
,

B 一

I 中出 现 d 。 的全 排 列 } 笼
e a r

,

八 门B 一

{ I 中同 时 出 现

和 d 。 的全 排 列 }
a r

。 a r

d ( I ) = 6!

c a r

d (八 ) ~ 4 !

d(B )= 5!

,

e a r

d (A

门B )

所以
:

。a r
a


d (A b


门B ) 一 c a r d ( I ) 一 e


d ( A ) 一。 a r d ( B ) +
,

。a r


d ( A 门B ) = 6 !


一4 ! 一 5 !
2

+ 3 ! ~ 58 2


答 在 例
4

`

d




l



f 六 个字 母的 全 排 列 中 不 出现 a b
x


和 d 的 排 列 个数 是 5 8
6 6
,



求方 程

`

x


+
3

Z

+

x

3



x

;

一2 0
x
,

中 至 少有 一 个 未 知数 的值 大 于


,

的 正 整 数解 的 个 数




ea r
e a r
,

A

l



A

:

A

A

4

分 别表 示
, , ,

:

x

:



x

3、

x

4

的 值大 于
7 3
l : 门A

的 正 整 数 解的 集 合 则
O

d (A )一C
d (A


13 3

(i ~ 1 2 3 4)


e a r

` , d ( A 门A ) = C

( 1蕊 i ( j 镇 4 )
3 ` 门A 门A ) =

自A

,

门K ) ~

0

( 1成 i

<

少(

4)

,

e a r

d (A

因此 方 程 中 至 少 有 一 个 未 知 数 的 值 大 于

6
`

的 正 整 数 解 的 个 数是

一d ( A
e a r

l

U

A

Z

UA U

3

A

4

,一

一d (A 答
33

,一
73

一d(A 髻

`

n

A, ,+

`

d` A 鬓…
*



门A n



A庵 , -

l Z ` : d ( A 自 A 门 A 3门 A )二 4 C

一 C

4 2

C

= 934

参 考文献
裘宗沪
.

奥林 匹 克 数 学 教 程

,

开 明 出 版社

,

1994

( 贵 任 编辑

丁 永臻 )


推荐相关:

容斥原理及应用.ppt

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


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

第6章容斥原理及应用 - 组合数学第6章 容斥原理及应用 计算机与软件学院 陆


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

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


容斥原理及其应用.doc

容斥原理及其应用_数学_自然科学_专业资料。容斥原理及其应用福建省上杭职业中专学


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

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


容斥原理及应用_于其芳_图文.pdf

容斥原理及应用_于其芳 - 年 12 4 卷第 1 2 000 胜利油田师 范专


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

第10 讲 容斥原理应用 熟练运用容斥原理解决计数问题。 教学目标 培养学生分析...3、教师讲解: ⑴∠COB 是∠AOB 和∠COD 的重叠部分,由容斥原理可知:∠AOD=...


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

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


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

第六章 容斥原理及应用 - 随堂练习 ? 2n ? ? 2n ? 1 ? 2n


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

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


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

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

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