chap32廣義容斥原理

1、例2 一個學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時修數(shù)學(xué)、物理的學(xué)生45人；同時修數(shù)學(xué)、化學(xué)的20人；同時修物理化學(xué)的22人。同時修三門的3人。假設(shè)每個學(xué)生至少修一門課，問這學(xué)校共有多少學(xué)生？13.3. 廣義容斥原理若將.1中的例子2改為“單修一門數(shù)學(xué)的學(xué)生有多少？”“只修一門課的學(xué)生有多少”“只修兩門課的學(xué)生有多少？”單修一門數(shù)學(xué)的用來表示，則有類似的2同樣的3設(shè)有與性質(zhì),2,n相關(guān)的元素N個，Ai為有第 i 種性質(zhì)的元素的集合.i=1,2,n定義a(0)=n；當(dāng)m1時b(m)是正好具有m個性質(zhì)的元素的個數(shù)。4例如，對于n=3,m=2利用這

2、些記號 b(1)=a(1)-2a(2)+3a(3) b(2)=a(2)-3a(3)5定理（廣義容斥原理）：特別的，當(dāng)m=0時6例1 某校有12個教師，已知教數(shù)學(xué)的有8位，教物理的有6位，教化學(xué)的5位；數(shù)、理5位，數(shù)、化4位，理、化3位；數(shù)理化3位。問教其他課的有幾位？只教一門的有幾位？只教兩門的有幾位？解:令教數(shù)學(xué)的教師屬于A1，教物理的屬于A2，教化學(xué)的屬于A3。則 a(0)12， a(1)|A1 |+|A2|+|A3 |8+6+519; a(2)|A1A2|+ |A1A3|+|A2A3|12； a(3)|A1A2A3|3； 7故教其他課的老師數(shù)為： b(0)=a(0)-a(1)+a(2)-

3、a(3)=2只教一門的教師數(shù)為： b(1)=a(1)-2a(2)+3a(3)=4恰好教兩門的老師數(shù)為： b(2)=a(2)-3a(3)=383.4.廣義容斥原理應(yīng)用1、非負(fù)整數(shù)解線性方程的非負(fù)整數(shù)解：非負(fù)整數(shù)解的個數(shù)為C(n+r-1,r)非負(fù)整數(shù)解一一對應(yīng)于r個相同的球放入n個不同的盒子中的方案9但對于方程求滿足附加條件的解的個數(shù)。若無上界條件限制，則非負(fù)整數(shù)解的個數(shù)為C(15+3-1,15)=C(17,2)10令 N為全體非負(fù)整數(shù)解；為其中的解；為其中的解；為其中的解；對于A1 ，相當(dāng)于求方程的非負(fù)整數(shù)解類似的 11故方程滿足條件的解為12另解： 做變量替換則問題轉(zhuǎn)化為求方程的非負(fù)整數(shù)解。其

4、個數(shù)為C(3+3-1,3)=C(5,2)=10132、第二類Stirling數(shù)的展開式先考慮m個有標(biāo)志的球放入n個有區(qū)別的盒子,無一空盒的情形14則m個有標(biāo)志的球放入n個有區(qū)別的盒子,無一空盒的方案數(shù)為153、錯排問題的推廣例如，3個中取2個的排列有P(3,2)=6個，其中D(3,2,0)= 3 21 31 23D(3,2,1)= 2 13 32D(3,2,2)= 1 12164、n對夫妻問題n對夫妻圍一圓桌坐下，要求男女相鄰而又避免夫妻座位相鄰，求這樣的方案數(shù)。從1,2,n中取r個不相鄰的數(shù)的組合方案數(shù)為 C(n-r+1,r)首先討論問題：假定數(shù)1,2,n沿一圓周排列，整數(shù)k滿足0k n/2

5、，其k元子集中無一相鄰數(shù)的方案數(shù)為c(k)(1和n相鄰)。17定理：證明：設(shè)di表示這樣的k元子集中含有元i的數(shù)目設(shè)A1表示含有元1的k元子集，則A1不含有2和n，故它的其他k-1個元素是從3,4,.,n-1中取不相鄰的18又由于每個集合有k個元素，因此求和時每個子集都重復(fù)計(jì)算了k次，故有19假定n位夫人先依次圍圓桌坐下，要求相鄰兩位之間留下一個空位。然后，她們的丈夫 再找空位坐，這樣保證了男女相間而坐。設(shè)正好有r對夫妻相鄰而坐的方案數(shù)為M(n,r)，則20證明：設(shè)N是所有 的所有排列的集合注意：21對于n k 2n對于0 k n22特別的，當(dāng)r=0時235、墨比烏(Mbius)反演定理定義：

6、墨比烏函數(shù)例如，30235，u(30)=-11211111，u(121)=024定理（墨比烏反演定理）設(shè)f(n)和g(n)是定義在正整數(shù)集合上的兩個函數(shù)，則的充要條件是稱f(n)是g(n)的墨比烏變換， g(n)是f(n)的墨比烏逆變換。256、可重圓排列在元素可重復(fù)的情況下，一個圓排列在n個位置斷開形成的n個線排列未必都不相同。例如當(dāng)d|n時，由不重復(fù)的d個元素重復(fù)n/d次構(gòu)成的圓排列只能形成d個不同的線排列。若一個圓排列可由一個長度為k的線排列重復(fù)若干次形成，則這樣的k中最小者稱為該圓排列的周期。一個圓排列中元素的個數(shù)（重復(fù)者按重?cái)?shù)計(jì)）稱為它的長度。26設(shè)由集合1,2,m中元素形成的長度與周期都是d的