自然数の分割

数学の各分野、特に数論および組合せ論^[1] において、正の整数 n の分割（ぶんかつ、英: partition）あるいは整分割 (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 で表すことがある。

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

定義

自然数 $n$ に対して，数列{λ_i}が次の条件

各項は自然数で有限個を除いて $0$ である。

λ i \in ℕ 0, \exists M > 0 s.t. \forall m > M [m > #{λ i | λ i \neq 0}]

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

\sum i = n

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

例

整数 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 と書く代わりに、冪記法も利用して (2², 1⁴) と書き表せる。

制限つきの分割

整数 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年にオイラーが示した^[3]（オイラーの分割恒等式）。

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

フェラーズ図形

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

6 + 4 + 3 + 1

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


4	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

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

	↔
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) と自己共軛な分割が得られるということである。

↔

以下の例にあるような方法で、相異なる奇数への分割全体のなす集合と自己共軛な分割全体のなす集合との間に全単射を得ることができる。

	↔
9 + 7 + 3	=	5 + 5 + 4 + 3 + 2
異なる奇数		自己共軛

同様の方法を用いれば、例えば次のような等式を得ることができる。

整数 n を分割したときの成分の数が k 個以下になるような分割の総数は、成分が k 以下の整数となるような n の分割の総数に等しい。
整数 n を分割したときの成分の数が k 個以下になるような分割の総数は、成分がちょうど k 個になるような n + k の分割の総数に等しい。

ヤング図形

→詳細は「ヤング図形」を参照

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

5+4+1

である。同じ分割のフェラーズ図形は

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

脚注

[脚注の使い方]

^ 伏見康治「確率論及統計論」第I章　数学的補助手段 1節組合わせの理論 p.5 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204
^ Nakamura 2012, p. 13.
^ Andrews, George E. Number Theory. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.

参考文献

Andrews, George E. (1976), The Theory of Partitions, Cambridge University Press, ISBN 0-521-63766-X
Andrews, George E.; Eriksson, Kimmo (2004), Integer Partitions (2nd ed.), Cambridge University Press, ISBN 0-521-60090-1
- ジョージ・アンドリュース、キムモ・エリクソン『整数の分割』佐藤文広訳、数学書房(出版) 白揚社(発売)、2006年5月。ISBN 978-4-8269-3103-8。 - 注記：原著第2版の翻訳。
Apostol, Tom M. (1990), Modular functions and Dirichlet Series in Number Theory, Graduate Texts in Mathematics (Book 41) (2nd ed.), New York: Springer-Verlag, ISBN 978-0-387-97127-8 - 注記：第5章のRademacherの公式に対する教育的な導入を参照。
Bóna, Miklós (2002), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing, ISBN 981-02-4900-4 - 自然数の分割に関する話題の初等的な導入。フェラーズ図形に関する議論も含まれる。
Gupta; Gwyther; Miller (1962), Roy. Soc. Math. Tables, vol 4, Tables of partitions - 注釈：解説とほぼ完全な文献表を含む。ただし、執筆者（およびAbramowitz）は Whiteman 1956 による A_k(n) の Selberg の公式を挙げていない。
Macdonald, Ian G. (1979), Symmetric functions and Hall polynomials, Oxford University Press, ISBN 0-19-853530-9 - 注釈：第1.1章を参照。
Rademacher, Hans (1974), Collected Papers of Hans Rademacher, v II, MIT Press, pp. 100–107, 108–122, 460–475
Stanley, Richard P. (1999), Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press, ISBN 0-521-56069-1, http://www-math.mit.edu/~rstan/ec/
Sautoy, Marcus du (2012-08-14), The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics (Reprint ed.), New York: Harper Perennial, ISBN 978-0-06-206401-1
- マーカス・デュ・ソートイ『素数の音楽』冨永星訳、新潮社〈新潮クレスト・ブックス〉、2005年8月。ISBN 4-10-590049-8。
- マーカス・デュ・ソートイ『素数の音楽』冨永星訳、新潮社〈新潮文庫シ-38-1〉、2013年10月。ISBN 978-4-10-218421-9。
Whiteman, A. L. (1956), “A sum connected with the series for the partition function”, Pacific Journal of Mathematics 6 (1): 159–176 - 注釈：Selbergの公式を与えている。古い形式のSelbergの有限フーリエ展開。

Flavius Turcu; Cosmin Bonchiş; Mohamed Najim (2018). “Vector partitions, multi-dimensional Faà di Bruno formulae and generating algorithms” (英語) (PDF). Discrete Applied Mathematics (Elsevier). doi:10.1016/j.dam.2018.09.012 2019年12月11日閲覧。.
Shigeki Nakamura (2012年5月5日). “Nの分割と対称式の話”. 2019年12月11日閲覧。

外部リンク

Weisstein, Eric W. "Partition". mathworld.wolfram.com (英語).
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

[1] 伏見康治「確率論及統計論」第I章　数学的補助手段 1節組合わせの理論 p.5 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204

[FOOTNOTENakamura201213-2] Nakamura 2012, p. 13.

[3] Andrews, George E. Number Theory. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.

[1]

[2]

[3]