組合數(shù)學ch03-3

1、第三章 基本計數(shù)方法及應(yīng)用,一、集合的排列和組合(§3.1 ,§3.2.1 )二、圓排列（環(huán)排列） (§3.2.1 )三、排列和組合的生成 (§3.2.2 )四、多重集的排列和組合(§3.3 )五、二項式系數(shù) (§3.4 )六、Stirling數(shù) (§3.5 )七、分拆問題

2、 (§3.6 )八、分配問題 (§3.7 ),§3.5 集合的分劃與Stirling數(shù),§3.5.1 集合的分劃與第二類Stirling數(shù),1, 集合的分劃的定義,3.其中每個Si稱為一個分劃塊，也把這個k-分劃記為：,,定義3.5.1 集合S的子集族稱為n元集S的一個k-分劃，如果這個子集族滿足每個Si非空； 當i≠j時，,例3.5.1 集合A

3、={1,,3,4} 的2-分劃,有7個，它們是：,定義3.5.2 一個n元集合的全部k-分劃的個數(shù)記為第二類Stirling數(shù)，表示為或 S2(n,k),2，第二類Stirling數(shù),（1）,（2）,幾條性質(zhì)：,證明 等式左邊 是集合的k-分劃的個數(shù)，這些k-分劃可以分成兩類： 第1類：{an}是A的k-分劃中的一塊，這時，只需對集合A -{an}進行(k–1)-分劃，再加上{an}這一塊，就構(gòu)成了A的k-分劃，

4、因此，這類分劃有 個,定理3.5.1 第二類Stirling數(shù) 滿足如下遞推關(guān)系,第2類： {an}不是A的k-分劃中單獨的一塊，此時，先構(gòu)造A -{an}的k-分劃，共有 種方法 然后，對于A -{an}的每個k-分劃，將an加到該k-分劃的k個塊中的某一塊，從而構(gòu)成A的k-分劃 因此由乘法原理，集合A的此類k-分劃共有 個 綜上以上，由加法原理,,定理3.

5、5.2,（1）,（2）,證明 由定理3.5.1中的遞推關(guān)系，有,（1）,,（2）,,這兩條性質(zhì)也可以用組合意義來解釋：,（1）,是n元集合 的2-分劃,數(shù)，先取出a1,則對于 a2,a3,…, an，每個元素都有兩種選擇，即與a1在同一塊里或者ai與a1不在同一塊里，不同的選擇就構(gòu)成了集合A的不同的2-分劃，但這里要排除掉a2,a3,…, an，都與a1在同一塊中的情形（此時不構(gòu)成集合

6、A的2-分劃,由此可知，n元集合A的2-分劃數(shù)為2n-1-1,（2） 是n元集合的(n-1)-分劃，由于分劃中各塊是非空的，所以每個(n-1)-分劃中必有一塊為兩個元素，其余各塊都恰有一個元素，所以，對于n元集合的每個(n-1)-分劃，只要確定了有兩個元素的那一塊，整個(n-1)-分劃就確定了 因此， 就是在n元集中選取2個元素的方法數(shù),,§3.5.2 第一類Stirling數(shù),第一類Stirling數(shù)也

7、與集合的分劃相關(guān) 集合有7個2-分劃，但我們要求將每個分劃塊做成圓排列（或者輪換），則共可構(gòu)成11個不同的圓排列組，如圖3.5.1所示,定義3.5.3 一個n元集合的全部k-分劃所形成的不同的圓排列組的個數(shù)，即k-圓排列分劃數(shù)記為第一類Stirling數(shù)，表示為 或S1(n,k),性質(zhì)(1)性質(zhì)(2)性質(zhì)(3)性質(zhì)(4),定理3.5.3 第一類Stirling數(shù)滿足如下遞推關(guān)系,證明：等式左邊 是

8、將集合的k-圓排列分劃數(shù)，這些圓排列組可以分成兩類： 第1類：{an}單獨構(gòu)成一個圓排列，只需對集合A-{an}進行(k-1)-圓排列分劃，再加上{an}這個圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個。,第2類： {an}不是A的k-圓排列分劃中的單獨一個圓排列，此時，先構(gòu)造A-{an}的k-圓排列分劃，共有 種方法，然后對于A-{an}的每個k-圓排列分劃，將an插入該k-圓排列分劃的k個

9、圓排列中的某一個圓排列中，共有n-1種不同的插入方法，因此集合A的此類k-圓排列分劃共有 個。 綜上以上分析，由加法原理，有,§3.6 正整數(shù)的分拆,正整數(shù)的分拆，就是把一個正整數(shù)表成若干個正整數(shù)之和。,整數(shù)分拆成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做分拆數(shù)。,定義3.6.1 正整數(shù)n的一個k-分拆是把n表示成k個正整數(shù)的和，即

10、 （3.6.1）的形式 其中 ， 叫做該分拆的分部 如果表達式（3.6.1）是無序的，叫做無序分拆，或簡稱為分拆,,若表達式（3.6.1）是有序的，即表達式（3.6.1）右邊的和不僅與各項的數(shù)值有關(guān)，而且與各項的順序有關(guān)，這樣的分拆叫做有序分拆 相應(yīng)的，叫做該有序分拆的第i個分部，n的k-分拆的個數(shù)稱為n的k-分拆數(shù)， n的所有分拆的

11、個數(shù)稱為n的分拆數(shù)。,,例如：4=4，4=1+3，4=3+1，4=2+2，4=2+1+1，4=1+2+1，4=1+1+2，4=1+1+1+1 是4的所有有序分拆，對于4的有序3-分拆4=2+1+1而言，第1個分部為2，第2個和第3個分部均為1。若考慮無序分拆，則4有如下5個無序分拆， 4=4，4=1+3， 4=2+2，4=2+1+1，4=1+1+1+1,§3.6.1 有序分拆定理3.6.1正整數(shù)n的

