組合數(shù)學(xué)整數(shù)的分拆

1、2.6 正整數(shù)的分拆粗略地說，正整數(shù)的分拆就是將一個正整數(shù)分成幾個正整數(shù)的和。在本章的前幾節(jié)中已經(jīng)看到，某些重要和式的求和范圍都與正整數(shù)的分拆有聯(lián)系，在2.7節(jié)中我們將說明有一類分配問題就是“分拆問題”。分拆問題也是組合論的重要內(nèi)容之一，本節(jié)我們將介紹正整數(shù)的分拆的概念及其一些最基本的性質(zhì)，在2.7節(jié)中再將本節(jié)的一些結(jié)果應(yīng)用到一類分配問題。定義2.6.1正整數(shù)n的一個k分拆是把n表示成k個正整數(shù)的和（2.6.1）的一種表示法，其中叫做該分拆的分部量。如果表達式（2.6.1）是無序的，也就是說，對諸任意換位后的表示法都只視為一種表示法，這樣的分拆叫做無序分拆，或簡稱為分拆。反之，若表達式（2.6

2、.1）是有序的，即表達式（2.6.1）右邊的和不僅與各項的數(shù)值有關(guān)，而且與各項的次序有關(guān)，不同的次序認為是不同的表示法，這樣的分拆叫做有序分拆。這時，叫做該有序分拆的第i個分部量。n的k分拆的個數(shù)稱為n的k分拆數(shù)，n的所有分拆（k取遍所有可能的值）的個數(shù)稱為n的分拆數(shù)。例如：是4的所有3個有序3分拆。在4的第一個有序3分拆中，第1個分部量為2，第2個和第3個分部量均勻為1。而：是4的唯一一個3分拆。2.6.1 有序分拆在這一小節(jié)中，我們介紹n的有序分拆的計數(shù)公式，以及在幾類限定條件下n的有序分拆的計數(shù)公式。定理2.6.1 正整數(shù)n的有序k分拆的個數(shù)為。證明 正整數(shù)n分成k個分部量的一個有序分拆

3、：，等價于方程：。的正整數(shù)解，由2.3節(jié)定理2.3.4的證明知，正整數(shù)n的有序k分拆的個數(shù)為。由定理2.3.4和定理2.6.1，正整數(shù)n的有序k分拆數(shù)等于多重集合的至少出現(xiàn)一次的n組合數(shù)，均為。定理2.6.2 （1）正整數(shù)n的有序k分拆，要求第i個分部量大于等于，其個數(shù)為：（2）正整數(shù)2n分拆成k個分部，各分部量都是正偶數(shù)的有序分拆個數(shù)為。（3）正整數(shù)n分成k個分部，若n與k同為奇數(shù)或同為偶數(shù)，則n的各分部量都是奇數(shù)的有序分拆數(shù)為：證明 （1）設(shè)：（2.6.2）是n滿足條件：（2.6.3）的一個有序k分拆。令：且滿足方程：（2.6.4）即是方程（2.6.4）的一組非負整數(shù)解。反之，若給定方程（

4、2.6.4）的一組非負整數(shù)解，令，則構(gòu)成n的一個有序k分拆（2.6.2），且滿足條件（2.6.3）。所以，n的滿足條件（2.6.3）的有序k分拆與方程（2.6.4）的非負整數(shù)解之間構(gòu)成一一對應(yīng)。由定理2.3.3的證明知，其個數(shù)為：（2）設(shè)2n的一個有序k分拆：滿足條件：為偶數(shù)（2.6.5），令，則有：即是n的一個有序k分拆。反之，設(shè)是n的一個有序k分拆，令，則是2n的一個滿足條件（2.6.5）的有序k分拆。所以，2n滿足條件（2.6.5）的有序k分拆數(shù)等于n的有序k分拆數(shù)，為。（3）n的各分部量為奇數(shù)的分拆：與的各分部量為偶數(shù)的分拆：顯然構(gòu)成一一對應(yīng)。由（2）知，n的各分部量為奇數(shù)的分拆數(shù)為：

5、定理2.6.2給出了幾種不同限定條件下的有序分拆數(shù)。2.6.2無序分拆我們用來表示n的k分拆的個數(shù)，用表示n的所有分拆的個數(shù)，則顯然有（1）；（2）n的k分拆中，各分部量的次序無關(guān)緊要，一般按遞降順序排列。若：則：如果在n的k分拆中有個分部量為，那么可以把該分拆記為：有時也記為：例如，的所有5分拆為：表2.6.1列出了當時n的所有k分拆。定理2.6.3 n的k分拆數(shù)滿足遞推關(guān)系：（2.6.6）（2.6.7）證明 由的定義易知等式（2.6.7）成立，下面證明遞推關(guān)系（2.6.6）為此，我們考慮n分成至多k個分部的分拆，這樣的分拆總數(shù)為n的每個分成至多k個分部的分拆可表示為：這個和式中包含k項，并

