自然数の分割

出典: フリー百科事典『ウィキペディア（Wikipedia）』

これはこのページの過去の版です。Æskja (会話 | 投稿記録) による 2012年1月15日 (日) 00:37 （個人設定で未設定ならUTC）時点の版 (→‎参考文献: リンク修正。)であり、現在の版とは大きく異なる場合があります。

1 から 8 までの自然数の分割に対応するヤング図形。これらを正方形の枠の主対角線で反転させたものは、もとの分割の共軛になっている。

数学の各分野、特に数論および組合せ論において、正の整数 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 で表すことがある。

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

例

整数 4 の分割は

  1. 4
  2. 3 + 1
  3. 2 + 2
  4. 2 + 1 + 1
  5. 1 + 1 + 1 + 1

で全てである。また整数 8 の分割を列挙すれば

  1. 8
  2. 7 + 1
  3. 6 + 2
  4. 6 + 1 + 1
  5. 5 + 3
  6. 5 + 2 + 1
  7. 5 + 1 + 1 + 1
  8. 4 + 4
  9. 4 + 3 + 1
  10. 4 + 2 + 2
  11. 4 + 2 + 1 + 1
  12. 4 + 1 + 1 + 1 + 1
  13. 3 + 3 + 2
  14. 3 + 3 + 1 + 1
  15. 3 + 2 + 2 + 1
  16. 3 + 2 + 1 + 1 + 1
  17. 3 + 1 + 1 + 1 + 1 + 1
  18. 2 + 2 + 2 + 2
  19. 2 + 2 + 2 + 1 + 1
  20. 2 + 2 + 1 + 1 + 1 + 1
  21. 2 + 1 + 1 + 1 + 1 + 1 + 1
  22. 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年にオイラーが示した[1]（オイラーの恒等式）。

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

フェラーズ図形

ノーマン・マクリード・フェラーズに因んで名づけられた、以下のように分割を図示する図形を考えよう。整数 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) と自己共軛な分割が得られるということである。
*
*
*
*
* 		↔ ***
*
*
以下の例にあるような方法で、相異なる奇数への分割全体のなす集合と自己共軛な分割全体のなす集合との間に全単射を得ることができる。
o*x
o*x
o*x
o*
o*
o*
o*
o
o 		↔ ooooo
o****
o*xx
o*x
o*
9 + 7 + 3 = 5 + 5 + 4 + 3 + 2
異なる奇数 自己共軛

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

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

ヤング図形

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

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

5+4+1
5+4+1

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

*****
****
*

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

関連項目

注意

  1. ^ Andrews, George E. Number Theory. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.

参考文献

  • George E. Andrews, The Theory of Partitions (1976), Cambridge University Press. ISBN 0-521-63766-X .
  • Tom M. Apostol, Modular functions and Dirichlet Series in Number Theory (1990), Springer-Verlag, New York. ISBN 0-387-97127-0 (See chapter 5 for a modern pedagogical intro to Rademacher's formula).
  • Sautoy, Marcus Du. The Music of the Primes. New York: Perennial-HarperCollins, 2003.
  • Gupta, Gwyther, Miller, Roy. Soc. Math. Tables, vol 4, Tables of partitions, (1962) (Has text, nearly complete bibliography, but they (and Abramowitz) missed the Selberg formula for Ak(n), which is in Whiteman.)
  • Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, 1979, ISBN 0-19-853530-9 (See section I.1)
  • Richard P. Stanley, Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press, 1999 ISBN 0-521-56069-1
  • A. L. Whiteman, A sum connected with the series for the partition function, Pacific Journal of Math. 6:1 (1956) 159–176. (Provides the Selberg formula. The older form is the finite Fourier expansion of Selberg.)
  • Hans Rademacher, Collected Papers of Hans Rademacher, (1974) MIT Press; v II, p 100–107, 108–122, 460–475.
  • Miklós Bóna (2002). A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing. ISBN 981-02-4900-4  (qn elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs)
  • George E. Andrews, Kimmo Eriksson (2004). Integer Partitions. Cambridge University Press. ISBN 0-521-60090-1 
  • 'A Disappearing Number', devised piece by Complicite, mention Ramanujan's work on the Partition Function, 2007

外部リンク

「https://ja.wikipedia.org/w/index.php?title=自然数の分割&oldid=40805672」から取得