關於分拆數的一個結論

05-05

分拆是指將一個正整數表示成不大於其自身的一個或幾個正整數的無序和，分拆數（partition number）則指不同的分拆方式的數目。

關於分拆數，有一個有趣的結論，即對任意正整數，其奇分拆數目（每個部分均為奇數）等於其互異分拆（每個部分互不相同）數目。

為證明此命題，需要使用到生成函數方法。

我們將對於一個數n的分拆視作由無數個部分組成，每個部分可以取0到n的任意整數。我們不妨用 $sum_{i =0}^{infty }{x^{ai} }$ 來表示分拆中大小為a的分拆，i不同的取值則表示有幾個這樣的分拆，則我們可有形式 $prod_{a=1}^{infty } (sum_{i=0}^{infty }{x^{ai} })$ 可對任意分拆進行表示，對於1大小為n的分拆，上式 $x^{n}$ 一項的係數即為其分拆數。例如對將5分解為2,3的分拆，則對應多項式 $sum_{i=0}^{infty }{x^{2i} }$ 中取i=1項， $sum_{i=0}^{infty }{x^{3i} }$ 取i=1項所得的一個 $x^{5}$ 。這種方法叫做生成函數。值得注意， $sum_{i =0}^{infty }{x^{ai} }$ 又可以寫成形式級數 $frac{1}{1-x^{a} }$ 。

對於奇分拆，其各個部分只能取奇數，即所有a必須為奇數，因此其生成函數表示為 $prod_{i=1}^{infty } frac{1}{1-x^{2i-1}}$ 。

對於互異分拆，我們直接考慮其生成函數，由於大小為i的分拆部分只能選擇有0個或1個，因此，其生成函數可以寫作 $prod_{1}^{infty} left( 1+x^{i} ight)$ 。

顯然，有 $prod_{i=1}^{infty } frac{1}{1-x^{2i-1}}$ = $prod_{i=1}^{infty } left({1-x^{2i}} ight)$ / $prod_{i=1}^{infty } left({1-x^{i}} ight)$ = $prod_{1}^{infty} left( 1+x^{i} ight)$ 。

因此，證得兩種分拆生成函數相同。

因此，一個數的奇分拆數等於其互異分拆數。