Ch3-容斥原理及应用.pdf
- 文档编号:14648652
- 上传时间:2023-06-25
- 格式:PDF
- 页数:74
- 大小:370.84KB
Ch3-容斥原理及应用.pdf
《Ch3-容斥原理及应用.pdf》由会员分享,可在线阅读,更多相关《Ch3-容斥原理及应用.pdf(74页珍藏版)》请在冰点文库上搜索。
1容斥原理及应用容斥原理及应用Chapter3.云南大学计算机系云南大学计算机系Fall,2009Fall,20092容斥原理容斥原理?
容斥原理是求解计数问题常用工具之一,是加法原理的推广。
容斥原理是求解计数问题常用工具之一,是加法原理的推广。
?
容斥原理又称逐步淘汰原理,是组合分析中常用的计数原理。
其思考方法是将难的问题分解成若干简单问题,通过对这些简单问题的结果代数求和得到困难问题的解。
容斥原理又称逐步淘汰原理,是组合分析中常用的计数原理。
其思考方法是将难的问题分解成若干简单问题,通过对这些简单问题的结果代数求和得到困难问题的解。
3主要内容主要内容DeMorgen公式公式容斥原理与广义容斥原理容斥原理与广义容斥原理容斥原理的应用:
错排问题容斥原理的应用:
错排问题棋盘多项式与有限制的排列棋盘多项式与有限制的排列n对夫妻问题对夫妻问题4DeMorgan定理定理:
若若,UBA,定义定义:
有限集合中元素的个数称为基数有限集合中元素的个数称为基数,记为记为.表示小于等于的最大整数表示小于等于的最大整数;表示大于等于的最小整数表示大于等于的最小整数.BABABABA=,A|AxxxxDeMorgan定理的推广定理的推广:
若若,UAAAn,21LnnnnAAAAAAAAAAAA=LLLL212121215容斥原理容斥原理(TheInclusion-ExclusionPrinciple)例例1:
求不超过求不超过20的正整数中为的正整数中为2或或3的倍数的数的个数的倍数的数的个数.2的倍数是:
的倍数是:
2,4,6,8,10,12,14,16,18,20。
10个个3的倍数是:
的倍数是:
3,6,9,12,15,18。
6个个10616?
6容斥原理容斥原理(TheInclusion-ExclusionPrinciple)例例1:
求不超过求不超过20的正整数中为的正整数中为2或或3的倍数的数的个数的倍数的数的个数.2的倍数是:
的倍数是:
2,4,6,8,10,12,14,16,18,20。
10个个3的倍数是:
的倍数是:
3,6,9,12,15,18。
6个个但答案不是但答案不是10+6=16个,因为个,因为6,12,18在两类中重复计数,应减去。
故答案是:
在两类中重复计数,应减去。
故答案是:
16-3=137容斥原理容斥原理(TheInclusion-ExclusionPrinciple)例例2:
求求1到到600之间不能被之间不能被6整除的整数个数整除的整数个数.已知已知1到到600之间共有之间共有600个数。
因为,每个数。
因为,每6个连续的整数中恰有个连续的整数中恰有1个能被个能被6整除,所以共有个整数能被整除,所以共有个整数能被6整除,不能被整除,不能被6整除的数有:
整除的数有:
600100500个。
个。
1006600=8容斥原理容斥原理(TheInclusion-ExclusionPrinciple)例例3:
求求1,2,n的的1不在第一个位置上的全排列的个数不在第一个位置上的全排列的个数.设设,2,121niiinLL是的一个全排列,因的一个全排列,因1不在第一个位置上,所以。
不在第一个位置上,所以。
11i方法方法1(直接方法):
(直接方法):
3,21nkiL=,,1,1,132nkkiiinLLL+是)!
1(n,因此由加法原理知的全排列数是因此由加法原理知的全排列数是11i的一个全排列,其排列数的一个全排列,其排列数为为)!
1)(1(nn9容斥原理容斥原理(TheInclusion-ExclusionPrinciple)例例3:
求求1,2,n的的1不在第一个位置上的全排列的个数不在第一个位置上的全排列的个数.设设,2,121niiinLL是的一个全排列,因的一个全排列,因1不在第一个位置上,所以。
不在第一个位置上,所以。
11i方法方法2(间接方法):
已当时,是的一个全排列,其排列数(间接方法):
已当时,是的一个全排列,其排列数)!
1(的全排列数是的全排列数是n,因此因此1不在第一个位置上的全排列数是不在第一个位置上的全排列数是)!
1)(1()!
1(!
=nnnn,2,1nL!
n11=iniiiL32,3,2nL10容斥原理容斥原理(TheInclusion-ExclusionPrinciple)例例3:
求求1,2,n的的1不在第一个位置上的全排列的个数不在第一个位置上的全排列的个数.用集合语言描述:
用集合语言描述:
设设A有限集合有限集合S的一个子集,则的一个子集,则A中元素的个数中元素的个数等于等于S中元素的个数减去中元素的个数减去S中不在中不在A内的元素的个数。
内的元素的个数。
若记若记ASA=,则有,则有|ASA=11容斥原理容斥原理(TheInclusion-ExclusionPrinciple)?
定理定理1:
设是有限集合设是有限集合,是与集合有关的个性质是与集合有关的个性质,是中具有性质的元素构成的集合是中具有性质的元素构成的集合,是中不具有性质的元素构成的集合是中不具有性质的元素构成的集合,则中不具有性质的元素个数为则中不具有性质的元素个数为SnPPP,21LiAiAiP)1(ni|)1(|2111,121nnninjinjijiinAAAAAASAAA+=LLLSSSSniPnPPP,21L12?
特别特别:
时时时时2=n|)|(|212121AAAASAA+=3=n|)|(|)|(|321133221321321AAAAAAAAAAAASAAA+=13?
定理定理2:
设是有限集合设是有限集合,是与集合有关的个性质是与集合有关的个性质,是中具有性质的元素构成的集合是中具有性质的元素构成的集合,则中至少具有一个性质的元素个数为则中至少具有一个性质的元素个数为SnPPP,21LiAiP)1(ni|)1(|211111,121nnnkjikjininjinjijiinAAAAAAAAAAAA+=LLLSSSniP14?
特别特别:
时时时时2=n|212121AAAAAA+=3=n|)|(|321133221321321AAAAAAAAAAAAAAA+=15?
例例1:
1与与1000之间不能被之间不能被5,6,8整除的整数有多少个整除的整数有多少个?
321,AAA分别表示分别表示S中能被中能被5,6,8整除的整数集合,整除的整数集合,解:
设解:
设S=1,2,1000,则则|S|=1000.设设有有8)8,6,5(1000|,41241000)8,6(1000|,25851000|,33651000|12581000|,16661000|,20051000|321323121321=lcmAAAlcmAAAAAAAAA于于6008)412533()125166200(1000|)|(|)|(|321323121321321=+=+=+=AAAAAAAAAAAASAAA16?
例例2:
求这求这6个字母的全排列中不允许出现和图象的排列数个字母的全排列中不允许出现和图象的排列数.fedcba,acedf1Aace2Adf解:
解:
为为作为一个元素出现的排列集,作为一个元素出现的排列集,为为作为一个元素出现的排列集,作为一个元素出现的排列集,21AA为同时出现和的排列集,则为同时出现和的排列集,则acedf!
3|,!
5|,!
4|2121=AAAA于是,不允许出现和的排列数是于是,不允许出现和的排列数是acedf582!
3)!
4!
5(!
6|21=+=AA17?
例例3:
求由这四个字符构成的位符号串中求由这四个字符构成的位符号串中,至少出现一次的符号串数目至少出现一次的符号串数目.dcba,ndcba,4321,AAAA分别为不出现的位符号分别为不出现的位符号dcba,n串的集合。
由于位符号串的每一位都可以取串的集合。
由于位符号串的每一位都可以取ndcba,四个符号中的任一个,共有个,其中,不出现的四个符号中的任一个,共有个,其中,不出现的n4a符号串的每一位都可以取中的任一个,共有个。
符号串的每一位都可以取中的任一个,共有个。
dcb,n3类似地类似地0|,1|4,3,2,1,2|,3|4321=AAAAAAAjijiAAAkjinjini设设于于426344|4321+=nnnAAAA18例例4:
欧拉函数表示小于且与互素的个数欧拉函数表示小于且与互素的个数,求求.解解:
将分解成素因子的乘积形式将分解成素因子的乘积形式:
设为不大于且为的倍数的自然数的集合设为不大于且为的倍数的自然数的集合,则因与互素则因与互素,所以与的最小公倍数为所以与的最小公倍数为,所以小于并与互素的自然数是集合中的那些不属于任何一个集合的数所以小于并与互素的自然数是集合中的那些不属于任何一个集合的数,由容斥原理知由容斥原理知)(nnnnnnn)(nkkpppnL2121=iAipki1kipnAii,2,1/|L=ipjpipjp)(jijipp),2,1,(|kjijippnAAjijiL=,2,1nAL=),2,1(kiAiL=+=kkikjikkjiikpppnpppnppnpnnAAAn111111)1(|)(21112121LLLL19260235,111(60)60
(1)
(1)
(1)16235n=例如则即比即比60小且与小且与60无公因子的数有无公因子的数有16个:
个:
7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,此外尚有一个,此外尚有一个1。
=kpppnn111111)(21L欧拉函欧拉函20广义容斥原理广义容斥原理?
定理定理:
设是一有限集合设是一有限集合,是上的性质集合是上的性质集合,表示中具有性质的元素个数表示中具有性质的元素个数,令规定令规定,设集合中恰好具有个性质的元素个数为设集合中恰好具有个性质的元素个数为,则则S,21nPPPPL=),(21kiiiPPPNLSSkiiiPPP,21L=niiiiiikkPPPNkLL21211),()(n=)0(Sm)(m)()1()2()1()()(21nCmCmCmmnmmnmmmm+=L推推)()1()2()1()0()0(nn+=L21,21nxxxM=Lr?
例题:
具有有限重复数的多重集合的组合数例题:
具有有限重复数的多重集合的组合数r的组合数为的组合数为多重集多重集1+rnrC,相当于线性方程,相当于线性方程rxxxn=+L21的非负整数解的数目。
的非负整数解的数目。
22例例1:
求方程满足的整数解数目求方程满足的整数解数目.15321=+xxx70,60,50321xxx转化为求解问转化为求解问0,15321321=+xxxxxx的整数解数目的整数解数目减去问减去问8,7,6,15321321=+xxxxxx的整数解数目的整数解数目方法方法1:
显然,问题:
显然,问题0,15321321=+xxxxxx的整数解数目的整数解数目为为1361715131515=+CC对于问题对于问题8,7,6,15321321=+xxxxxx如何求解?
如何求解?
23令令N为全体非负整数解,为全体非负整数解,1A为其中的解,为其中的解,61x2A为其中的解,为其中的解,72x3A为其中的解。
为其中的解。
83x求问题求问题8,7,6,15321321=+xxxxxx的整数解数目。
的整数解数目。
24对于性质,相当于对于性质,相当于1A15)6(321=+xxx即即615321的非负整数解数目的非负整数解数目=+xxx的非负整数解,的非负整数解,112119136156151|CCCA=+同理,对于性质,同理,对于性质,2A102108137157152|CCCA=+对于性质,对于性质,3A9297138158153|CCCA=+于于10)3()2()1()0()0()0(0|)3(|)2(|)1(172171513151532113871587151386158615137615761532312192102112321=+=+=+=+=+=+CCCAAACCCAAAAAACCCAAA25方法方法2:
作置换:
作置换3322117,6,5xxx=则则0,3)(18321321321=+=+xxx求整数解数目,求整数解数目,10531333=+CC26例例2:
求的求的10组合数组合数.,cbaS=5,4,3cbaS=,则,则S的的10组合数为组合数为令令661210131010=+CC现在要求在现在要求在10组合数中组合数中a的个数小于等于的个数小于等于3,b的个数小于的个数小于等于等于4,c的个数小于等于的个数小于等于5。
定义性质集定义性质集,321PPPP=,其中,其中1P:
10组合数中组合数中a的个数大于等于的个数大于等于4;2P:
10组合数中组合数中b的个数大于等于的个数大于等于5;3P:
10组合数中组合数中c的个数大于等于的个数大于等于6;27将满足性质的将满足性质的10组合全体记为,于是组合全体记为,于是iP3,2,1,=iAi0|,0|,|,|321322013641065103131136410541021641361061037513510510286134104101=+AAAAACCAACCAACCACCACCA同同而而a的个数小于等于的个数小于等于3,b的个数小于等于的个数小于等于4,c的个数小于等于的个数小于等于5的的10组合全体为组合全体为321AAA,由容斥原理得,由容斥原理得6|321=AAA28例例3:
证明:
当时,由证明:
当时,由m元集元集A到到n元集元集B的满射个数是的满射个数是mnkknkknnmg=1)1(),(nm29容斥原理的应用容斥原理的应用错排问题错排问题(Derangements)?
设集合设集合,则的排列数为则的排列数为.若其中两个排列和若其中两个排列和,如果则称排列为的一个错位排列如果则称排列为的一个错位排列,简称错排简称错排.,2,1nSL=S!
nnL12niiiL21niiin,2,121LniiiL21nL12例例:
时时,不存在错排不存在错排.时时,1,2有唯一一个错排有唯一一个错排.时时,1,2,3有两个错排有两个错排.时时,1,2,3,4有有9个错排个错排.1=n3=n2=n4=n设的错排个数用表示设的错排个数用表示,则则nD,2,1nSL=9,2,1,04321=DDDD30?
定理定理:
对任意正整数对任意正整数,有有证明证明:
令是令是1,2,n的全排列的全体的全排列的全体,则则.定义上的性质集合定义上的性质集合,其中其中,表示排列中在左数第个位置上表示排列中在左数第个位置上,即在其自然顺序的位置上即在其自然顺序的位置上.令为中满足性质的全排列的全体令为中满足性质的全排列的全体.因中的每一个全排列形如而是的全排列因中的每一个全排列形如而是的全排列,所以有所以有1n+=!
1)1(!
31!
21!
111!
nnDnnLS!
|nS=S,21nPPPPL=iPii)1(niiASiPiAniijjjjLL111+niijjjjLL111+,1,1,2,1niiLL+)1()!
1(|ninAi=31同理同理,有一般地有一般地,有其中有其中,且互不相等且互不相等.因为中不满足性质的元素个数因为中不满足性质的元素个数,由容斥原理得由容斥原理得)1()!
2(|njinAAji=)!
(|21knAAAkiii=Lniiik,121Lkiii,21LnDSnPPP,21L+=+=!
1)1(!
21!
111!
0)1()!
2
(2)!
1(1!
|21nnnnnnnnnAAADnnnnLLL32例例1.数数1,2,3,9的全排列中的全排列中,求偶数在原来的位置上求偶数在原来的位置上,其余都不在原来位置上的错排数目其余都不在原来位置上的错排数目.解:
实际上是解:
实际上是1,3,5,7,9五个数的错排问题,总数为:
五个数的错排问题,总数为:
5!
(5,1)4!
(5,2)3!
(5,3)2!
(5,4)1!
1111(5,5)120()442624120CCCCC=+=33例例2.在在8个字母个字母A,B,C,D,E,F,G,H的全排列中的全排列中,求使求使A,C,E,G四个字母不在原来位置上的错排数目。
四个字母不在原来位置上的错排数目。
8个字母的全排列中,令分别表示个字母的全排列中,令分别表示A,C,E,G在原来位置上的排列,则错排数为:
在原来位置上的排列,则错排数为:
1234,AAAA12348!
(4,1)7!
(4,2)6!
(4,3)5!
(4,4)4!
24024AAAACCCC=+III34例例3.求求8个字母个字母A,B,C,D,E,F,G,H的全排列中只有的全排列中只有4个不在原来位置上的排列数。
个不在原来位置上的排列数。
解:
解:
8个字母中只有个字母中只有4个不在原来位置上,其余个不在原来位置上,其余4个字母保持不动,相当于个字母保持不动,相当于4个元素的错排,其数目为个元素的错排,其数目为9)!
41!
31!
21!
111(!
4=+故故8个字母的全排列中有个字母的全排列中有4个不在原来位置上的排列数应为:
个不在原来位置上的排列数应为:
C(8,4)9=63035例例4.证明:
表示集合的错排个数,则证明:
表示集合的错排个数,则nD,2,1nSL01211111210!
)3()(1()2()1()1(DnnDnnDnDnDnnDDnDnDDnnnnnnnnn+=+=+=L=36错排问题的推广错排问题的推广?
从中取个进行排列从中取个进行排列,得得,要求其中只有个数满足要求其中只有个数满足,这样的错排数用表示这样的错排数用表示,即有个数是错排即有个数是错排.例例:
4个数取个数取3个全排列共有个全排列共有,其中有其中有231,312,214,241,412,314,341,431,234,342,432有有132,213,321,142,421,134,413,243,324有有124,143,423有有123,2,1nNL=rraaaL21kiai=),(krnDkr24!
343=C1)3,3,4(3)2,3,4(9)1,3,4(11)0,3,4(=DDDD37定理定理:
对于整数对于整数,若若,krn,krn)!
()1()!
(),(0iknikrrnkrkrnDkrii=38性质性质:
nDnnDkrnDkrnDrkrnDnkrnDkrnDkrknDkrkrnD=+=)0,()3()1,2,2(),2,2()1(),1,1()1()1,1,1(),()2()0,(),()1(1334961,13349614833,1854,265,449,2,1,010987654321=DDDDDDDDDD39容斥原理的应用有限制的排列容斥原理的应用有限制的排列?
讨论某些元素之间的某种相对位置不能出现的一类排列讨论某些元素之间的某种相对位置不能出现的一类排列.用表示用表示1,2,n的不出现的不出现12,23,(n-1)n这些模式的全排列的个数这些模式的全排列的个数,并规定并规定.12,21123,132,213,231,312,3211234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321nQ11=Q2=n12=Q33=Q114=Q3=n4=n40定理:
对任意正整数定理:
对任意正整数,有有1n!
111)1()!
2(21)!
1(11!
1+=nnnnnnnQnnL证明:
令表示在排列中出现这一性证明:
令表示在排列中出现这一性jp)1(+jj1,2,1=njL),(21kiiipppnL表示同时具有性质的排列个数,表示同时具有性质的排列个数,kiiippp,21L则则)!
(),(21knpppnkiii=L)!
(1),(112121knknpppnniiiiiikk=LL从从!
111)1()!
2(21)!
1(11!
),()1(),()(!
),(12111111212121+=+=ndnnd|1,01,1)(rrpppnL2121=证明:
证明:
n=1时显然成立。
时显然成立。
n1时,设是时,设是n的素因子分解的素因子分解是是Mbius反演函数,则对一切正整数反演函数,则对一切正整数rpppnL21*=*n令令对于不能整对于不能整的的n的因子的因子n,可以断定,可以断定含有因子,而,因含有因子,而,因kkp1k0)(=d,因,因=ndnddd|*)()(根据的定根据的定0)1()1(321)()()()()()1()(*1211|*=+=+=rrkrrrrnppppppdrkrrrndLLLLL65Mbius反演定理反演定理?
和是定义在正整数集合上的两个函数,满足和是定义在正整数集合上的两个函数,满足)(nf)(ng=nddgnf|)()(=nddnfdng|)()(则则66例题讲解例题讲解67例例1:
试证满足下列条件:
试证满足下列条件nikxrxxxin,2,1,0,21LL=+的整数解数目的整数解数目+=11)1()1(1nnikrinnii68例例2:
求数字:
求数字1至至9组成的每种数字至少出现组成的每种数字至少出现1次的位数的个数。
次的位数的个数。
)9(nn69例例3:
设是一个字符集,由生成长度为的字符串,串中的字符可以相同。
(:
设是一个字符集,由生成长度为的字符串,串中的字符可以相同。
(1)证明:
当时,中的每个字符至出现一次的字符串个数是()证明:
当时,中的每个字符至出现一次的字符串个数是
(2)当时,推出一个的恒等式。
)当时,推出一个的恒等式。
21kaaaSL=SnnkS+1)1()2
(2)1(11kkkkkkkknnnLnk=!
n70例例4:
在由组成的排列中,求满足下列条件的排列数:
(:
在由组成的排列中,求满足下列条件的排列数:
(1)不存在相邻的)不存在相邻的3元素相同;(元素相同;
(2)相邻两元素不相同。
)相邻两元素不相同。
cccbbbaaa,71,2211kkanananS=L例例5:
,令是使得至少存在的一个组合的正整数。
证明:
在应用容斥原理确定组合数时,有:
,令是使得至少存在的一个组合的正整数。
证明:
在应用容斥原理确定组合数时,有rrrS=kAAAL21其中是满足条件其中是满足条件iAkinxrxxxiik,2,1,1,21LL=+=+的非负整数的非负整数72例6:
求由个相异元作成的不在第1位、不在第2位、不在第3位的全排列的个数。
例6:
求由个相异元作成的不在第1位、不在第2位、不在第3位的全排列的个数。
)3(nnnaaa,21L1a2a3a73例例7:
利用容斥原理证明:
利用容斥原理证明1,111)1(0=+=mnmnnkmnkmmkk74例例8:
(:
(1)求自然数)求自然数1到到n的全排列中不出现相邻两数相邻的全排列中不出现相邻两数相邻的排列数;的排列数;
(2)求)求0到到n-1的圆排列中不出现相邻数相邻的排列的圆排列中不出现相邻数相邻的排列数,包括数,包括n-1和和0作为相邻两个数。
作为相邻两个数。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Ch3 原理 应用