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

1、2.9 費勒斯（Ferrers)圖像,假設正整數(shù)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)圖像的性質(zhì)：,(1)每一層至少有一個格子；,(3)行與列互換，即第1行與第1列互換，第2行與第2

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

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

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

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

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

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

8、r個排列的不同排列數(shù)所對應的指數(shù)型母函數(shù)為：,例1 求下列數(shù)列的指數(shù)型母函數(shù)：,例2 由1，2，3，4四個數(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ù)的個數(shù)。,設滿足上述條件的r位數(shù)個數(shù)為cr，則其對應的指數(shù)型母函數(shù)為：,由此可見滿足條件的5位數(shù)共215個。,例3 求由1，3，5，7，9五個數(shù)字組成的n位數(shù)的個數(shù)，要求其

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