組合數(shù)學(xué)ch03-3

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

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

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

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

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

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

7、與集合的分劃相關(guān) 集合有7個(gè)2-分劃，但我們要求將每個(gè)分劃塊做成圓排列（或者輪換），則共可構(gòu)成11個(gè)不同的圓排列組，如圖3.5.1所示,定義3.5.3 一個(gè)n元集合的全部k-分劃所形成的不同的圓排列組的個(gè)數(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}單獨(dú)構(gòu)成一個(gè)圓排列，只需對(duì)集合A-{an}進(jìn)行(k-1)-圓排列分劃，再加上{an}這個(gè)圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個(gè)。,第2類： {an}不是A的k-圓排列分劃中的單獨(dú)一個(gè)圓排列，此時(shí)，先構(gòu)造A-{an}的k-圓排列分劃，共有 種方法，然后對(duì)于A-{an}的每個(gè)k-圓排列分劃，將an插入該k-圓排列分劃的k個(gè)

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

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

11、個(gè)數(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的所有有序分拆，對(duì)于4的有序3-分拆4=2+1+1而言，第1個(gè)分部為2，第2個(gè)和第3個(gè)分部均為1。若考慮無序分拆，則4有如下5個(gè)無序分拆， 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-分拆個(gè)數(shù)為,證明 正整數(shù)n分成k個(gè)分部的一個(gè)有序分拆等價(jià)于方程的一組正整數(shù)解由定理3.3.4正整數(shù)n的有序k分拆個(gè)數(shù)為,定理3.6.2 （1）正整數(shù)n的有序k-分拆，要求第i個(gè)分部大于等于pi，分拆個(gè)數(shù)為 （2）正整數(shù)2n分拆成k個(gè)分部，各分部都是正偶數(shù)的有序分拆個(gè)數(shù)為,,證明（1）設(shè) （3.6.2）是n滿足條件

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

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

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

16、 （3.6.8）我們?cè)谒街本€上畫 個(gè)點(diǎn)，在其下面一條直線上畫 個(gè)點(diǎn)，且使這兩條直線上的第一個(gè)點(diǎn)在同一條豎線上，其他點(diǎn)依次與上一行的點(diǎn)對(duì)齊；依此類推，最后在第k條直線上畫 個(gè)點(diǎn)，第一個(gè)點(diǎn)與前面各行的第一個(gè)點(diǎn)均在同一條豎線上，其他點(diǎn)依次與上面各行的點(diǎn)對(duì)齊， 這樣得到的點(diǎn)陣叫做n的k-分

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

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

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

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

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