6、且：我們將n的這個m分拆映射到的k分拆如下：該和式中包含k項，并且：設(shè)上面確定的映射為，因為不同的n分為至多k個分部的分拆對應(yīng)著不同的k分拆，所以是單射。又因為每個的k分拆：在作用下的原像是每個減去1，再保留不為零的那些項而得到的n的一個分部數(shù)至多為k的分拆，所以是滿射。因此，是一一映射，于是有：定理2.6.3提供了對逐行遞推的計算方法，見表2.6.2，例如：例1 正整數(shù)n的2分折數(shù)為：其中，表示小于等于的最大整數(shù)。證明 設(shè)n的2分拆為：因，所以恰能取1，2，中的任一個，故：2.6.3 分拆的Ferrers圖研究分拆數(shù)性質(zhì)的一種簡單有效的組合手段就是Ferrers圖，設(shè)n的一個k分拆為（2.6

7、.8）我們在一條水平直線上畫個點，在其下面一條直線上畫個點，且使這兩條直線上的第一個點在同一條豎線上，其他點依次與上一行的點對齊；依此類推，最后在第k條直線上畫個點，第一個點與前面各行的第一個點均在同一條豎線上，其他點依次與上面各行的點對齊，這樣得到的點陣圖叫做n的k分拆（2.6.8）的Ferrers圖例如，15的4分拆：（2.6.9）的Ferrers圖如圖2.6.1所示。反過來，對于n的一個Ferrers圖，又可按上述規(guī)則對應(yīng)于n的唯一的一個分拆。所以，n的分拆同它的Ferrers圖之間是一一對應(yīng)的。把一個Ferrers圖的各行改成列，但其相對位置不變，這樣又得到一個Ferrers圖，叫做原

8、Ferrers圖的共軛圖。例如，圖2.6.1對應(yīng)的共軛圖是圖2.6.2。共軛Ferrers圖所對應(yīng)的分拆叫做原分拆的共軛分拆。例如，圖2.6.2對應(yīng)的分拆（2.6.10）是分拆（2.6.9）的共軛分拆。若n的一個分拆與其共軛分拆相同，則該分拆稱為n的自共軛分拆。從分拆的Ferrers圖可以證明以下一些定理：定理2.6.4 n的k分拆的個數(shù)等于n的最大分部量為k的分拆數(shù)。證明 上面定義的分拆的共軛運算是一個映射，它將n的最大分部量為k的分拆映射到n的k分拆。例如，分拆（2.6.9）是15的最大分部量為5的分拆，其共軛分拆（2.6.10）是15的一個5分拆。并且這個映射顯然是一一的，所以兩者相等。

9、定理2.6.5 n的自共軛分拆的個數(shù)等于n的各分部量都是奇數(shù)且兩兩不等的分拆的個數(shù)。證明 為了證明這個性質(zhì)，我們將借助于Ferrers圖建立一個n的各分部量為奇數(shù)且兩兩不等的分拆到n的自共軛分拆之間的一一對應(yīng)。設(shè)n的一個分部量為奇數(shù)且兩兩不等的分拆為：（2.6.11）其中：由n的分拆（2.6.11），我們構(gòu)造n的一個自共軛分拆的Ferrers圖。在第1行與第1列都畫個點，共有個點；畫完第1行和第1行后，在第2行與第2列再各畫個點，共個點，此時，第2行與第2列中加上第1行與第1列已畫的點，都已有個點；在第k行與第k行再畫個點，共個點。因為，所以如此畫的n個點的點陣圖的每一行都不比下一行的點數(shù)少，

10、因而是n的一個分拆的Ferrers圖。且由上面的構(gòu)造法知，該Ferrers圖是對稱的，所以其對應(yīng)的分拆是自共軛的。例如，用上述方法由分拆：構(gòu)造的Ferrers圖如圖2.6.3所示，對應(yīng)的自共軛分拆為顯然，上面建立的n個分部量為奇數(shù)且兩兩不等的分拆與n的自共軛分拆之間的對應(yīng)關(guān)系是一一的，所以定理的結(jié)論成立。定理2.6.6 n的分部量兩兩不等的分拆的個數(shù)等于n的各分部量都是奇數(shù)的分拆的個數(shù)。證明 證明的方法還是建立定理中提及的兩類不同的分拆之間的一一對應(yīng)。在一個n的各分部量為奇數(shù)的分拆中，假設(shè)數(shù)出現(xiàn)p次，我們將p寫成2的冪次和的形式：則這種表示法是唯一的。我們將n的這個分拆的Ferrers圖中這個

11、小點按下列方法重排：各行的小點數(shù)分別為，如此將原來那個分拆的Ferrers圖中所有的點重排了一次。然后再將各行按小點數(shù)遞減的順序排列，就得到n的另一個分拆的Ferrers圖。例如，分拆的Ferrers圖如圖2.6.4所示。我們將重復(fù)數(shù)2，3，5分別寫成2的冪次和的形式：則由上述方法構(gòu)造出的新Fereers圖如圖2.6.5所示，它所對應(yīng)的24的分拆為在新的Ferrers圖中，各行的點數(shù)為的形式。在各行點數(shù)的表達式中，參數(shù)k和i中必有一個不同，所以各行的點數(shù)互不相同，因而它所對應(yīng)的分拆的各分部量不同。如上建立了兩類分拆之間的一一對應(yīng)。事實上，任一自然數(shù)表示成2的冪次和的形式是唯一的，從而上面建立的映射是單射。另外，上面構(gòu)造成新的Ferrers圖的方法顯