Ch4容斥原理a課件

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

解：

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

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

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

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

一個(gè)學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理的學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)的20人；同時(shí)修物理化學(xué)的22人。同時(shí)修三門的3人。假設(shè)每個(gè)學(xué)生至少修一門課，問(wèn)這學(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）式。用來(lái)計(jì)算有限集合的并或交的元素個(gè)數(shù)。例3.

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

例5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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