12、有序k-分拆個數(shù)為,證明 正整數(shù)n分成k個分部的一個有序分拆等價于方程的一組正整數(shù)解由定理3.3.4正整數(shù)n的有序k分拆個數(shù)為,定理3.6.2 （1）正整數(shù)n的有序k-分拆，要求第i個分部大于等于pi，分拆個數(shù)為 （2）正整數(shù)2n分拆成k個分部，各分部都是正偶數(shù)的有序分拆個數(shù)為,,證明（1）設(shè) （3.6.2）是n滿足條件

13、 （3.6.3）的一個有序k-分折，令則且滿足方程 （3.6.4）即是方程（3.6.4）的一組非負整數(shù)解。,,反之，若給定方程（3.6.4）的一組非負整數(shù)解 令則構(gòu)成n的一個有序k-分拆（3.6.2），且滿足條件（

14、3.6.3）。 所以，n的滿足條件（3.6.3）的有序k-分拆與方程（3.6.4）的非負整數(shù)解之間構(gòu)成一一對應(yīng)，由定理3.3.3可知，其個數(shù)為,（2）設(shè)2n的一個有序k-分拆滿足條件 （3.6.5）令 ，則有即 是n的一個有序k-分折。 反之，

15、 是n的一個有序k-分拆，令 ，則是2n的一個滿足條件（3.6.5）的有序k-分拆。 所以，2n滿足條件（3.6.5）的有序k-分拆數(shù)等于n的有序k-分拆數(shù)，為,§3.6.2 無序分拆與Ferrers圖,來表示n的k分拆的個數(shù)。,來表示n的所有分拆個數(shù)。,1，無序分拆,幾個性質(zhì),（1）,（2）,Ferrers圖，設(shè)n的一個k-分拆為

16、 （3.6.8）我們在水平直線上畫 個點，在其下面一條直線上畫 個點，且使這兩條直線上的第一個點在同一條豎線上，其他點依次與上一行的點對齊；依此類推，最后在第k條直線上畫 個點，第一個點與前面各行的第一個點均在同一條豎線上，其他點依次與上面各行的點對齊， 這樣得到的點陣叫做n的k-分

17、拆（3.6.8）的Ferrers圖。,2，無序分拆的Ferrers圖,共軛Ferrers圖所對應(yīng)的分拆叫做原分拆的共軛分拆,定理3.6.3 n的k-分拆的個數(shù)等于n的最大分部為k的分拆數(shù),證明 上面定義的分拆的共軛運算是一個映射，它將n的最大分部為k的分拆映射到n的k-分拆，例如，分拆（3.6.9）是12的最大分部為5的分拆，其共軛分拆（3.6.10）是12的一個5分拆，并且這個映射顯然是一一的，所以兩者相等。,若n的一個分拆與其軛

18、分拆相同，則該分拆稱為n的自共軛分拆。,定理3.6.4 n的自共軛分拆的個數(shù)等于n的各分部都是奇數(shù)且兩兩不等的分拆的個數(shù)。,證明 我們將借助于Ferrers圖建立一個n的各分部為奇數(shù)且兩兩不等的分拆到n的自軛分拆之間的一一對應(yīng)。 設(shè)n的一個分部為奇數(shù)且兩兩不等的分拆為（3.6.11）,其中由n的分拆（3.6.11），我們構(gòu)造n的一個自共軛分拆的Ferrers圖。 在第1行與第1列都畫n1+1個點，共有2n1+1個點

19、； 畫完第1行和第1列后，在第2行與第2列再各畫n2+1個點，共2n2+1個點；……；在第k行與第k列再畫nk+1個點，共2nk+1個點，,因為 所以如此畫出的n個點的點陣圖的每一行都不比下一行的點數(shù)少 因而是n的一個分拆的Ferrers圖，且由上面的構(gòu)造過程知道，該Ferrers圖一定是對稱的，當然其對應(yīng)的分拆是自共軛的。 顯然，上面建立的n的分部為奇數(shù)且兩兩不等的分拆

20、與n的自共軛分拆之間的對應(yīng)關(guān)系是一一的所以定理的結(jié)論成立。,定理3.6.5 n的分部兩兩不等的分拆數(shù)等于n的各分部量都是奇數(shù)的分拆數(shù)。,證明 我們采用的方法仍然是建立兩類不同的分拆之間的一一對應(yīng)。 在一個n的各分部均為奇數(shù)的分拆中，假設(shè)數(shù)2k+1出現(xiàn)p次，我們將p寫成2的冪次和的形式：根據(jù)數(shù)論的知識，這種表示法是唯一的。,我們將n的這個分拆的Ferrers圖中這個小點按下列方法重排：各行的小點數(shù)分別為 然后再將

21、各行按小點數(shù)遞減的順序排列，就得到n的另一個分拆的Ferrers圖。 在新的Ferrers 圖中，各行的點數(shù)為的形式，在各行點數(shù)的表達式 中，參數(shù)k和i中必有一個不同,所以各行的點數(shù)互不相同，因而它所對應(yīng)的分拆的各分部不同。顯然，上述建立了兩類分拆之間的一一對應(yīng)。因此，n的分部兩兩不等的分拆的個數(shù)等于n的分部都是奇數(shù)的分拆的個數(shù)。,§3.7 分配問題,所謂分配問題，就是把一些球放入一些