計(jì)數(shù)問題是組合數(shù)學(xué)研究的重要問題之一。已學(xué)過的一些計(jì)數(shù)方法：如加法法則，乘法法則，生成函數(shù)方法，遞推關(guān)系方法等。重要的計(jì)數(shù)原理：。容斥原理研究有限集合的交或并的計(jì)數(shù)。4.1

解：

2的倍數(shù)是：2，4，6，8，10，12，14，16，18，20。共10個；4.1容斥原理例1.

求不超過20的正整數(shù)中2或3的倍數(shù)的個數(shù)。否！因?yàn)?，12，18在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。3的倍數(shù)是：3，6，9，12，15，18。共6個；答案是10+6=16個嗎？故答案是：16-3=13

對于求兩個有限集合A和B的并的元素?cái)?shù)目，我們有即具有性質(zhì)A或B的元素的個數(shù)等于具有性質(zhì)A的元素個數(shù)和具有性質(zhì)B的元素個數(shù)減去同時具有性質(zhì)A和B的元素個數(shù)。(1)定理14.1容斥原理4.1容斥原理ABA∩BU4.1容斥原理定理24.1容斥原理AB

CA∩BA∩B∩CB∩CA∩CU例2.

一個學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時修數(shù)學(xué)、物理的學(xué)生45人；同時修數(shù)學(xué)、化學(xué)的20人；同時修物理化學(xué)的22人。同時修三門的3人。假設(shè)每個學(xué)生至少修一門課，問這學(xué)校共有多少學(xué)生？4.1容斥原理解：令A(yù)為修數(shù)學(xué)的學(xué)生集合；

B為修物理的學(xué)生集合；

C為修化學(xué)的學(xué)生集合；即學(xué)校學(xué)生數(shù)為336人。4.1容斥原理同理可推出：利用數(shù)學(xué)歸納法可得一般的定理：4.1容斥原理4.1容斥原理(4)定理3設(shè)是有限集合，則4.1容斥原理(5)容斥原理指的就是（4）和（5）式。用來計(jì)算有限集合的并或交的元素個數(shù)。例3.

求從1到500的整數(shù)中能被3或5除盡的數(shù)的個數(shù).4.2容斥原理的應(yīng)用解：令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合，B為被5除盡的數(shù)的集合.被3或5除盡的數(shù)的個數(shù)為解：令A(yù)、B、C分別為不出現(xiàn)a，b，c符號的集合。即有4.2容斥原理的應(yīng)用例4.求由a,b,c,d四個字母構(gòu)成的n位符號串中a,b,c都至少出現(xiàn)一次的符號串?dāng)?shù)目。a,b,c都至少出現(xiàn)一次的n位符號串?dāng)?shù)目為4.2容斥原理的應(yīng)用

例5.

用26個英文字母作不允許重復(fù)的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。4.2容斥原理的應(yīng)用解：所有排列中，令則出現(xiàn)dog字樣的排列，相當(dāng)于把dog作為一個單元參加排列，故類似有：由于god,dog不可能在一個排列中同時出現(xiàn)，故：4.2容斥原理的應(yīng)用

由于gum,dog可以在dogum中同時出現(xiàn)，故有：類似有4.2容斥原理的應(yīng)用4.2容斥原理的應(yīng)用其余多于3個集合的交集都為空集。4.2容斥原理的應(yīng)用

故滿足要求的排列數(shù)為：

例6.求不超過120的素?cái)?shù)個數(shù)。

4.2容斥原理應(yīng)用—素?cái)?shù)個數(shù)4.2容斥原理應(yīng)用—素?cái)?shù)個數(shù)4.2容斥原理應(yīng)用—素?cái)?shù)個數(shù)4.2容斥原理應(yīng)用—素?cái)?shù)個數(shù)4.2容斥原理應(yīng)用—素?cái)?shù)個數(shù)

注意：27并非就是不超過120的素?cái)?shù)個數(shù)，因?yàn)檫@里排除了2，3，5，7這四個數(shù)，又包含了1這個非素?cái)?shù)。2，3，5，7本身是素?cái)?shù)。故所求的不超過120的素?cái)?shù)個數(shù)為：27+4-1=30例7.錯排問題

n個元素依次給以標(biāo)號1，2，…，n。n個元的全排列中，求每個元素都不在自己原來位置上的排列數(shù)。設(shè)Ai

為元素i在第i位上的全體排列,i=1,2,…,n。則有|U|=n!，因元素i不能動，因而有：4.2容斥原理應(yīng)用—錯排同理

每個元素都不在原來位置的排列數(shù)為4.2容斥原理應(yīng)用—錯排

例8.數(shù)1,2,…,9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置的錯排數(shù)目。解：實(shí)際上是1，3，5，7，9五個數(shù)的錯排問題，總數(shù)為：4.2容斥原理應(yīng)用—錯排例9.在8個字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個字母不在原來位置上的錯排數(shù).

8個字母的全排列中，令分別表A,C,E,G在原來位置上的排列，則錯排數(shù)為：4.2容斥原理應(yīng)用—錯排

例10.求8個字母A,B,C,D,E,F,G,H的全排列中只有4個不在原來位置的排列數(shù)。

解：8個字母中只有4個不在原來位置上，其余4個字母保持不動，相當(dāng)于4個元素的錯排，其數(shù)目為4.2容斥原理應(yīng)用—錯排

故8個字母的全排列中有4個不在原來位置上的排列數(shù)應(yīng)為：C(8,4)·9=630.(n)是指小于n且與n互素的正整數(shù)的個數(shù)。

設(shè)1到n的n個數(shù)中pi倍數(shù)的集合為解：若n分解為素?cái)?shù)的乘積4.2容斥原理應(yīng)用—?dú)W拉函數(shù)例11.歐拉函數(shù)(n)

4.2容斥原理應(yīng)用—?dú)W拉函數(shù)則有4.2容斥原理應(yīng)用—?dú)W拉函數(shù)

即比60小且與60無公因子的數(shù)有16個：7，11，13，17,19,23，29，31，37，41，43，47，49，53，59，此外尚有一個1。4.2容斥原理應(yīng)用—?dú)W拉函數(shù)4.2容斥原理應(yīng)用—不定方程整數(shù)解個數(shù)35寫在最后成功的基礎(chǔ)在于好的學(xué)