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

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

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

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

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

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

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

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

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

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

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

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