上一页

ⓘ 整數分拆




                                     

ⓘ 整數分拆

一個正整數可以寫成一些正整數的和。在數論上,跟這些和式有關的問題稱為 整數拆分 、 整數剖分 、 整數分割 、 分割數 或 切割數 。其中最常見的問題就是給定正整數 n {\displaystyle n} ,求不同數組 {\displaystyle } 的數目,符合下面的條件:

  • a 1 + a 2 +. + a k = n {\displaystyle a_{1}+a_{2}+.+a_{k}=n} ( k {\displaystyle k} 的大小不定)
  • 其他附加條件(例如限定「k是偶數」,或「 a i {\displaystyle a_{i}} 不是1就是2」等)
  • a 1 ≥ a 2 ≥. ≥ a k > 0 {\displaystyle a_{1}\geq a_{2}\geq.\geq a_{k}> 0}

分割函數 pn是求符合以上第一、二個條件的數組數目。

                                     

1. 拆分數量數列

4可以用5種方法寫成和式:4, 3+1, 2+2, 2+1+1, 1+1+1+1。因此 p 4 = 5 {\displaystyle p4=5} 。

定義 p 0 = 1 {\displaystyle p0=1} ,若n為負數則 p n = 0 {\displaystyle pn=0} 。

此函數應用於對稱多項式及對稱群的表示理論等。

分割函數pn,n從0開始:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77.OEIS:A000041
                                     

2. Ferrers圖示與恆等式

每種分割方法都可用 Ferrers圖示 表示。

Ferrers圖示是將第1行放 a 1 {\displaystyle a_{1}} 個方格,第2行放 a 2 {\displaystyle a_{2}} 個方格……第 k {\displaystyle k} 行放 a k {\displaystyle a_{k}} 個方格,來表示整數分割的其中一個方法。

借助Ferrers圖示,可以推導出許多恆等式:

  • 給定正整數k和n,n表達成不多於k個正整數之和的方法數目,等於將n分割成任意個不大於k的正整數之和的方法數目。

證明:將表示前者其中一個數組的Ferrers圖示沿對角線反射,便得到後者的一個數組。即兩者一一對應,因此其數目相同。

例如 k=3,n=6:

此外,

6 = 1 + 5 = 1 + 1 + 1 + 1 + 2 {\displaystyle 6=1+5=1+1+1+1+2} 6 = 2 + 4 = 2 + 2 + 1 + 1 {\displaystyle 6=2+4=2+2+1+1} 6 = 3 + 3 = 2 + 2 + 2 {\displaystyle 6=3+3=2+2+2} 6 = 6 = 1 + 1 + 1 + 1 + 1 + 1 {\displaystyle 6=6=1+1+1+1+1+1}
  • 上述恆等式的值亦等於將 n + k {\displaystyle n+k} 表達成剛好 k {\displaystyle k} 個正整數之和的方法的數目。
  • 給定正整數 n {\displaystyle n} 。將 n {\displaystyle n} 表達成兩兩相異正整數之和的方法的數目,等於將 n {\displaystyle n} 表達成奇數之和的方法的數目。

例如 n = 8 {\displaystyle n=8} :

  • 3 + 3 + 1 + 1
  • 5 + 1 + 1 + 1
  • 3 + 1 + 1 + 1 + 1 + 1
  • 7 + 1
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  • 5 + 3
  • 6 + 2
  • 7 + 1
  • 4 + 3 + 1
  • 8
  • 5 + 2 + 1
  • 5 + 3
  • 將 n {\displaystyle n} 表達成 p {\displaystyle p} 個1和 q {\displaystyle q} 個2之和,這些方法的數目是第 n {\displaystyle n} 個斐波那契數。
  • 將 n {\displaystyle n} 表達成多於1的正整數之和的方法數目是pn - pn -1。
                                     

3. 生成函數

p n {\displaystyle pn} 的生成函數是

∑ n = 0 ∞ p n x n = ∏ k = 1 ∞ 1 − x k {\displaystyle \sum _{n=0}^{\infty }pnx^{n}=\prod _{k=1}^{\infty }\left{\frac {1}{1-x^{k}}}\right}

當|x| a 1 > a 2. > a k {\displaystyle a_{1}> a_{2}.> a_{k}}

及分拆的每个数都不相等。

生成函數是

∑ n = 0 ∞ p n x n = ∏ k = 1 ∞ 1 + x k {\displaystyle \sum _{n=0}^{\infty }pnx^{n}=\prod _{k=1}^{\infty }\left1+x^{k}\right}
                                     

3.1. 生成函數 奇分拆

考虑满足下面条件分拆

  • a 1 ≥ a 2. ≥ a k {\displaystyle a_{1}\geq a_{2}.\geq a_{k}}
  • a 1 + a 2 +. + a k = n {\displaystyle a_{1}+a_{2}+.+a_{k}=n} ( k {\displaystyle k} 的大小不定)
  • 要求 a i = 1, 2., k {\displaystyle a_{i}i=1.2.,k} 为奇数

生成函數是

∑ n = 0 ∞ p n x n = ∏ k = 1 ∞ 1 − x 2 k − 1 {\displaystyle \sum _{n=0}^{\infty }pnx^{n}=\prod _{k=1}^{\infty }\left{\frac {1}{1-x^{2k-1}}}\right}.
                                     

3.2. 生成函數 引理

差分拆的个数与奇分拆的个数是一样多的。

可以通过杨表证明。

                                     

4. 其他常見的問題

不少數學家亦有研究按以下方式分拆的方法數目:

  • 將模p同餘r正整數寫成的正整數之和
  • 將正整數寫成模p同餘r的正整數之和