組合數(shù)學(xué)第二章第九節(jié)

1、2.9 費(fèi)勒斯（Ferrers)圖像,假設(shè)正整數(shù)n拆分成n=n1+n2+…+nk。 其中n1≥n2 ≥n3 ≥… ≥nk。將他們排成階梯形，左邊對(duì)齊，第一行n1格，第二行n2格，第k行nk格。,,,,,,3,2,2,1,1,2,3,4,例如：8=3+2+2+1,,,,,,,,,,,,,,1、什么是費(fèi)勒斯圖像,2、費(fèi)勒斯（Ferres)圖像的性質(zhì)：,(1)每一層至少有一個(gè)格子；,(3)行與列互換，即第1行與第1列互換，第2行與第2

2、列互換，……,也就是沿對(duì)角線旋轉(zhuǎn)180°，仍然是費(fèi)勒斯圖像；,后一個(gè)費(fèi)勒斯圖像稱為前一個(gè)費(fèi)勒斯圖像的共軛圖像，而且互為共軛。,(2)下一層的格數(shù)不多于上一層的格子數(shù)；,(1) 整數(shù)n拆分成k個(gè)數(shù)的和的拆分?jǐn)?shù)，與數(shù)n拆分成最大數(shù)為k的拆分?jǐn)?shù)相等。,因?yàn)檎麛?shù)n拆分成k個(gè)數(shù)的和的拆分可以用一個(gè)k行的圖像表示。所得的Ferrers圖像的共軛圖像最上面一行有k個(gè)格子。例如：,3. 利用Ferrers圖像可以得到一些關(guān)于整數(shù)拆分的結(jié)果：,

3、24=6+6+5+4+3 5個(gè)數(shù)，最大數(shù)為6,24=5+5+5+4+3+2 6個(gè)數(shù)，最大數(shù)為5,理由和(1)相類似。,因此，拆分成最多不超過m個(gè)數(shù)的和的拆分?jǐn)?shù)的母函數(shù)是：,(2) 整數(shù)n拆分成最多不超過m個(gè)數(shù)的和的拆分?jǐn)?shù)，與n拆分成最大不超過m的拆分?jǐn)?shù)相等。,正好拆分成m個(gè)數(shù)的和的拆分?jǐn)?shù)的母函數(shù)為,(3) 整數(shù)n拆分成互不相同的若干奇數(shù)的和的的拆分?jǐn)?shù)，與n拆分成自共軛的Ferrers圖像的拆分?jǐn)?shù)相等。,設(shè)整數(shù)n拆分為n=(2n1+1

4、)+(2n2+1)+…+(2nk+1)，其中n1>n2>…>nk。,構(gòu)造一個(gè)Ferrers圖像，第一行第一列都是n1+1格，對(duì)應(yīng)于2n1+1，第二行第二列都是n2+1格，對(duì)應(yīng)于 2n2+1，依此類推。,這樣得到的Ferrers圖像一定是自共軛的。,反過來，自共軛的Ferrers圖像也可以對(duì)應(yīng)到一些不同奇數(shù)的和。,例如17=9+5+3對(duì)應(yīng)的Ferrers圖像為：,(4) 正整數(shù)n剖分成不超過k個(gè)數(shù)的和的剖分?jǐn)?shù)，等于將n+

5、k剖分成恰好k個(gè)數(shù)的剖分?jǐn)?shù)。,不超過k層的Ferrers圖像的每一層加上一個(gè)格子，一一對(duì)應(yīng)到一個(gè)剛好k層的Ferrers圖像。,2.11 指數(shù)型母函數(shù),考慮n個(gè)元素組成的多重集，其中a1重復(fù)了n1次，a2 重復(fù)了n2次，…，ak重復(fù)了nk次，n=n1+n2+…+nk。從中取r個(gè)排列，求不同的排列數(shù)。,若r=n，即考慮n個(gè)元素的全排列，則不同的排列數(shù)為：,但是對(duì)于一般的r，情況就比較復(fù)雜了。,先看一個(gè)具體的問題：假設(shè)有8個(gè)元素，其中a1

6、重復(fù)3次，a2重復(fù)2次，a3重復(fù)3次。從中取r個(gè)組合，其組合數(shù)為cr，則其對(duì)應(yīng)的母函數(shù)為：,從x4的系數(shù)可知，從這8個(gè)元素中取4個(gè)組合，不同的組合數(shù)為10。,這10個(gè)組合可從下面的展開式中得到：,,其中4次方項(xiàng)表示了所有從8個(gè)元素中取4個(gè)的組合方案。,例如 表示一個(gè)a1三個(gè)a3的組合， 表示兩個(gè)a1兩個(gè)a3的組合，依此類推。,接下來討論從這8個(gè)元素中取4個(gè)的不同排列總數(shù)。,以兩個(gè)a1兩個(gè)a3組合為例，不同排

7、列數(shù)為4!/(2!2!)。,同樣一個(gè)a1三個(gè)a3的不同排列數(shù)為4!/(1!3!)。,依此類推可以得到不同的排列總數(shù)為：,為了便于計(jì)算，利用上述特點(diǎn)，形式地引進(jìn)函數(shù),從右邊很容易可以看出，取2個(gè)的排列數(shù)為9，取3個(gè)的排列數(shù)為28，取4個(gè)的排列數(shù)為70…依此類推。,定義：對(duì)于序列a0,a1,a2,…，函數(shù),稱為序列a0,a1,a2,…對(duì)應(yīng)的指數(shù)型母函數(shù)。,這樣，對(duì)于一個(gè)多重集，其中a1重復(fù)n1次，a2 重復(fù)n2次，…，ak重復(fù)nk次，從中取

8、r個(gè)排列的不同排列數(shù)所對(duì)應(yīng)的指數(shù)型母函數(shù)為：,例1 求下列數(shù)列的指數(shù)型母函數(shù)：,例2 由1，2，3，4四個(gè)數(shù)字組成的五位數(shù)中，要求數(shù)1出現(xiàn)次數(shù)不超過2次，但不能不出現(xiàn)； 2出現(xiàn)次數(shù)不超過1次； 3出現(xiàn)次數(shù)最多3次，可以不出現(xiàn)；4出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個(gè)數(shù)。,設(shè)滿足上述條件的r位數(shù)個(gè)數(shù)為cr，則其對(duì)應(yīng)的指數(shù)型母函數(shù)為：,由此可見滿足條件的5位數(shù)共215個(gè)。,例3 求由1，3，5，7，9五個(gè)數(shù)字組成的n位數(shù)的個(gè)數(shù)，要求其

9、中3，7出現(xiàn)的次數(shù)為偶數(shù)，其他1，5，9出現(xiàn)次數(shù)不加限制。,設(shè)滿足上述條件的n位數(shù)個(gè)數(shù)為cn，則其對(duì)應(yīng)的指數(shù)型母函數(shù)為：,因此,例4 7個(gè)有區(qū)別的球放進(jìn)4個(gè)有標(biāo)志的盒子里，要求1，2兩個(gè)盒子必須有偶數(shù)個(gè)球，第3個(gè)盒子有奇數(shù)個(gè)球，求不同的方案?jìng)€(gè)數(shù)。,這相當(dāng)于從1234這4個(gè)數(shù)中取7個(gè)做允許重復(fù)的排列，即每個(gè)數(shù)字對(duì)應(yīng)于每個(gè)球所放的盒子的序號(hào)。,這樣的排列數(shù)所對(duì)應(yīng)的指數(shù)型母函數(shù)為：,因此,例5 r個(gè)有標(biāo)志的球放進(jìn)n個(gè)不同的盒子里，要求無一空