|
|
| 1行目: |
1行目: |
| − | {{翻訳中途|date=2011年8月|[[:en:Partition (number theory)]] 14:16, 19 August 2011}} | + | {{テンプレート:20180815sk}} |
| − | <!--{{expert-subject|mathematics|date=February 2011}}-->
| |
| − | [[File:Ferrer partitioning diagrams.svg|thumb|right|300px|1 から 8 までの自然数の分割に対応する[[ヤング図形]]。これらを正方形の枠の主対角線で反転させたものは、もとの分割の共軛になっている。]]
| |
| − | | |
| − | [[数学]]の各分野、特に[[数論]]および[[組合せ論]]<ref>[[伏見康治]]「[[確率論及統計論]]」第I章 数学的補助手段 1節 組合わせの理論 p.5 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204</ref>
| |
| − | において、正の[[整数]] ''n'' の'''分割'''（ぶんかつ、{{lang-en-short|''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'' {{Unicode|⊢}} ''n'' で表すことがある。
| |
| − | | |
| − | 自然数の分割を図示する方法として[[ヤング図形]]や[[#フェラーズ図形|フェラーズ図形]]がある。これらは[[数学]]や[[物理学]]のいくつかの分野で用いられるが、特に[[対称多項式]]や[[対称群]]の研究あるいは一般の[[群の表現|群の表現論]]などが含まれる。
| |
| − | | |
| − | == 例 ==
| |
| − | | |
| − | 整数 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<sup>2</sup>, 1<sup>4</sup>) と書き表せる。
| |
| − | | |
| − | == 制限つきの分割 ==
| |
| − | 整数 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年に[[レオンハルト・オイラー|オイラー]]が示した<ref>Andrews, George E. ''Number Theory''. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.</ref>（[[オイラーの分割恒等式]]）。
| |
| − | | |
| − | 制限された分割についての同様の結果を得るのに、フェラーズ図形などの視覚的な道具を用いるのはひとつの助けとなるだろう。
| |
| − | | |
| − | == フェラーズ図形 ==
| |
| − | [[ノーマン・マクリード・フェラーズ]]に因んで名づけられた、以下のように分割を図示する図形を考えよう。整数 14 の分割 6 + 4 + 3 + 1 は、以下の図形によって表される。
| |
| − | | |
| − | {| align="center"
| |
| − | |- style="vertical-align:top; text-align:left;"
| |
| − | | [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| |
| − | |- style="vertical-align:top; text-align:center;"
| |
| − | | 6 + 4 + 3 + 1
| |
| − | |}
| |
| − | | |
| − | 14 個の丸が4列にそれぞれの成分の大きさにしたがって並べられている。整数 4 の分割、全5種類は次のようになる。
| |
| − | {| align="center"
| |
| − | |- style="vertical-align:top; text-align:left;"
| |
| − | | [[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]] ||
| |
| − | | [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]] ||
| |
| − | | [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]] ||
| |
| − | | [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]] ||
| |
| − | | [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]
| |
| − | |- style="vertical-align:top; text-align:center;"
| |
| − | | 4 || =
| |
| − | | 3 + 1 || =
| |
| − | | 2 + 2 || =
| |
| − | | 2 + 1 + 1 || =
| |
| − | | 1 + 1 + 1 + 1
| |
| − | |}
| |
| − | | |
| − | さて、分割 6 + 4 + 3 + 1 を表す図形を、その主対角線に沿ってひっくりかえすと、整数 14 のまた別の分割が得られる。
| |
| − | {| align="center"
| |
| − | |- style="vertical-align:top; text-align:left;"
| |
| − | | [[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| |
| − | | style="vertical-align:middle;"| ↔
| |
| − | | [[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| |
| − | |- style="vertical-align:top; text-align:center;"
| |
| − | | 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;"| [[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| |
| − | | style="vertical-align:middle;"| ↔
| |
| − | | style="vertical-align:bottom;"| [[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| |
| − | |}
| |
| − | : 以下の例にあるような方法で、相異なる奇数への分割全体のなす集合と自己共軛な分割全体のなす集合との間に全単射を得ることができる。
| |
| − | :{| align="center"
| |
| − | |-
| |
| − | | valign="top" | [[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|o]]<br />[[File:GrayDot.svg|16px|o]]
| |
| − | | style="vertical-align:middle;"| ↔
| |
| − | | valign="top" | [[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]]
| |
| − | |- 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'' の分割の総数に等しい。
| |
| − | | |
| − | == ヤング図形 ==
| |
| − | {{Main|ヤング図形}}
| |
| − | 整数の分割の別の視覚的な表現に、イギリス人数学者[[アルフレッド・ヤング]]に因んで名づけられた、'''ヤング図形'''がある。フェラーズ図形では丸で表していたものを、ヤング図形では箱型を使う。つまり、分割 5 + 4 + 1 に対するヤング図形は
| |
| − | [[Image:Young diagram for 541 partition.svg|center|100px|5+4+1]]
| |
| − | である。同じ分割のフェラーズ図形は
| |
| − | {| align="center"
| |
| − | |- style="vertical-align:top; text-align:left;"
| |
| − | | [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| |
| − | |- style="vertical-align:top; text-align:center;"
| |
| − | |}
| |
| − | | |
| − | これは一見取り立てて分けて述べる価値のあるようには思われないつまらない違いにも見えるが、実際には[[対称函数]]や[[群の表現論]]の研究にとってヤング図形はきわめて有用な存在となる。特に、ヤング図形の箱の中に様々な決まりのもとで数値（あるいはもっと複雑な対象）を書き込むことで、[[ヤング盤]]と呼ばれる対象を導入することができて、それが組合せ論や群の表現論で効果を発揮するのである。
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{脚注ヘルプ}}
| |
| − | {{reflist|2}}
| |
| − | | |
| − | == 参考文献 ==
| |
| − | *{{Citation|last=Andrews|first=George E.|date=1976|title=The Theory of Partitions|publisher=Cambridge University Press|isbn=0-521-63766-X}}
| |
| − | *{{Citation |last1=Andrews|first1=George E.|last2=Eriksson|first2=Kimmo |title=Integer Partitions |edition=2nd|publisher=Cambridge University Press |year=2004 |isbn=0-521-60090-1}}
| |
| − | **{{Cite book|和書|author=ジョージ・アンドリュース|coauthors=キムモ・エリクソン|others=[[佐藤文広]] 訳|date=2006-05|title=整数の分割|publisher=数学書房(出版) 白揚社(発売)|isbn=978-4-8269-3103-8|url=http://www.sugakushobo.co.jp/903342_61_mae.html|ref={{Harvid|アンドリュース|エリクソン|2006}}}} - 注記：[[#CITEREFAndrewsEriksson2004|原著第2版]]の翻訳。
| |
| − | *{{Citation|last=Apostol|first=Tom M.|author-link=トム・アポストル|date=1990|title=Modular functions and Dirichlet Series in Number Theory|publisher=Springer-Verlag|location=New York|edition=2nd|series=Graduate Texts in Mathematics (Book 41)|isbn=978-0-387-97127-8}} - 注記：第5章のRademacherの公式に対する教育的な導入を参照。
| |
| − | *{{Citation |last=Bóna |first=Miklós |title=A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory |publisher=World Scientific Publishing |year=2002 |isbn=981-02-4900-4}} - 自然数の分割に関する話題の初等的な導入。フェラーズ図形に関する議論も含まれる。
| |
| − | *{{Citation|author1=Gupta|author2=Gwyther|author3=Miller|year=1962|title=Roy. Soc. Math. Tables, vol 4, Tables of partitions}} - 注釈：解説とほぼ完全な文献表を含む。ただし、執筆者（およびAbramowitz）は {{Harvnb|Whiteman|1956}} による A<sub>k</sub>(n) の Selberg の公式を挙げていない。
| |
| − | *{{Citation|last=Macdonald|first=Ian G.|author=Ian G.|author-link=イアン・マクドナルド|date=1979|title=Symmetric functions and Hall polynomials|publisher=[[オックスフォード大学出版局|Oxford University Press]]|isbn=0-19-853530-9}} - 注釈：第1.1章を参照。
| |
| − | *{{Citation|last=Rademacher|first=Hans|author-link=ハンス・ラーデマッヘル|date=1974|title=Collected Papers of Hans Rademacher|publisher=MIT Press|volume=v II|pages=100–107, 108–122, 460–475}}
| |
| − | *{{Citation|last=Stanley|first=Richard P.|date=1999|title=Enumerative Combinatorics|publisher=Cambridge University Press|volume=Volumes 1 and 2|isbn=0-521-56069-1|url=http://www-math.mit.edu/~rstan/ec/}}
| |
| − | *{{Citation|last=Sautoy|first=Marcus du|author-link=マーカス・デュ・ソートイ|date=2012-08-14|title=The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics|publisher=Harper Perennial|location=New York|edition=Reprint|isbn=978-0-06-206401-1|url=https://www.harpercollins.com/9780062064011/the-music-of-the-primes}}
| |
| − | **{{Cite book|和書|author=マーカス・デュ・ソートイ|others=[[冨永星]] 訳|date=2005-08|title=素数の音楽|series=新潮クレスト・ブックス|publisher=新潮社|isbn=4-10-590049-8|ref={{Harvid|ソートイ|2005}}}}
| |
| − | **{{Cite book|和書|author=マーカス・デュ・ソートイ|others=冨永星 訳|date=2013-10|title=素数の音楽|series=新潮文庫 シ-38-1|publisher=新潮社|isbn=978-4-10-218421-9|ref={{Harvid|ソートイ|2013}}}}
| |
| − | *{{Citation|last=Whiteman|first=A. L.|year=1956|title=A sum connected with the series for the partition function|journal=Pacific Journal of Mathematics|volume=6|issue=1|pages=159–176|url=http://projecteuclid.org/euclid.pjm/1103044252}} - 注釈：Selbergの公式を与えている。古い形式のSelbergの有限フーリエ展開。
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * {{仮リンク|支配的順序|en|Dominance order}}(Dominance order)
| |
| − | * {{仮リンク|写像12相|en|Twelvefold way}}(Twelvefold way)
| |
| − | * [[集合の分割]]
| |
| − | * {{仮リンク|乗法的分割|en|Multiplicative partition}} (Multiplicative partition)
| |
| − | * {{仮リンク|ダーフィー正方形|en|Durfee square}}: [[ヤング図形]]の左上隅を含む最大の正方形
| |
| − | * [[多重集合]]
| |
| − | * {{仮リンク|丁寧数|en|Polite number}}(Polite number)/[[台形数]] (trapezoidal numbers)/[[階段数]] (staircase numbers): 連続する整数への分割から定まる
| |
| − | * {{仮リンク|ニュートンの公式|en|Newton's identities}} (Newton's identities): ある種の対称函数の間で成り立つ変換公式
| |
| − | * {{仮リンク|平面の分割|en|Plane partition}} : 平面[[植木算]]
| |
| − | * {{仮リンク|見えない数|en|A Disappearing Number}} - 2007年に [[Complicite]] で上演された作品。分割関数に関するラマヌジャンの論文に言及。
| |
| − | * [[ヤング束]] (Young's lattice) :「ヤング束(そく)」と読む
| |
| − | | |
| − | == 外部リンク ==
| |
| − | * {{MathWorld | urlname=Partition | title=Partition }}
| |
| − | * [http://www.sciencenews.org/articles/20050618/bob9.asp Pieces of Number] from Science News Online
| |
| − | * [http://www.math.upenn.edu/%7Ewilf/PIMS/PIMSLectures.pdf Lectures on Integer Partitions] by Herbert S. Wilf
| |
| − | * [http://www.site.uottawa.ca/~ivan/F49-int-part.pdf Fast Algorithms For Generating Integer Partitions]
| |
| − | * [http://arxiv.org/abs/0909.2331 Generating All Partitions: A Comparison Of Two Encodings]
| |
| − | | |
| − | {{DEFAULTSORT:せいすうふんかつ}}
| |
| − | [[Category:初等整数論]]
| |
| − | [[Category:組合せ論]]
| |
| − | [[Category:数学に関する記事]]
| |