この項目「自然数の分割」は途中まで翻訳されたものです。(原文:en:Partition (number theory)
14:16, 19 August 2011)数学の各分野、特に数論および組合せ論[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}が次の条件 を満たすとき,数列{λi}はnを分割すると言う[2]。一般に0である項は省略され,また同じ数の項はまとめて指数表記される場合がある(例えばkという値を取る項がl個あるならklと表す)。 整数 4 の分割は で全てである。また整数 8 の分割を列挙すれば となる。本項ではしないが、"+" 記号を省略するために、しばしば分割を成分の列として扱うことがある。例えば、整数 8 の分割 4 + 3 + 1 を三つ組 (4, 3, 1) で表すというようなことである。このような記法を用いると、整数をよりコンパクトな形に書くことができる。例えば、2 + 2 + 1 + 1 + 1 + 1 と書く代わりに、冪記法も利用して (22, 14) と書き表せる。 整数 8 の分割は22個あるが、そのうちの6個は「奇数のみを成分とする」ものになっている。 また、8の分割のなかで、「成分が全て異なる」ものは次の6個。 実は、任意の自然数について、その奇数のみを成分とする分割の数と成分が全て異なる分割の数とは一致する。このことは1748年にオイラーが示した[3](オイラーの分割恒等式)。 制限された分割についての同様の結果を得るのに、フェラーズ図形などの視覚的な道具を用いるのはひとつの助けとなるだろう。 ノーマン・マクリード・フェラーズ 14 個の丸が4列にそれぞれの成分の大きさにしたがって並べられている。整数 4 の分割、全5種類は次のようになる。 さて、分割 6 + 4 + 3 + 1 を表す図形を、その主対角線に沿ってひっくりかえすと、整数 14 のまた別の分割が得られる。 つまり、行と列とを入れ替えることにより、整数 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) であるという。
定義
各項は自然数で有限個を除いて0である。
λi ∈ ?0, ∃M > 0 s.t. ∀m > M [m > #{λi | λi ≠ 0}]
非増加列である。(順序は問わない)
その総和がnである。
∑i = n
例
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
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
制限つきの分割
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
7 + 1
6 + 2
5 + 3
5 + 2 + 1
4 + 3 + 1
フェラーズ図形
4=3 + 1=2 + 2=2 + 1 + 1=1 + 1 + 1 + 1
?
6 + 4 + 3 + 1=4 + 3 + 3 + 2 + 1 + 1
主張
自己共軛な分割の総数は相異なる奇数への分割の総数に等しい。
証明(概略)
証明の骨子は、全ての奇数成分をその真ん中で「折り畳む」(fold) と自己共軛な分割が得られるということである。
Size:29 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef