自然数の分割

数学の各分野、特に数論および組合せ論伏見康治「確率論及統計論」第I章　数学的補助手段 1節 組合わせの理論 p.5 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204
において、正の整数 n の分割（ぶんかつ、）あるいは整分割 (integer partition) とは、与えられた正整数 n を正整数の和として表す方法をいう。ただし、和の因子（summand; 被加数）の順番のみが異なる分割は同じ分割とみなされる（順序をも考慮する場合は、順序つき分割または、分割ではなく合成あるいは結合 (composition) と呼ばれる概念となる）。

例えば 4 の異なる分割は次の五通りである。
 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

このとき、順序を考慮した合成 1 + 3 は分割としては 3 + 1 と同じであり、同様に合成としては異なる 1 + 2 + 1 および 1 + 1 + 2 は分割としては 2 + 1 + 1 と同じである。

分割の各因子は部分または成分 (part) などとも呼ばれる。また、各正整数 n に対して n の分割の総数を与える函数を p(n) であらわし、n の分割数 (partition function) と呼ぶ。これによれば上記は p(4) = 5 と表せる。なお、p が n の分割であることを p  n で表すことがある。

自然数の分割を図示する方法としてヤング図形やフェラーズ図形がある。これらは数学や物理学のいくつかの分野で用いられるが、特に対称多項式や対称群の研究あるいは一般の群の表現論などが含まれる。

 定義 
自然数に対して，数列が次の条件
 各項は自然数で有限個を除いてである。

 非増加列である。（順序は問わない）
 その総和がである。

を満たすとき，数列はを分割すると言う。
一般に0である項は省略され，また同じ数の項はまとめて指数表記される場合がある
（例えばという値を取る項が個あるならと表す）。

 例 

整数 4 の分割は
 4
 3 + 1
 2 + 2
 2 + 1 + 1
 1 + 1 + 1 + 1
で全てである。また整数 8 の分割を列挙すれば
 8
 7 + 1
 6 + 2
 6 + 1 + 1
 5 + 3
 5 + 2 + 1
 5 + 1 + 1 + 1
 4 + 4
 4 + 3 + 1
 4 + 2 + 2
 4 + 2 + 1 + 1
 4 + 1 + 1 + 1 + 1
 3 + 3 + 2
 3 + 3 + 1 + 1
 3 + 2 + 2 + 1
 3 + 2 + 1 + 1 + 1
 3 + 1 + 1 + 1 + 1 + 1
 2 + 2 + 2 + 2
 2 + 2 + 2 + 1 + 1
 2 + 2 + 1 + 1 + 1 + 1
 2 + 1 + 1 + 1 + 1 + 1 + 1
 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

となる。本項ではしないが、"+" 記号を省略するために、しばしば分割を成分の列として扱うことがある。例えば、整数 8 の分割 4 + 3 + 1 を三つ組 (4, 3, 1) で表すというようなことである。このような記法を用いると、整数をよりコンパクトな形に書くことができる。例えば、2 + 2 + 1 + 1 + 1 + 1 と書く代わりに、冪記法も利用して (22, 14) と書き表せる。

 制限つきの分割 
整数 8 の分割は22個あるが、そのうちの6個は「奇数のみを成分とする」ものになっている。
 7 + 1
 5 + 3
 5 + 1 + 1 + 1
 3 + 3 + 1 + 1
 3 + 1 + 1 + 1 + 1 + 1
 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

また、8の分割のなかで、「成分が全て異なる」ものは次の6個。
 8
 7 + 1
 6 + 2
 5 + 3
 5 + 2 + 1
 4 + 3 + 1

実は、任意の自然数について、その奇数のみを成分とする分割の数と成分が全て異なる分割の数とは一致する。このことは1748年にオイラーが示したAndrews, George E. Number Theory. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.（オイラーの分割恒等式）。

制限された分割についての同様の結果を得るのに、フェラーズ図形などの視覚的な道具を用いるのはひとつの助けとなるだろう。

 フェラーズ図形 
ノーマン・マクリード・フェラーズに因んで名づけられた、以下のように分割を図示する図形を考えよう。整数 14 の分割 6 + 4 + 3 + 1 は、以下の図形によって表される。

 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|* 6 + 4 + 3 + 1

14 個の丸が4列にそれぞれの成分の大きさにしたがって並べられている。整数 4 の分割、全5種類は次のようになる。
 16px|*16px|*16px|*16px|*  16px|*16px|*16px|*16px|*  16px|*16px|*16px|*16px|*  16px|*16px|*16px|*16px|*  16px|*16px|*16px|*16px|* 4  = 3 + 1  = 2 + 2  = 2 + 1 + 1  = 1 + 1 + 1 + 1

さて、分割 6 + 4 + 3 + 1 を表す図形を、その主対角線に沿ってひっくりかえすと、整数 14 のまた別の分割が得られる。
 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|* ↔ 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|* 6 + 4 + 3 + 1 = 4 + 3 + 3 + 2 + 1 + 1

つまり、行と列とを入れ替えることにより、整数 14 の分割 4 + 3 + 3 + 2 + 1 + 1 が得られたわけである。このような分割は、互いに他の共軛 (conjugate) あるいは双対 (dual) であるという。整数 4 の分割の場合、二つの分割 4 および 1 + 1 + 1 + 1 が互いに共軛で、分割 3 + 1 および 2 + 1 + 1 も同様に共軛である。最も注目すべきは分割 2 + 2 で、これは自分自身が自身の共軛となっている。このような分割は自己共軛 (self-conjugate) あるいは対称 (symmetry) であるという。

 主張 自己共軛な分割の総数は相異なる奇数への分割の総数に等しい。
 証明（概略） 証明の骨子は、全ての奇数成分をその真ん中で「折り畳む」(fold) と自己共軛な分割が得られるということである。
{| align="center"
|-
| style="vertical-align:bottom;"| 16px|*16px|*16px|*16px|*16px|*
| style="vertical-align:middle;"| ↔
| style="vertical-align:bottom;"| 16px|*16px|*16px|*16px|*16px|*
|}
 以下の例にあるような方法で、相異なる奇数への分割全体のなす集合と自己共軛な分割全体のなす集合との間に全単射を得ることができる。
{| align="center"
|-
| valign="top" | 16px|o16px|*16px|x16px|o16px|*16px|x16px|o16px|*16px|x16px|o16px|*16px|o16px|*16px|o16px|*16px|o16px|*16px|o16px|o
| style="vertical-align:middle;"| ↔
| valign="top" | 16px|o16px|o16px|o16px|o16px|o16px|o16px|*16px|*16px|*16px|*16px|o16px|*16px|x16px|x16px|o16px|*16px|x16px|o16px|*
|- style="vertical-align:top; text-align:center;"
| 9 + 7 + 3
| =
| 5 + 5 + 4 + 3 + 2
|- style="vertical-align:top; text-align:center;"
| 異なる奇数
|
| 自己共軛
|}

同様の方法を用いれば、例えば次のような等式を得ることができる。
 整数 n を分割したときの成分の数が k 個以下になるような分割の総数は、成分が k 以下の整数となるような n の分割の総数に等しい。
 整数 n を分割したときの成分の数が k 個以下になるような分割の総数は、成分がちょうど k 個になるような n + k の分割の総数に等しい。

 ヤング図形 

整数の分割の別の視覚的な表現に、イギリス人数学者アルフレッド・ヤングに因んで名づけられた、ヤング図形がある。フェラーズ図形では丸で表していたものを、ヤング図形では箱型を使う。つまり、分割 5 + 4 + 1 に対するヤング図形は
である。同じ分割のフェラーズ図形は
 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*

これは一見取り立てて分けて述べる価値のあるようには思われないつまらない違いにも見えるが、実際には対称函数や群の表現論の研究にとってヤング図形はきわめて有用な存在となる。特に、ヤング図形の箱の中に様々な決まりのもとで数値（あるいはもっと複雑な対象）を書き込むことで、ヤング盤と呼ばれる対象を導入することができて、それが組合せ論や群の表現論で効果を発揮するのである。

 脚注 

 参考文献 

 - 注記：原著第2版の翻訳。
 - 注記：第5章のRademacherの公式に対する教育的な導入を参照。
 - 自然数の分割に関する話題の初等的な導入。フェラーズ図形に関する議論も含まれる。
 - 注釈：解説とほぼ完全な文献表を含む。ただし、執筆者（およびAbramowitz）は  による Ak(n) の Selberg の公式を挙げていない。
 - 注釈：第1.1章を参照。

 - 注釈：Selbergの公式を与えている。古い形式のSelbergの有限フーリエ展開。




 関連項目 
 (Dominance order)
 写像12相(Twelvefold way)
 集合の分割
  (Multiplicative partition)
 : ヤング図形の左上隅を含む最大の正方形
 多重集合
 (Polite number)/台形数 (trapezoidal numbers)/階段数 (staircase numbers): 連続する整数への分割から定まる
  (Newton's identities): ある種の対称函数の間で成り立つ変換公式
  : 平面植木算
  - 2007年に Complicite で上演された作品。分割関数に関するラマヌジャンの論文に言及。
 ヤング束 (Young's lattice) :「ヤング束(そく)」と読む

 外部リンク 

 Pieces of Number from Science News Online
 Lectures on Integer Partitions by Herbert S. Wilf
 Fast Algorithms For Generating Integer Partitions
 Generating All Partitions: A Comparison Of Two Encodings

Category:初等整数論
Category:組合せ論
Category:数学に関する記事