资源描述：
《容斥原理及一般公式.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广州航海高等专科学校学报NO.21995serialNO总第5期1995年第2期.e1995l:死1995年12月Journalof6uarlgzhouMaritimeCollege容斥’原理及一般公式唐续俞(广州航海高等专科学校基础部广州510725):,。摘要通过对容斥原理及一般公式的证明及说明导出有限集合运算后的计数公式:,集合;有限集关锐调容斥原理:0中图法分类号157O前言,,我们知道有限集合AB的并A自B的元素数目}AUB}的计数公式为AB{二A{一B`月B{}U!一门(l),。见图1图中v为全集尹A溉nC今BnC图1图2A,B,,,2。对于三个有限集合
2、C的并AUBUC同样有相应的公式见图所示ABCAB}+,C,A`一B一ACAC!IUU}一}}+}八BI自C}}自}+I门Bn这其实是最简单的容斥原理.1.容斤原理:一一收稿日期1995072。·18·。将式(l)推广可得一般性的定理:,:,,,,.,定理l设AAA…A是有限集.日::”.``则{AUAUA犷UA{=刃}A}一U人}十!式n人门`一l三三IA,三三三.lA·,::一“+(一l)一{A门An…nA了(2)。证明用数学归纳证明n,:,:,:已知~2时有IAUA}~,A}+IAI一!A门AI。::·一_:假设一1时有}AuAu”uA}一``了,`j}A1一艺
3、艺}A门A}+艺工艺}AnA`一1`一t`)心二>户A`一…+(一2:::门}l)一}AnAn门A一l.,,:A:::】:,:::!UAU…UA一UA!}AUAUAU…UA一)UA1二}AUAU一:.::,一;.…U人}+}UAI一}AUAU…UA)门Al:::。,.,一:。但(AUAU…UA一)nA=(A门A)门A.)U…U(A门A)。。,..’d}(A:::)门::一::UAU…UA一A}=}(A门A)U(AU…U(A门A)}=}A门。...:::::n::A}+}AnAUA}+…+}A卜门A}一}A门AnA}一}A门A门A}一…一::.::i-1工`。`j}A一
4、门A一门A}+…+(一1)’!A门A门一nA一州!AnA!一艺艺}AnA,,::.nA}+…+(一1)}A门An…门Al,:.。``’:’!AU凡AU…UA1~工!At一}人n+}人门人门一”三三川三三三.lA“一,::+(一l)}AnAn…n.A!I:,。,定理2设AA…A是有限集合则.-::·`”A``.}万门万门门瓦I二N一工}}+入n一门街n+”三到川三.IA川,`:.总+(一l)IA门A门…门AIv.式中N是全集的元素个数(3)organ证明由eDM律:2:·:::·.万门万门万门“门凡~AUAUAU“UA及}万l=N一}Al和式(2)显然。。可得证毕。,,
5、容斥原理就是指式(2)和式(3)这两个公式我们是从式(2)推出式(3)的不难验证从。式(3)同样可推出式(2)2一般公式。下面将容斥原理推广到一般场合3,,:,。::::。定理关于性质AA…A的N个元素如果令户~!A}+}A1+…+!AI:::;::。P~}A门A}+}A门A}+…+}A一门A{.;:。P=}AnA门…门:.nA}::::::“··::一:q~!An万门…n瓦}+}万nAn万门门瓦}+”+}万n万门一n瓦门.AI:,:3`.::3..,g一IA门An万门万门…门万1+I滩门万门A门万门…门万1+…+l万..19门刀:门A一,.二门门A{,..`.。.叮
6、,,l:叮~IA门n…nA)(P二)则.`,`+;,`+2,一P一C(k干1l)P+C(k十22)P·。,。,,,,n一一士C(一k)户(k~012一)1(4):。2证明略[]以下作4点说明。,。,。,Z,(l)在公式(4)中若令P一Nq=!万门通n…门万}则式(4)便是容斥原理定理2。的式(3),,(2)定理l与定理2的式(2)(3)也可由式(4)加以证明因此式(4)也可称为更一般的容斥原理。,k~,,,,,.(3)在式(4)中如果则有q一:CP这是显然的事实、,,,n(4)由(1)条(即k二o时)及(3)条(即k=时)可知一般只需讨论h~12…一便可。3一般公式下
7、的简单情形。以下面就儿种简单情形(也是常见情形)加以说明.31当,~3时,(nl)=3k二l,,由式(4)如果令n~3k~1则有,::3q一P一ZP+3P亦即}A门石门亡I+}万nB门己十}万自万门CI~(IAI+}Bl+}Cl)一2(fAn、BC3AB!+.A门(I+I门})+}nBnC}(,。,k~22)=3,,由式(4)如果令n=3k一2则有,Z3q一P一3P亦即}万门刀门e}+l八n万门C{+}A门B门石}~(IA门B}+}A门c}+IB门CI)一3}A门B门C}.32n一4时当,(1)”~4k一1,,由式(4)如果令n=4k二1则有ql::
