組合數學第二章第九節

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

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

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

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

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

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

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

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

9、中3，7出現的次數為偶數，其他1，5，9出現次數不加限制。,設滿足上述條件的n位數個數為cn，則其對應的指數型母函數為：,因此,例4 7個有區別的球放進4個有標志的盒子里，要求1，2兩個盒子必須有偶數個球，第3個盒子有奇數個球，求不同的方案個數。,這相當于從1234這4個數中取7個做允許重復的排列，即每個數字對應于每個球所放的盒子的序號。,這樣的排列數所對應的指數型母函數為：,因此,例5 r個有標志的球放進n個不同的盒子里，要求無一空