冀东学刊199年第6期容斥原理在组合数学中的若千应用吴国柱大家知道IA设A,郝端绪则3,容斥原理的内容是Z,……n,,A一:,表示有限集合I的子集二(An,UA(AZU…UA::)=’二(A;,:)I飞+AnZ:(A)+…+(A`)Z〔n(A;:门AZ)+(A一nK(A;自A:)+…+自AK卜自A1:)〕+〔n(A门自A3)+nK(A自A自A)+…+n:门A;)〕-…+(一一)(A盆n(:AA:n…nAn)简写为U…UAK(A:日A:)一艺n(A*)艺n(A;自As)+…+(1)K一`n,自A门一自AK)(1)以及n口A人厂丈n:U二勺A天》=;。:(I)一n(A一,UA:U…UA一K);=(I),一艺n(A)+艺n(A门As)一,(1)K`n(A自A:A自…f飞K)(2)在这里例1有多少个(A)表示有限集合中元素的个数n公式(1)(2)的用途极广,,在此仅就其在组合数学中的若干应用…,,简述于下在集合I~{1设A了飞2,3,200}中5能被3整除或能被5整除或能被7整除的数7整除的数组成的集合解n气BC分别表示I中能被3。。显然l)=「200〕i一L_。二一l3」二勺D皿、D尹一200〕「lL八。一S。二一l」=4U1、勺少=2001「lL-~代:e丫J=乙6并且n(_A自B)~2003X。一_513n、11`勺夕一「2001。_,。。。L万贾下J~人”u`。”切夕~「2001L亏贾下」一“,”`A自“【飞C’一。n二「L岚女刘n200〕一`n二~~一二~~一由公式(`),`中合要求的数共有二n`n(A日BUC)=+nn(A)+(B)+(C)一(A自B)一n(A「飞C)一n(B自C)(A自B口C)玉(6+“40+28一13一9一5十1~118(个)(答略,下同)例2央,,了个人站一横排照像若甲不站在最左端,乙不站在最右端,丙不站在正中有多少种不同的站法解,设I表示7个人在一横排的任意排列组成的集合A(BC)分别表示I中甲站在,最左端(乙站在最右端=n丙站在正中央)的排列组成的集合(A自B)=n显然nI“!7()n(nA)(B)=n(C)一6!n(A日C)=n(B自C)=5!(A自B口C)=41由公式所求的站2法有